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

[Gregor Lingl]

Julieta schrieb:

> 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. I don't have any
> programming experience nor have I ever taken a computer programming
> class, however, I would like to start learning.  I've written very
> small programs (20 lines long) in my TI - 92 calculator and in Python,
> and I'm trying to build on that.  Right now I'm trying to learn some
> Python, so any kind of input on this problem would help
> tremendously.

Dear Julieta!

I assume, that 'any kind of input' doesn't mean a complete solution to
the problem.
So I'll provide some hints:

Befor beginning to code you have to know clearly how to solve the
problem
by hand.

I think it could be helpful to break up the problem in two smaller ones:

1. Calculate an n so that the the location (M,N) ist the n-th 'point' on
your
spiral, for instance:
                (0/0) ->1
                (1/0) ->2
                (1/1) ->3
                 ...
                (1/-1) -> 9
                (2/-1) -> 10
                (2/0)  -> 11
                ...
and so on.
2. Calculate the n-th prime. For this a simple (although probably not
very efficient) way would be to use the Sieve of Eratosthenes:
Write down all natural numbers from 1 to a certain maximum z (yet to
determine). Cancel 1. Next uncancelled number is 2 It's a prime: mark it

and cancel all the multiples of two. Next uncancelled number is 3.
It's a prime: mark it and cancel all the multiples of three, ... Repeat
this until
the square of the next uncacelled number ( = found prime) surpasses z.
Only primes remain in the list and now you can determine the n-th one.
As z use a number which will be securely big enough.

Remark: If you have an algorithm to determine if a given natural number
is
prime, an even simpler but less efficient way would be to go through the

natural numbers, determine for each one, if it is a prime and count it
...
until you arrive at the n-th prime.

3. Combine those two parts of the solution.

4. If you need more help on specific parts of the solution,
try to formulate clear questions and put them into the tutor-newsgroup.

5. If you arrive at a solution post it at   Useless Python , the best
place
where it belongs to.

Have fun, Gregor Lingl

P.S.: Interesting would be a (more or less) simple and efficient way to
calculate from a given prime p next_prime(p). Perhaps someone else
knows one ....