Ulam's spiral is a truly fascinating, yet puzzling, topic in mathematics. How it works in detail can be found here, but a short summary can be explained as so:

I start off by writing a one, then I write a two to the right of it. Above the two, I write a three, and to the left of that I write four. I continue this pattern of circling around 1 (and any numbers between me and 1) infinitely (or until told to stop), forming a spiral pattern. (see example below)

The Objective

Make a program that accepts n (will always be an odd number greater than zero) as an input that correlates with the number of rows, then prints out the values of the primes row by row of the Ulam spiral. The formatting can be any fashion, but must be human readable and obvious.

For example, given the input 3, your program should output 5,3,2,7, because 3 rows produces the following spiral:

5 4 3 <-- first row has the primes 5 and 3
6 1 2 <-- second row has the prime 2
7 8 9 <-- third row has the prime 7

As this is a code golf, the answer with the fewest bytes wins (no matter how inefficient)! Standard loopholes are not acceptable.

  • Is a trailing comma allowed? Or better still, space separated, e.g. ``` 5 3 2 7``` – Tom Carpenter Oct 10 '15 at 19:58
  • 5
    As long as it is human readable and can tell me the primes, feel free. – Addison Crump Oct 10 '15 at 19:59
up vote 9 down vote accepted

Pyth, 20 bytes

f}TPTsuC+R=hZ_GtyQ]]

Try it online: Demonstration

This code generates the fully Ulam's spiral, connects all lines and filters for primes.

Explanation:

f}TPTsuC+R=hZ_GtyQ]]   implicit: Z = 0
      u           ]]   reduce, start with G = [[]]
               tyQ     for H in [0, 1, ..., 2*input-2] do:
             _G           reverse the order of the lines
        +R=hZ             append Z + 1 at the end of each line, 
                          updating Z each time with the new value Z + 1
       C                  update G with the transposed of ^
                       this gives the Ulam's spiral
     s                 combine all lines to a big list of numbers
f                      filter for numbers T, which satisfy:
 }TPT                    T appears in the prime-factorization of T
                         (<==> T is prime)

MATLAB, 48

a=fliplr(spiral(input(''))');disp(a(isprime(a)))

Basically this creates a spiral of the required size (requested from user), then arranges it so that it appears in the correct row order. This is stored in a. Next it displays all values in a which are prime.

As you said any readable format, I saved a byte and went for the default output of disp() which is (in your test case, n=3):

 5
 3
 2
 7

As an added bonus, this works for any n>0, including even numbers. For example, the output for n=10 is:

97
61
59
37
31
89
67
17
13
 5
 3
29
19
 2
11
53
41
 7
71
23
43
47
83
73
79
  • 1
    Very nice! Good to know that spiral function – Luis Mendo Oct 11 '15 at 18:39

CJam, 42 33 bytes

Xali(2*{_W%zY@,Y+:Y,>a+}*e_{mp},`

Try it online

The latest version includes substantial improvements suggested by @Martin.

The method for building the spiral is to, in each step, rotate the matrix we have so far by 90 degrees, and add a row with additional numbers. This is repeated (n / 2) * 4 times.

The values in the resulting matrix are then filtered for being primes.

Explanation:

Xa    Push initial matrix [1].
li    Get input and convert to int.
(2*   Calculate 2*(n-1), which is the number of rotations and row additions needed.
{     Start rotation loop.
  _     Copy current matrix for getting number of rows later.
  W%    Reverse the order of the rows...
  z     ... and transpose the matrix. The combination produces a 90 degree rotation.
  Y     Get next value from variable Y (which is default initialized to 2).
  @,    Rotate previous matrix to top, and get number of rows. This is the number
        of columns after the 90 degree rotation, meaning that it's the length of
        the row to be added.
  Y+    Add first value to row length to get end value.
  :Y    Save it in Y. This will be the first value for next added row.
  ,     Create list of values up to end value.
  >     Slice off values up to start value, leaving only the new values to be added.
  a+    Wrap the new row and add it to matrix.
}*    End of rotation loop.
e_    Flatten matrix into list.
{mp}, Filter list for primes.
`     Convert list to string for output.
  • Could 2/4* be replaced by 2*, or have you left it like that on purpose? – ETHproductions Oct 10 '15 at 22:34
  • @ETHproductions That's not equivalent because it's an integer division. For example, for input 3, the result needs to be 4. Actually, now that I think about it, I believe there is a byte to be saved. (2* should be correct. – Reto Koradi Oct 10 '15 at 22:39

Mathematica 223

This appropriates Kuba's code for an Ulam spiral. That's why I'm submitting it as a community wiki. I merely golfed it and selected out the primes, which are listed by the row in which they reside.

r=Range;i=Insert;t=Transpose;s@n_:=#~Select~PrimeQ&/@Nest[With[{d=Length@#,l=#[[-1,-1]]},
Composition[i[#,l+3d+2+r[d+2],-1]&,t@i[t@#,l+2d+1+r[d+1],1]&,i[#,l+d+r[d+1,1,-1],1]&,
t@i[t@#,l+r[d,1,-1],-1] &][#,15]]&,{{1}},(n-1)/2]

Example

 s{15]

{{197, 193, 191}, {139, 137}, {199, 101, 97, 181}, {61, 59, 131}, {103, 37, 31, 89, 179}, {149, 67, 17, 13}, {5, 3, 29}, {151, 19, 2, 11, 53, 127}, {107, 41, 7}, {71, 23}, {109, 43, 47, 83, 173}, {73, 79}, {113}, {157, 163, 167}, {211, 223}}

To improve the display:

 %// MatrixForm

matrix

Mathematica, 118 bytes

f=Permute[Range[#*#],Accumulate@Take[Join[{#*#+1}/2,Flatten@Table[(-1)^j i,{j,#},{i,{-1,#}},{j}]],#*#]]~Select~PrimeQ&

This generates the Ulam spiral in linear form by noting that the position of each subsequent number can be accumulated as

{(n*n + 1)/2, +1, -n, -1, -1, +n, +n, +1, +1, +1, -n, -n, -n, ...}

i.e. start from the centre, then move 1 right, 1 up, 2 left, 2 down, 3 right, 3 up, ...

Output:

In[515]:= f[5]
Out[515]= {17,13,5,3,19,2,11,7,23}

Javascript, 516 363 304 276 243 240 Bytes

My solution does not create a dense matrix with the Spiral, instead it returns the index that corresponds to the given number in the Ulam's Matrix of the given order. So it iterates through the numbers between 2 and M*M and creates an array of primes with the idx given by the fn ulamIdx

M=15;
$=Math;
_=$.sqrt;
/**
 * Return M*i+j (i.e. lineal or vector idx for the matrix) of the Ulam Matrix for the given integer
 * 
 * Each Segment (there are 4 in each round) contains a line of consecutive integers that wraps the 
 * inner Spiral round. In the foCowing example Segments are: {2,3}, {4,5},
 * {6,7}, {8,9}, {a,b,c,d}, {e,f,g,h}, {i,j,k,l}, {m,n,o,p}  
 *            
 *    h g f e d
 *    i 5 4 3 c
 *    j 6 1 2 b
 *    k 7 8 9 a 
 *    l m n o p
 * 
 * @param n integer The integer which position in the Matrix we want.
 * @param M integer Matrix Order. 
 */
/*
 * m: modulus representing step in segment in current spirtal round
 * v: Step in current spiral round, i.e. n - (inner spirals greatest num.)
 * s: the current Segment one of [1, 2, 3, 4] that represents the current spiral round 
 * L: Segment Length (Current spiral round Order - 1)
 * B: inner Spiral Order, for trib¿vial case 1 it's -1 special case handled differently.
 * C: relative line (row or column) corresponding to n in current spiral Round 
 * R: relative line (column or row) corresponding to n in current spiral Round
 * N: Curren (the one that contains n) Spiral (matrix) round Order
 * D: Difference between M and the current Spiral round order.
 */

/**
 * Runs the loop for every integer between 2 and M*M
 * Does not check sanity for M, that should be odd.
 */
r=[];
for (x = 2; x < M * M; x++) {
    p=1;
    // Is Prime?
    for (k = 2; p&&k <= _(x); k++)
        if (x % k==0) p=0;
    if (p) {
        B = $.floor(_(x - 1));
        B=B&1?B:B-1;
        N = B + 2;
        D = (M - N) / 2;
            v = x - B * B;
            L = B + 1;
            s = $.ceil(v / L);
            m = v % L || L;
            C = D + (s < 3 ? N - m : 1 + m);
            R = s&2 ? D + 1 : D + N;
            w= s&1 ? M * C + R : M * R + C;
        // /*uncomment to debug*/ console.log("X:" + x + ": " + ((s&1) ? [C, R].join() : [R, C].join()));
        r[w] = x;
    }
}
alert(r);

Minified looks like this:

for(M=15,$=Math,_=$.sqrt,r=[],x=2;x<M*M;x++){for(p=1,k=2;p&&k<=_(x);k++)x%k==0&&(p=0);p&&(B=$.floor(_(x-1)),B=1&B?B:B-1,N=B+2,D=(M-N)/2,v=x-B*B,L=B+1,s=$.ceil(v/L),m=v%L||L,C=D+(s<3?N-m:1+m),R=2&s?D+1:D+N,w=1&s?M*C+R:M*R+C,r[w]=x)}alert(r);

For input 15 the output is:

,,,,,,,,,,,,,,,,197,,,,193,,191,,,,,,,,,,,,,,,,139,,137,,,,,,199,,101,,,,97,,,,,,,,181,,,,,,,,61,,59,,,,131,,,,103,,37,,,,,,31,,89,,179,,149,,67,,17,,,,13,,,,,,,,,,,,5,,3,,29,,,,,,151,,,,19,,,2,11,,53,,127,,,,107,,41,,7,,,,,,,,,,,,71,,,,23,,,,,,,,,,109,,43,,,,47,,,,83,,173,,,,73,,,,,,79,,,,,,,,,,113,,,,,,,,,,,,157,,,,,,163,,,,167,,,,211,,,,,,,,,,,,223

  • That was quite a bit of compression. Can you explain your original code and your changes? – Addison Crump Oct 13 '15 at 0:06
  • I removed some useless brackets. And realized that uI() had 4 conditionals with similar blocks. Each with 3 lines that generated Row and Collumn for the current segment (see main docblock) so I replacef thos 4 blocks by ll&llt lines and the return line decides if llt is row or column. S&2 is true for s in (3,2) (upper & left segments); s <3 , for s in (1,2) right & upper. S&1, for s in (1,3) will determine if the values in ll & llt are row & col or col&row and M (spiral order) × row +col preventes overlaping indexes (like rectifying matrix but with wrong lineal idx, correctness would need ll-1 – juanmf Oct 13 '15 at 3:32
  • In the main loop (run ()) only if i is prime (which fn was reduced as never need to test for <2 nor %1 ) it asks for i's index (ll,llt) in the spiral, which cames rectified. Then just print the result array. – juanmf Oct 13 '15 at 3:38
  • There are 3 conceptually important matrices. Inner, curret & M. Useful for calculating absolute row & col. Substracting inner to n leaves uss with a relative int in current (the one in which n falls ) spiral round. And the diff between M's and current's order plays as offset for row and col in current round to get absolutes ones. – juanmf Oct 13 '15 at 3:45
  • 364 -> 240 by writing fn logic inline and removing unused tests. – juanmf Oct 13 '15 at 14:18

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.