[Tutor] Primes on a two-dimensional plane in the form of
arectangular spiral
Gregor Lingl
glingl@aon.at
Mon, 09 Apr 2001 19:30:15 +0200
--------------A10B7D9871003B18E15DEEBB
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Daniel Yoo wrote:
... 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...
Here I propose a different derivation of this formula:
[Geometry mode on. No warnings!]
n n n n n n n
n x x x x x n
n x ... x n
n x . O x n
n x .. x n
n A x x x x n
B
In this pattern A is at location ( -(n-1), -(n-1) )
an B is at location (-n, -n)
There a (2*n-1)**2 points in the inner square,
consuming indices from 0 to (2*n-1)**2 - 1,
and 6*n points at the rim of the outer square, so
(2*n-1)**2 - 1 + 6*n = 4*n**2 -4*n + 1 - 1 + 6*n =
4*n**2+2*n = 2*n*(2*n+2) as was our desire!
I've continued to follow this quasi-pythagorean
approach of simple counting (beginning with the
index 1 for the point (0/0)) and arrived at the
following code:
def loc_number(M,N):
if M==0 and N==0:
return 1
maxabs = max(abs(M),abs(N))
innersquare = (2 * maxabs-1)**2
if M == maxabs and N > -maxabs:
rest = maxabs + N
elif N == maxabs:
rest = 3 * maxabs - M
elif M == -maxabs:
rest = 5 * maxabs - N
else:
rest = 7 * maxabs + M
return innersquare + rest
# which can be accompanied by
def dannies_loc_number(M,N):
return loc_number(M,N) - 1
Of course I'm curious, if someone else
(who has already or is off to buy a copy
of Mathematica) finds a more elegant or
more concise solution.
Always interested in useless problems
Gregor L.
Here follow - for reference - Daniels complete reply to Julieta:
> 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*
>
> _______________________________________________
> Tutor maillist - Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
--------------A10B7D9871003B18E15DEEBB
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<p>Daniel Yoo wrote:
<p>... but it's a pattern, and there might be a very cute
<br>way of writing a function that can quickly find, given a position,
the nth
<br>number. I'll take a closer look at this when I have time ---
this looks
<br>really interesting!
<p>Skip below if you want to listen to me ramble about discrete math while
<br>I'm working at this... *grin*
<p>(note: yes, there is a cute way.
<p>>>> def a(n): return 2*n*(1+2*n)
<br>...
<br>>>> a(0), a(1), a(2), a(3), a(4)
<br>(0, 6, 20, 42, 72)
<p>The method for deriving this is below.)
<p>---
<p>[Math mode on. Warning!]
<p>Hmmm...
<p><tt>Here I propose a different derivation of this formula:</tt>
<p><tt>[Geometry mode on. No warnings!]</tt>
<p><tt> n n n n n n n</tt>
<br><tt> n x x x x x n</tt>
<br><tt> n x ... x n</tt>
<br><tt> n x . O x n</tt>
<br><tt> n x .. x n</tt>
<br><tt> n A x x x x n</tt>
<br><tt> B</tt>
<p><tt>In this pattern A is at location ( -(n-1), -(n-1) )</tt>
<br><tt>an B is at location (-n, -n)</tt>
<p><tt>There a (2*n-1)**2 points in the inner square,</tt>
<br><tt>consuming indices from 0 to (2*n-1)**2 - 1,</tt>
<br><tt>and 6*n points at the rim of the outer square, so</tt>
<br><tt>(2*n-1)**2 - 1 + 6*n = 4*n**2 -4*n + 1 - 1 + 6*n =</tt>
<br><tt>4*n**2+2*n = 2*n*(2*n+2) as was our desire!</tt>
<p><tt>I've continued to follow this quasi-pythagorean</tt>
<br><tt>approach of simple counting (beginning with the</tt>
<br><tt>index 1 for the point (0/0)) and arrived at the</tt>
<br><tt>following code:</tt>
<br>
<p><tt>def loc_number(M,N):</tt>
<br><tt> if M==0 and N==0:</tt>
<br><tt> return 1</tt>
<br><tt> maxabs = max(abs(M),abs(N))</tt>
<br><tt> innersquare = (2 * maxabs-1)**2</tt>
<br><tt> if M == maxabs and N > -maxabs:</tt>
<br><tt> rest = maxabs + N</tt>
<br><tt> elif N == maxabs:</tt>
<br><tt> rest = 3 * maxabs -
M</tt>
<br><tt> elif M == -maxabs:</tt>
<br><tt> rest = 5 * maxabs -
N</tt>
<br><tt> else:</tt>
<br><tt> rest = 7 * maxabs +
M</tt>
<br><tt> return innersquare + rest</tt>
<p><tt># which can be accompanied by</tt>
<p><tt>def dannies_loc_number(M,N):</tt>
<br><tt> return loc_number(M,N) - 1</tt>
<p><tt>Of course I'm curious, if someone else</tt>
<br><tt>(who has already or is off to buy a copy</tt>
<br><tt>of Mathematica) finds a more elegant or</tt>
<br><tt>more concise solution.</tt>
<p><tt>Always interested in useless problems</tt>
<br><tt>Gregor L.</tt>
<br>
<br>
<p>Here follow - for reference - Daniels complete reply to Julieta:
<blockquote TYPE=CITE>On Sun, 8 Apr 2001, Julieta wrote:
<p>> The primes, 2,3,4,5,7, . . . can be arranged on a two-dimensional
<br>> plane in the form of a rectangular spiral.
<p>> <-represents left -> represents right
^represents up | represents down
<br>>
<br>> 59 <- 53 <- 47 <- 43
<- 41
<br>>
^
<br>> 11 <-
7 <- 5 <-
37
<br>> |
^ ^
<br>> 13
2 -> 3
31
<br>> |
^
<br>> 17 ->
19 -> 23 -> 29
<br>>
<br>> How could I write a program which inputs integers M and N and outputs
<br>> the value of the number at location (M, N) on the plane? The
initial
<br>> 2 is stored at position (0,0). This means that an input of
( 0, 0 )
<br>> should output 2. An input of, say, ( -1, 1) should output 11;
an
<br>> input of (-1,2) should output 53, and so on.
<p>Wow! This looks like a really interesting problem. The problem
with the
<br>primes doesn't seem as interesting as trying to get the cycle thing
<br>going. The cycle problem seems rife with patterns; it'd be nice
to get it
<br>working.
<br>
<p>The first problem that I'm seeing is trying to figure out a function
that,
<br>given a location, tells us which prime we're looking for. Let's
see if
<br>there are patterns...
<p>nth location
<br>--- ------
<br>0 (0, 0)
<br>1 (1, 0)
<br>2 (1, 1)
<br>3 (0, 1)
<br>4 (-1, 1)
<br>5 (-1, 0)
<br>6 (-1, -1)
<br>...
<p>The numbers that are catching my eye, at the moment, are the ones on
the
<br>diagonal in Quadrant three:
<p>nth location
<br>--- ------
<br>0 (0, 0)
<br>6 (-1, -1)
<br>20 (-2, -2)
<br>42 (-3, -3)
<br>... ...
<p>The reason that these numbers seem interesting to me is that if we start
<br>taking the differences between them, there's an interesting pattern
that
<br>occurs:
<p>0 6 20 42
# Position numbers on the diagonal
<br> 6 14 22
# Difference level 1
<br> 8 8
# Difference level 2
<p>As a prediction, I suspect that at position (-4, -4), we are trying
to
<br>print out the 72th number. I haven't testing this yet.
The reason for
<br>this guess is because there's a way to consistantly extend this pattern:
<p>0 6 20 42
72
<br> 6 14 22 30
<br> 8 8 8
<p>But I'd have to draw it out to manually verify this. Testing it
now...
<br>verified! Yes: the number at position (-4, -4) should be the
72th prime.
<br>Cool, so that's one pattern we might be able to exploit here, that
if we
<br>take the difference between two diagonal positions, the gap between
the
<br>appears to expand at a rate of 8.
<p>This might not help, but it's a pattern, and there might be a very cute
<br>way of writing a function that can quickly find, given a position,
the nth
<br>number. I'll take a closer look at this when I have time ---
this looks
<br>really interesting!
<p>Skip below if you want to listen to me ramble about discrete math while
<br>I'm working at this... *grin*
<p>(note: yes, there is a cute way.
<p>>>> def a(n): return 2*n*(1+2*n)
<br>...
<br>>>> a(0), a(1), a(2), a(3), a(4)
<br>(0, 6, 20, 42, 72)
<p>The method for deriving this is below.)
<p>---
<p>[Math mode on. Warning!]
<p>Hmmm... I'd like to label those three sequences I was looking
at earlier:
<p>0 6 20 42
72 # Let's
call this sequence (a)
<br> 6 14 22 30
# Let's call this sequence (b)
<br> 8 8 8
# Let's call this sequence (c)
<p>The problem that I'd like to solve is to find a nice formula for sequence
<br>(a) --- that would solve the problem of finding which nth prime should
go
<br>on the diagonals. Sequence (c) isn't that interesting, because
it's just
<br>all 8s.
<p>Let's look at sequence (b). Sequence (b) isn't that much harder,
because
<br>every time we go up the sequence, we just need to add 8 to what we
had
<br>before. This translates, in math, to:
<p> b(n) = 6 + 8 * n
<p>With this done, we might be able to handle sequence (a), which looks
a
<br>little weirder. In order to get from one part of the sequence
to the
<br>next, we need to add a corresponding element from (b). More formally:
<p> a(0) = 0
<br> a(n) = a(n-1) + b(n-1)
<p>Let's see if this works in Python.
<p>###
<br>>>> def b(n): return 6 + 8*n
<br>...
<br>>>> def a(n):
<br>... if n == 0: return 0
<br>... else: return a(n-1) + b(n-1)
<br>...
<br>>>> a(0), a(1), a(2), a(3), a(4)
<br>(0, 6, 20, 42, 72)
<br>###
<p>Very cool. So this is a perfectly good way of solving the problem
of
<br>finding which prime numbers should go on the diagonal. But we
can go even
<br>further, if we're perverse enough. It's also very true that:
<p> a(n) = a(n-1) + 8*(n-1) + 6
<br> = a(n-1) + 8*n - 2
<p>if we substitute the value of b(n-1) into the equation. If I were
to do
<br>this by hand, I'd use a math technique called generating functions
that
<br>can take something like:
<p> a(0) = 0
<br> a(n) = a(n-1) + 8*n - 2
<p>and transform it into something nicer.
<p>But I'm cheap and ignorant about generating functions still, so I'll
use
<br>Mathematica instead. According to Mathematica's RSolve function,
<p> a(n) = 2n(1+2n)
<p>Does this work?
<p>###
<br>>>> def a(n): return 2*n*(1+2*n)
<br>...
<br>>>> a(0), a(1), a(2), a(3), a(4)
<br>(0, 6, 20, 42, 72)
<br>###
<p>My gosh. I must learn how generating functions work, so that I
can see
<br>how in the world that worked. *grin*
<p>_______________________________________________
<br>Tutor maillist - Tutor@python.org
<br><a href="http://mail.python.org/mailman/listinfo/tutor">http://mail.python.org/mailman/listinfo/tutor</a></blockquote>
</html>
--------------A10B7D9871003B18E15DEEBB--