16
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Is a trailing comma allowed? Or better still, space separated, e.g. ``` 5 3 2 7``` \$\endgroup\$ Commented Oct 10, 2015 at 19:58
  • 5
    \$\begingroup\$ As long as it is human readable and can tell me the primes, feel free. \$\endgroup\$ Commented Oct 10, 2015 at 19:59

6 Answers 6

8
\$\begingroup\$

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)
\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Very nice! Good to know that spiral function \$\endgroup\$
    – Luis Mendo
    Commented Oct 11, 2015 at 18:39
6
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ Could 2/4* be replaced by 2*, or have you left it like that on purpose? \$\endgroup\$ Commented Oct 10, 2015 at 22:34
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Oct 10, 2015 at 22:39
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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}
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ That was quite a bit of compression. Can you explain your original code and your changes? \$\endgroup\$ Commented Oct 13, 2015 at 0:06
  • \$\begingroup\$ 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 \$\endgroup\$
    – juanmf
    Commented Oct 13, 2015 at 3:32
  • \$\begingroup\$ 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. \$\endgroup\$
    – juanmf
    Commented Oct 13, 2015 at 3:38
  • \$\begingroup\$ 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. \$\endgroup\$
    – juanmf
    Commented Oct 13, 2015 at 3:45
  • \$\begingroup\$ 364 -> 240 by writing fn logic inline and removing unused tests. \$\endgroup\$
    – juanmf
    Commented Oct 13, 2015 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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