Show Ulam's spiral

Similar to this but in this one you need to write spiral starting from the center where:

space means composite number
.(dot) means prime number.

Size of the spiral can be given as parameter or on stdin. By size I mean side of square NxN and also N will be always odd.

Hauleth

Posted 2012-01-08T21:25:58.407

Reputation: 1 472

3Doesn't Ulam's spiral usually start with 1 in the middle and spiral outward, instead of spiraling inward? – PhiNotPi – 2012-01-08T21:32:44.277

Yeah, it's late so my brain is out of order. – Hauleth – 2012-01-08T22:17:00.880

By size of the spiral do you mean the number to go up to, or the number of spirals? – Gareth – 2012-01-08T22:24:13.833

Also, are there limits on the number that may be input or is it 1 to infinity? – Gareth – 2012-01-08T22:29:20.357

Square NxN and limit to 100000 – Hauleth – 2012-01-08T22:50:41.013

– gnibbler – 2012-01-09T23:02:58.803

Wow, the J paper linked to in the original post of that question is amazing. 72 characters! ' .'{~1 p:>:|.(,~$/:@(+/\)@(_1&|.@((}:@(2:#>:@i.))#(<:@+:$1:,],_1:,-)))) – Gareth – 2012-01-10T00:31:24.900

Answers

Python, 219 chars

N=input()
A={0:' '}
d=1j
x=1
for p in range(2,N*N+1):
 A[x]=' .'[all(p%i for i in range(2,p))]
 if abs(x.imag)==abs(x.real):x+=(1-1j)*(d==1);d*=1j
 x+=d
R=range(N)
for y in R:print''.join(A[x-N/2+(N/2-y)*1j]for x in R)

Works for any odd N. For example:

$ echo 9 | ./ulam.py 
    . .  
 .     . 
. .   .  
   . . . 
  .  .. .
 . .     
.   .    
 .   .   
.     .

Keith Randall

Posted 2012-01-08T21:25:58.407

Reputation: 19 865

JavaScript (~~240~~ ~~202~~ ~~195~~ 151 characters)

Update: Another much smaller version without function (a lot of credits to @mellamokb):

for(x=3,e=d=f=a>>1,c=2;(x&1?x&2?++e<a-d:--e>d:x&2?++f<a-d-1:--f>d)||++x&3||d--;c
++)for(g=0;g<2*a*a;z[g+=c]=1)z[c]||z.getContext("2d").fillRect(e,f,1,1)

Works with this HTML:

<script>a = 50</script>
<canvas id=z width=50 height=50></canvas>

25x25 example (zoomed in) - 800x800 example

This new version now performs well and outputs the right size (NxN) for any odd a.

Found some small improvements (195 now). Thanks @mellamokb.

Old version:

c=1;i=e=0;b={};for(d=[];c<a*a;){d.push("");for(i+=e+=2;i--;)d[Math.min(e-2,i)]+=
j();d.unshift("");for(i-=e;++i<e;)d[g=Math.max(0,i)]=j()+d[g]}x.innerHTML=d.join
("\n");function j(){if(f=!b[++c])for(h=c*c;h<2*a*a;h+=c)b[h]=1;return f?".":" "}

Currently takes variable a as input and outputs to an element with the id x:

<script>a = 50</script>
<pre id=x>

I used the Sieve of Eratosthenes for prime generation, which works really well. Output is quite slow so far though. Don't expect this to run for huge n yet.

copy

Posted 2012-01-08T21:25:58.407

Reputation: 6 466

I've used Math.max(0,i) trick in the past before thinking it was clever, but it's actually shorter to use a ternary: d[g=i>0?i:0]. Same with Math.min(e-2,i) which should be rewritten as d[i<e-2?i:e-2]. – mellamokb – 2012-01-09T21:30:32.917

@mellamokb: My never version doesn't use min or max anymore. But thanks for the tip; it's good to remember these minor optimizations. – copy – 2012-01-09T21:43:36.717

This is code-golf, so sacrifice a little performance to gain 3 chars: for(g=0;g<2*a*a;b[g+=c]=1); Likewise, move the whole for outside of the if and you can nix the {} for the if, saving another 2 characters :) – mellamokb – 2012-01-09T21:48:56.427

@mellamokb: wow, you're good at this. The second suggestion was even better because it can now be written as b[c]||z.getContext, saving 2 more characters. – copy – 2012-01-09T22:21:13.520

Working through some ideas. I have a few improvements to make, but I figured out this eval(["--f>d","--e>d","++f<a-d-1","++e<a-d"][x%4])||++x%4||d--;. Basically this replaces all the for(h().. and also changes the condition on the main loop to just d. Then you must define x=0 and subtract 1 from d to begin with since it's no longer in the condition. Finally, inline h() since it's now only called once, and should be able to save about 10 characters (hopefully) :). Will update with another idea that might save much more in a bit... – mellamokb – 2012-01-10T00:09:10.997

I figured out that if I started x at 3, then ++e runs first so you no longer need e=(..)+1. Also, then if I move the eval(..) to the front of the calls to h(), d-- gets applied first, so everything is correct again. However, then with a condition of d it stops one row early... so simply move the entire eval() and make it the condition of the main for loop! Then we can also move the ++c into the third part of the main for loop if we start c at 2 instead, saving another character. Here's the final working 163-character solution: – mellamokb – 2012-01-10T00:59:45.843

for(x=3,e=d=f=a>>1,c=2,b=[];eval(["--f>d","--e>d","++f<a-d-1","++e<a-d"][x%4])||++x%4||d--;c++)for(g=0;g<2*a*a;b[g+=c]=1)b[c]||z.getContext("2d").fillRect(e,f,1,1) (http://jsfiddle.net/SZp5v/2/) – mellamokb – 2012-01-10T00:59:53.723

@mellamokb: Nice one. This can be shortened even more by replacing the eval by ternary. And I think we can merge the 2 remaining loops, making this the least readable JavaScript code ever. I am working on it ... – copy – 2012-01-10T20:51:07.797

that's what code golf is all about :P love to see the outcome.. i do all JS answers on this site, u can look at some of my other ones. i'm not satisfied until every last possible optimization is made ^_^ – mellamokb – 2012-01-10T21:46:43.230

@mellamokb: Cut your version down to 151 chars. I also have this version with only one loop, but it's bigger. But this is great now.

– copy – 2012-01-10T22:54:20.837

Shaved off 3 more characters by optimizing the inner loop to use multiples of c instead of adding c over and over: for(i=0;a-i++;z[c*i]=1). Basic idea using index i and multiply by c. Also now only need to check i<=a instead of g<2*a*a. To optimize further, I use a-i instead and increment in the condition so that a-i==0 loop iteration is still performed. I'm also looking into optimizing the movement further by using x/y direction vectors and combining the four movement operations and conditions into a single one...stay tuned! :) – mellamokb – 2012-01-11T00:21:19.277

Golfscript - 92 Characters

Based on my answer here:

~.(:S+,:R{S\-:|;R{S-:$|>' .'1/[|$.|]2/@:d|~)$<!^=~:$;:y.*4*$-y-)2d*$y-*+:$,{)$\%!},,2==}%n}%

gnibbler

Posted 2012-01-08T21:25:58.407

Reputation: 14 170

APL (85)

K[R↑+\(1+M-⍨N×M←⌈N÷2),(2/⍳N)/(2×N)⍴1(-N)¯1N]←K←⍳R←N×N←⎕⋄'. '[1+N N⍴K∊P/⍨P∊P∘.×P←1↓⍳R]

Explanation:

Generating the spiral:
- K←⍳R←N×N←⎕: Read N from the user. The array size N×N is stored in R. K is [1..R].
- (1+M-⍨N×M←⌈N÷2): The coordinate of the middle field.
- (2×N)1(-N)¯1N: the delta coordinates for the next field (i.e. 1 right, up a line (so N fields to the left in a 1-dimensional array), then 1 left, then down a line.
- (2/⍳N)/: duplicate the deltas to form an expanding spiral. 2/⍳N is 1 1 2 2 3 3 ... N N, duplicating the deltas by these values gives right up left left down down right right right...
- R↑+\: sum these values (giving absolute coordinates) and take the first R.
- K[...]←K: assign K to K in the order given above. We now have K in spiral order.
Generating the pattern:
- P/⍨P∊P∘.×P←1↓⍳R: more or less the standard APL idiom for generating primes. P is [2..R], P∘.×P is a multiplication table for P. P∘.P therefore contains all composite numbers in the range [1..R]. P/⍨ then selects from P all values present in P∘.×P, giving a list of composite numbers.
- 1+N N⍴K∊: this selects from K all the composite numbers, giving a binary list in spiral order where there's an 1 if the number is composite. Then add 1 so that composite numbers are 2 and noncomposite (prime) numbers are 1. This is formatted as a N by N table.
- '. '[...]: prime numbers (1) become '.' and composites (2) become ' '.

marinus

Posted 2012-01-08T21:25:58.407

Reputation: 30 224