Problems & Puzzles: Puzzles

Puzzle 529. The prime-explosion Bergot graph To my friend Pat McGill (March, 2010) JM Bergot sent the following very nice puzzle: Based on the fact that all primes except 5 are of the form 5n+1,2,3,4, go through all the primes from 2 onward, ignoring the prime 5, and construct a graph according the following algorithm: 1. Start the graph in the point (0,0) for the prime 2 2. Go to next prime 3. Determine if this prime is 5n+1 or 2 or 3 or 4 4.1 If 5n+1, move the point up one (add 1 to the y in point location (x,y)); 4.2 if 5n+2 move the point one to the right (add one to the current x of position (x,y); 4.3 If 5n+3 move the point down one (subtract one from the current y values of (x,y) 4.4 If 5n+4 move the point one to the left (subtract one from x in current position (x,y). 5 If prime is less that certain limit then go to step 2, else end. Continue this for as long as you want and notice that the graph (below, beauty, isn't it?) grows in size   but very few points are in the 1st and third quadrants; most in the fourth quadrant and NONE of ten million points in the second quadrant (Color was used to indicate density, meaning how many times the point was at any position in its continuing movements) Please see this animation (just click on the hyperlink). Q1. Arithmetical question: Will the graph ever enter to the second quadrant? is it impossible? can you prove it? The above rules of movement are just one possibility of 4! or 24 different ways of assigning moves to all of the four  cases (5n+1,2,3,4). Perhaps some of your readers want to create some original art with this little puzzle and other combination of rules?) Q2. Aesthetic question: Please send other Prime-explosion graphs and/or animations. I will publish the most 'beauty' of them, no matter the variations you decide to do. Just explain them. [Variations may try: a) another of the 4! cases mentioned above or b) using this puzzle for set of numbers other than the primes.]

---

C. Rivera wrote:

First of all, discarding symmetries there are only two basic types of these graphs (This is wrong. There are three basic types. See more below on this my mistake)

By very obvious reasons, I will call these two graphs:

a) The "O" graph, corresponding to the rules given by Bergot: 1=up, 2=right, 3=down & 4=left

b) The "L" graph, corresponding to the following rules: 1=up, 2=down, 3=right & 4=left

My own arithmetical results is that Q2 is empty until the  203,280,221-th prime, the prime 4,294,967,291, for both type of graphs.

Here are the results:

Graph type "O"		Quantity of primes in Qx				(x,y) at K
Prime index K	Prime(K)	Q1	Q2	Q3	Q4	x(K)	y(K)
10	29	0	0	0	9	1	-2
100	541	0	0	0	99	1	-2
1000	7919	1	0	0	998	9	-8
10000	104729	56	0	4	9939	18	-31
100000	1299709	3031	0	974	95994	7	-40
1000000	15485863	3076	0	8852	988071	75	-176
10000000	179424673	273416	0	128542	9598041	533	-454
100000000	2038074743	2840340	0	4705449	92454210	377	-700
1000000000	4294967291	3283230	0	6341261	193655728	1908	-425
Graph type "L"		Quantity of primes in Qx				(x,y) at K
Prime index K	Prime(K)	Q1	Q2	Q3	Q4	x(K)	y(K)
10	29	0	0	0	9	1	-2
100	541	0	0	0	99	2	-1
1000	7919	9	0	10	980	7	-10
10000	104729	16	0	301	9682	24	-25
100000	1299709	1526	0	4520	93953	-2	-49
1000000	15485863	6586	0	32268	961145	170	-81
10000000	179424673	300619	0	106638	9592742	458	-529
100000000	2038074743	1399021	0	5577319	93023659	109	-968
1000000000	4294967291	1399021	0	13029097	188852101	1472	-861

At this very moment I'm not able to offer you a graphic for the "L" graph as the sent by Bergot. Maybe later...

***

Thank to a Bergot's friend that wants not credits at all for his generous help, here is the "L" graph mentioned above, for one million points.

But before showing that graph let me tell you that he states that there are not two but three basic type of graphs:

Bergot's "O" type:
4.1 If 5n+1 move the point up one (add 1 to the y in point location (x,y));
4.2 if 5n+2 move the point one to the right (add one to the current x of position (x,y);
4.3 If 5n+3 move the point down one (subtract one from the current y values of (x,y)
4.4 If 5n+4 move the point one to the left (subtract one from x in current position (x,y).

Riveras's "L" type:
4.1 If 5n+1 move the point up one (add 1 to the y in point location (x,y));
4.2 if 5n+2 move the point down one (subtract one from the current y values of (x,y)
4.3 If 5n+3 move the point one to the right (add one to the current x of position (x,y);
4.4 If 5n+4 move the point one to the left (subtract one from x in current position (x,y).

Bergot's friend "Γ" Gamma-type:
4.1 If 5n+1 move the point up one (add 1 to the y in point location (x,y));
4.2 If 5n+2 move the point one to the right (add one to the current x of position (x,y);
4.3 If 5n+3 move the point one to the left (subtract one from x in current position (x,y).
4.4 if 5n+4 move the point down one (subtract one from the current y values of (x,y)

And the most surprising thing, the Gamma-type has points in all the four quadrants!!!

Here are these one-million points three basic graphs (See more about the three basic graphs on this power point presentation):

The "O"-type (one million points)

 The "L"-type (one million points)

 The "Gamma"-type (one million points):

***

After this, remains the following re-stated question:

Q3. Arithmetical question: Will the graphs "O" & "L" type ever enter to the second quadrant? is it impossible? can you prove it?

***

T. D. Noe wrote:

This problem is very closely related to the prime races problem. See
http://mathdl.maa.org/images/upload_library/22/Ford/granville1.pdf , which
is the very interesting "Prime Number Races" paper by Granville and Martin.
The question about whether there is a point in the second quadrant is the
same as the question whether we ever have primes of the form 5n+1 more
plentiful than primes of the form 5n+3 and simultaneously primes of the
form 5n+4 more plentiful than primes of the form 5n+2. Note that 1 and 4
are squares (mod 5) and 2 and 3 are nonsquares (mod 5). According to the
paper, this may mean that there will never be points in the second
quadrant. But there are no definitive results.

The paper by Granville and Martin gives reasons why there are relatively
more primes of the forms 5n+2 and 5n+3 than primes of the forms 5n+1 and
5n+4. Call these two kinds of primes N and S (for nonsquare and square
residue). In the O and L graphs, the N and S kinds of primes affect both x
and y coordinates. In the gamma graph, the N primes affect the x
coordinate and the S primes affect the y coordinate. Hence the gamma graph
gives us a picture of the variability of the N primes versus the
variability of the S primes.

I did a check of the primes less than 10^10, and found no points in the
second quadrant. I will let my computer work longer and report the results
to you...

***

W. Edwin Clark wrote:

I did play around with Problem 529 but could not think of a way to attack Q1.

I drew a few plots for moduli other than 5. Actually
any modulus m will do provided that phi(m) = 4 (for 4 directions),
namely any one of 5,8,10,12. But nothing stands out that
I can see.

If the values p mod 5 are randomly distributed
among 1,2,3,4, the points trace out a "random walk" in the plane.

If I understand the attached paper correctly it implies that
a random walk starting at the origin in the plane will in a finite
time cover all the points on any fixed disk centered at the origin.
This would imply that all quadrants will be reached after sufficiently
many steps unless the walk is not random. Perhaps there is
something about the primes mod 5 that is not random?

Anyhow, I think Q1 is probably a very difficult problem. But I have
been wrong before.

(CR note:Q4. Is the red Clark's implication true? All the dark seas in the graphs will ever disappear? Considering the WW graphs below this seems not to happen...)

***

Jan van Delden wrote:

I did do some research of my own. I tried to implement a version of the fractal of Mandelbrot, z[n]=z[n-1]^2+c (mod p), z[0]=x+iy, x and y residues mod p, c=0, where I colored the graph using the length of the orbit. Results are far from spectacular. Lot's of (near) symmetry, as could probably be expected beforehand.

Regarding your Puzzle (529)

Problems in which a "random walk" is implemented are "hard". I think it may be possible to prove that the average position of the point is moving away from both axis. This would entail proving there are in general more primes of form 5n+1 than of the form 5n+3 (likewise 5n+2, 5n+4). If in the long run the number of primes of these forms should be equal however, then the reason the graph looks like it does, because primes of type 5n+1(5n+2) appear in general before 5n+3(5n+4), i.e. there is a headstart away from the axis, which might or might not be compensated in the very long run. Early assumptions regarding the distribution of non-trivial zeroes of the Riemann Zeta function could be proven wrong (after many years), by inspection, i.e. very long calculations. So good luck!

***

Jean Brette wrote:

In the puzzle 529 (primes modulo 5 with 4 directions), one moves on a square lattice

One can also use a triangular lattice, with 6 possible directions at each point :
Take the primes modulo 7 (Pi==1,2,3,4,5,or 6 (mod7) and use the result to
increment along one of these 6 directions.

There are a lot of possible cases... There are 6! = 720 permutations of (1,2,3,4,5,6)
But the order of the group of isometries (rotations/reflexions) of the hexagon (6 triangles) is 12
So the number of cases is 720/12 = 60

***

Seiji Tomita wrote:

I searched for the primes < 10^8 by the range of every 10^7. There was no such prime which enter to the second quadrant.

But,if we don't start from 2, the result becomes a different thing (???)

About Gamma-type, difference of the number of type 5m+3 and 5m+2 is very small than
O-type and L-type (please see attached data). Therefore, the case of Gamma-type is distributed equally on the x coordinate. Is the number of prime type 5m+4 is smaller than the number of type 5m+2 and 5m+3, or by the error of prime distribution, I don't know either. This may be a deep problem.

***

T. D Noe & Wilfred Whiteside solved independently half Q3 on 28-30 March 2010. Both identified exactly the same prime where Q-II is entered:

For the O graph, the first prime in the second quadrant is 716407555481.
Then there are over 50000 primes in the second quadrant [TDN]

"O" entered second quadrant!!! at 716407555481 which is the 27285383212 th prime entry coords are (xp,yp) = (-2470, 1) [WW]

At the same time they have shown positively that this puzzle is a variation of the prime-races problem.

In his own turn, WW produced some more beautiful graphs for both "O" & "L" types counting: 37,607,912,018 primes in the range 1-10^12. Enjoy here a couple of them:

The complete set of graphs are in this presentation that perhaps you may want to download.

***

For sure there must be a prime in 2nd quadrant for the graph type "L" too. Who will bring these news???

***

W.Edwin Clark wrote (April 2010)

Concerning symmetric random walks on the lattice points
Z^d in R^d: [Here symmetric means that the probabilities
of going in any directions from any position are equal.]
Apparently it is known that starting at the origin
all points in Z^d will be reached eventually with probability
1 if d = 1 or 2, but not so if d > 2. See the last
paragraph at

http://mathworld.wolfram.com/RandomWalk2-Dimensional.html

The question is whether or not using prime(i) mod 5
to determine the i-th step for d = 2 or,say, prime(i) mod 4
to determine the i-th step for d = 1, is sufficiently
random to allow all points to be reached.

After looking at the Prime Number Races paper mentioned by
T.D. Noe, I experimented with the following 1-dimensional walk:

Start at 0.
At the i-th step (i = 1,2,3,...)
move 1 unit to the left if prime(i+1) mod 4 = 1,
move 1 unit to the right if prime(i+1) mod 4 = 3.

[Note that using prime(i+1) is to avoid prime(1) = 2.]

Here are some results where n is the number of steps
and [min,max] is the interval covered in those n steps.

n [min,max]
10^1: [0, 2]
10^2: [0, 7]
10^3: [0, 19]
10^4: [-1, 47]
10^5: [-8, 157]
10^6: [-24, 433]
10^7: [-24, 1369]

Note that in the steps from 10^6 to 10^7 the walk
never goes below -24. Yet we know from the 1914 theorem
by Littlewood given on page 2 of the Prime Number Races
paper that eventually all negative numbers will be
reached by this walk. I think it would be hard to
guess that from computer computations alone.

So, I am willing to bet that the entire plane will
eventually be covered by the d = 2 walks described
in Puzzle 529. Collection on such a bet however might
be difficult minus some very clever Littlewood-type
results for the prime races modulo 5. The heat death
of the universe might come before a decision could
be made even for a disk of relatively small radius. :-)

***

WW wrote (April 2010) his finding about entering the L graph to Q-II:

L entered the second quadrant at xp,yp = -3048, 1 for the 182,096,803,634th prime p = 5,140,571,156,101. This was a 5 day run on 12 cores running 9 Miller-Rabin tests on each odd number starting from sieve results up to 1,800,000,000,000. It probably would have been faster to do a segmented seive, but haven't written one and it's hectic at work. Also would have been faster if I had done it right the first try.

Hope this helps verify anyone else's result or that someone can verify this result.

***

Andreas Höglund wrote:

I tested with my own program and confirmed the O-graph entered 2nd quadrant at: k=27,285,383,212  p(k)=716,407,555,481  (x,y)=-2470,1 and L-graph entered the 2nd quadrant at: k=182,096,803,634   p(k)=5,140,571,156,101  (x,y)=-3048,1

***