[Tutor] Primes on a two-dimensional plane in the form of a rectangular spiral

[Daniel Yoo]

On Sun, 8 Apr 2001, Julieta wrote:

> The primes, 2,3,4,5,7, . . . can be arranged on a two-dimensional
> plane in the form of a rectangular spiral.

> <-represents left   -> represents right    ^represents up     | represents down
> 
> 59 <-  53 <-  47  <-  43    <-    41
>                                              ^
>         11 <-   7    <-   5   <-     37
>           |                    ^            ^
>         13        2   ->   3           31
>           |                                 ^ 
>         17  ->  19  ->  23   ->    29
> 
> How could I write a program which inputs integers M and N and outputs
> the value of the number at location (M, N) on the plane?  The initial
> 2 is stored at position (0,0).  This means that an input of ( 0, 0 )
> should output 2.  An input of, say, ( -1, 1) should output 11; an
> input of (-1,2) should output 53, and so on.

Wow!  This looks like a really interesting problem.  The problem with the
primes doesn't seem as interesting as trying to get the cycle thing
going.  The cycle problem seems rife with patterns; it'd be nice to get it
working.

 
The first problem that I'm seeing is trying to figure out a function that,
given a location, tells us which prime we're looking for.  Let's see if
there are patterns...

nth  location
---  ------
0    (0, 0)
1    (1, 0)
2    (1, 1)
3    (0, 1)
4    (-1, 1)
5    (-1, 0)
6    (-1, -1)
...



The numbers that are catching my eye, at the moment, are the ones on the
diagonal in Quadrant three:

nth  location
---  ------
0    (0, 0)
6    (-1, -1)
20   (-2, -2)
42   (-3, -3)
...  ...

The reason that these numbers seem interesting to me is that if we start
taking the differences between them, there's an interesting pattern that
occurs:

0   6      20    42            # Position numbers on the diagonal
  6    14     22               # Difference level 1
    8      8                   # Difference level 2

As a prediction, I suspect that at position (-4, -4), we are trying to
print out the 72th number.  I haven't testing this yet.  The reason for
this guess is because there's a way to consistantly extend this pattern:

0   6    20    42    72
  6   14    22    30
    8    8     8 

But I'd have to draw it out to manually verify this.  Testing it now...
verified!  Yes: the number at position (-4, -4) should be the 72th prime.  
Cool, so that's one pattern we might be able to exploit here, that if we
take the difference between two diagonal positions, the gap between the
appears to expand at a rate of 8.


This might not help, but it's a pattern, and there might be a very cute
way of writing a function that can quickly find, given a position, the nth
number.  I'll take a closer look at this when I have time --- this looks
really interesting!

Skip below if you want to listen to me ramble about discrete math while
I'm working at this...  *grin*


(note: yes, there is a cute way.

>>> def a(n): return 2*n*(1+2*n)
...
>>> a(0), a(1), a(2), a(3), a(4)
(0, 6, 20, 42, 72) 

The method for deriving this is below.)


---

[Math mode on.  Warning!]

Hmmm...  I'd like to label those three sequences I was looking at earlier:

0   6    20    42    72           # Let's call this sequence (a)
  6   14    22    30              # Let's call this sequence (b)
    8    8     8                  # Let's call this sequence (c)

The problem that I'd like to solve is to find a nice formula for sequence
(a) --- that would solve the problem of finding which nth prime should go
on the diagonals.  Sequence (c) isn't that interesting, because it's just
all 8s.

Let's look at sequence (b).  Sequence (b) isn't that much harder, because
every time we go up the sequence, we just need to add 8 to what we had
before.  This translates, in math, to:

    b(n) = 6 + 8 * n

With this done, we might be able to handle sequence (a), which looks a
little weirder.  In order to get from one part of the sequence to the
next, we need to add a corresponding element from (b).  More formally:

    a(0) = 0
    a(n) = a(n-1) + b(n-1)

Let's see if this works in Python.

###
>>> def b(n): return 6 + 8*n
...
>>> def a(n):
...     if n == 0: return 0
...     else: return a(n-1) + b(n-1)
...
>>> a(0), a(1), a(2), a(3), a(4)
(0, 6, 20, 42, 72) 
###

Very cool.  So this is a perfectly good way of solving the problem of
finding which prime numbers should go on the diagonal.  But we can go even
further, if we're perverse enough.  It's also very true that:

    a(n) = a(n-1) + 8*(n-1) + 6
         = a(n-1) + 8*n - 2

if we substitute the value of b(n-1) into the equation.  If I were to do
this by hand, I'd use a math technique called generating functions that
can take something like:

    a(0) = 0
    a(n) = a(n-1) + 8*n - 2

and transform it into something nicer.



But I'm cheap and ignorant about generating functions still, so I'll use
Mathematica instead.  According to Mathematica's RSolve function,

    a(n) = 2n(1+2n)

Does this work?

###
>>> def a(n): return 2*n*(1+2*n)
...
>>> a(0), a(1), a(2), a(3), a(4)
(0, 6, 20, 42, 72) 
###

My gosh.  I must learn how generating functions work, so that I can see
how in the world that worked.  *grin*