Derbyshire Prime Obsession

John Engelbrecht has an interest in prime numbers. See http://home.earthlink.net/~johnenge/primes640.htm. So I paid attention through the years when I read that the Riemann Hypothesis relates to primes.

But the connection between Riemann's zeta function, ζ(s), and the prime counting function π(x), the number of primes at and below x, is not straightforward, I learn after reading all of Derbyshire's 2003 Prime Obsession, Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. ζ(s) is no easy shortcut to finding prime numbers. The book has a lot of interesting history. I understand enough of the math that I want to make some notes here so I can remember some of it without buying the book.

This is Derbyshire's Expression 21-1, p. 328. He says Riemann had this as his main result in his 1859 paper. Derbyshire says that Riemann was an extraordinary mathematician in the fields of analysis and number theory because of his bold leaps, not because of his logic. This is despite Riemann being a shy person afflicted by tuberculosis and dying at age 40.

The part of the formula marked E above is p. 299, a step function that is a finite sum involving π(x). I think J(x) is where the prime count crops up in this big formula. ζ(s) ends up not predicting “the next prime,” it lets you ratchet up x and you can tell when there is the next prime because J(x) will step up.

G and H are the log integral, which may have no closed form solution. It is integral from 0 to x of 1/log t dt. (In itself, Li(x) is a much better approximation for π(x), better than x/log x. Li(x) is almost always > π(x), but Littlewood found in 1914, p. 235, that Li(x)<π(x) at sufficiently large x, and Bays and Hudson in 2000 found this first happens near 1.39822E316.)

J(x) is on p. 309, Derbyshire's Expression 19-6. Derbyshire calls Expression 19-6 the Golden Key. It relates ζ(s) to an integral of J(x), and allows the tools of calculus to be brought to bear on ζ(s). Derbyshire delights is saying that the Golden Key bridges from number theory to analysis. Derbyshire: “I simply cannot tell you how wonderful” this is. This incredible math is in Riemann's 1859 paper, it isn't that modern math has taken up Riemann's zeta function and run with it to produce the J function.

Li(x) is by far the largest contribution to J(x). The second term, N, corrects by only .04% for π(1,000,000). P and R are tiny corrections, but are needed because all these numbers are decimal numbers, not integers, though they add up very closely to integers when the infinite series are taken far enough.

Derbyshire p. 343 uses Mathematica to demonstrate detail of J(x) for 1,000,000. Only 19 J(x) are needed. At N=1, Li(x) is 78627.54916. Even at N=1, my N marking in the formula above is only -29.74435. P and R are -.69315 and zero. The row total is 78597.11166. The N=2 row has -88.80483, .11044, .34657, and 0. The N=19 row has -.06013, -.02241, .03648, and -.000657. The all-in-all sum is 78498.00000, very close to the number of primes up to 1,000,000 known from the division method or the sieving method, 78498 primes at and below 1,000,000. It seems Riemann did all this for the first three zeros, then he went on to his other pursuits. It is amazing to me that a number so close to an integer could come out of the fantastic, decimal-number formula for J(x).

Derbyshire p. 348 goes on from π(1,000,000) to speculate about π(1.39822E316), the Bays and Hudson number from above. (Note how much larger this number is than the number of electrons in the universe, 1.57×10⁷⁹, the Eddington number.) Derbyshire says only 639 J-functions would be needed! He says the secondary terms, marked N in my function above, would get “very unruly.”

How do the famous zeros of zeta function figure in? There is a neat answer but I can't find it as I review the last chapters of the book. P. 349 hints at it. P. 235 says they are about the error term between π(x) and Li(x). P. 333 finally gets into the zeros but the reader of Derbyshire is distracted by the other neat math that Derbyshire exposits. Another book, 2005 Rockmore Stalking the Riemann Hypothesis, Fig. 13-15 shows various numbers of zeta zeros (5, 50, 500) approximating the step function of the prime distribution π(x) for x up to 200 or so. What I don't know is how many zeros are needed to do the same neat approximation when x=1,000,000. The Rockmore book p. 83 talks about the Fourier transform and how time functions look when adding up enough harmonics to approximate an arbitrary time function, which is what I experimented with when I was a TSTC. (Adding up 30 harmonics gets really close to making triangle and square waves, voices and instruments, etc.) http://empslocal.ex.ac.uk/people/staff/mrwatkin/zeta/encoding1.htm has an animation that shows various numbers of zeta zeros making prime-counting-function approximations. Derbyshire's book doesn't go into the Fourier aspect of approximating π(x), he says many times how he needs to restrict his content to keep the book a reasonable length.

Derbyshire p. 249-251 Theorem 15-2: the Riemann Hypothesis is equivalent to saying that Merten's function, M(k), equals O(k^.5+ε) where ε can shrink arbitrarily small. This is also related to the inverse of ζ(s) = Σ over n of Mobius function μ(n) / n^s. The Möbius function dates from the 1831 paper Über eine besondere Art von Umkehrung der Reihen which is decades before Riemann's 1859 paper.

Another Riemann connection is seen in The Liouville function on Farey fractions and the Riemann hypothesis by P.B. Braun on the Internet. The Liouville function and the Riemann Hypothesis were explored by Landau in his doctoral thesis of 1899.

This is somehow related to Jakob Bernoulli in 1689. (Derbyshire p. 322) Bernoulli said that tossing a coin a large number of times produces a half-and-half result with an average deviation from 50% that is simple: the square root of the number of trials.

The famous Fry's Electronics tech, big-box stores show up in Derbyshire p. 353. The American Institute of Mathematics (AIM) was founded in 1994 as a personal project of math enthusiast John Fry, co-founder of Fry's Electronics, Fry put up $300,000 yearly at the start for AIM. Until 2002, AIM was housed alongside one of the first Fry's stores, in Palo Alto. John and Margaret coincidentally visited this store before they toured the Stanford University campus in 2010, during their month-long California road trip. The store has a Western, and perhaps Hollywood, theme. Fry's carries on the hobbyist supply function that Radio Shack did until 1990. There are fewer, bigger Fry's than there were Radio Shacks, and Fry's has a whole aisle with electronics parts that probably don't sell much but are probably protected by John Fry. My purchases of ferric chloride for etching DIY printed circuit boards tend to be at Fry's because the alternative, from Mouser or Jameco, is becoming more restricted when UPS has to make the delivery, whereas at Fry's the bottles of etchant are right on the shelves. (Ferric chloride is somewhat hazardous. It etches even stainless steel and has so much iron that ingesting it can gives, I suspect, a fatal iron overdose. But it is cheap and much used since 1985 in water treatment plants for drinking water! See http://www.californiawatertechnologies.com/pdf/PotableBulletin.pdf.)

http://primerecords.dk/primegaps/megagap2.htm

January 2004 we (Hans Rosenthal and Jens Kruse Andersen) found the first known prime megagap with size 1001548. January-May 2004 we found a new record prime gap with size 2254930 between two probabilistic primes (prp's) with 86853 digits. Sieving for small factors used the GMP (GNU Multiple Precision) library. Prp testing of the remaining numbers was performed by the program PrimeForm/GW. The prime number theorem says the "typical" gap between primes around p is close to the natural logarithm of p. This is 199984 here, so the gap is 11.28 times larger than typical. No attempt to prove primality has been made since it is far beyond current computers and methods for numbers with no special form. The lower end of the gap is at (or close to) http://primerecords.dk/primegaps/p1.txt

Links about prime gaps:

Thomas R. Nicely's First occurrence prime gaps: http://www.trnicely.net/gaps/gaplist.html

and http://www.trnicely.net/gaps/gaps2.html#HugeGaps

Jens Kruse Andersen's

The Top-20 Prime Gaps: http://primerecords.dk/primegaps/gaps20.htm

First known prime megagap: http://primerecords.dk/primegaps/megagap.htm

New largest known prime gap: http://primerecords.dk/primegaps/megagap3.htm

Jens Kruse Andersen's The Top-20 Prime Gaps: http://primerecords.dk/primegaps/gaps20.htm

Chris Caldwell's Prime Pages, The Gaps Between Primes: http://primes.utm.edu/notes/gaps.html

Eric Weisstein's Mathworld, Prime Gaps: http://mathworld.wolfram.com/PrimeGaps.html

Official announcement of this gap, A prime gap of 2254930: NMBRTHRY archives

Some text files were made by Hans Rosenthal. This page was made by Jens Kruse Andersen and last updated 19 December 2012.

2012 http://primerecords.dk/primegaps/megagap3.htm Michiel Jansen and Jens Kruse Andersen find largest known prime gap, 3,311,852, with identified ends from 226007#/2310-2305218 to 226007#/2310+1006634. The previous record was a gap of 2254930, May 2004. n#, n primorial, is product of all primes ≤ n. The form increased the chance of a large gap compared to random numbers. A C program using the GMP (GNU Multiple Precision) library sieved for factors below 10E12. Prp testing of the 20226 remaining numbers was performed by the program PrimeForm/GW. The prime number theorem says the "typical" gap between primes around p is 225,545 for our 97953-digit numbers, so the gap is 14.68 times larger than typical.

March 2016 After learning that some software offers arbitrary precision, I thought about Python. Python is the natural language for Raspberry Pi. But something steered me to Ruby. I bought The Ruby Way at Barnes and Noble. Ruby has arbitrary precision, "bignum," built in. There seems to be limited typing, and small integers promote to bignum automatically, as needed. And there is Math.sqrt function that works with bignum. This is all needed for trial division on big integers, to prove primality. Also, Ruby can do array inversion, "rational" which is fractions of integers, and complex numbers. Small programs look like Basic, not like the functions you use so much in C.

I did some small Ruby programs to work toward large prime proving. On GRID with Ubuntu, I got Aptana Studio 3 installed, though Git doesn't work. But Aptana doesn't recognize varieties of comments. There is a degree of fatal-error advising. Aptana is my choice for coding Ruby. Though it is interpreted, not compiled, it seems fast. I got Ruby to generate a file of 40,000 prime numbers. For Windows 8.1 on ANODE, I installed Interactive Ruby, irb, which operates in a terminal window (command line) (no IDE). You type in "irb filename.rb" and it runs. I haven't found irb to balk on anything that Aptana works on. For irb, you modify a Ruby program in Notepad, then run it in the terminal.

My Ruby programs can fully prove a prime up to 2E14, using a 9.3MB primes file on ANODE that has all primes up to 15E6. (I wonder how much bigger this primes file could get before reaching memory limit on ANODE.)

A program finds the lowest factor. Another finds gaps. Output is generally long lists into files, often followed by import to spreadsheet and analysis. The gaps program can find all gaps around 2E14, in a range of 400,000 integers, in three hours.

When I did that last one, gaps in a range of 400,000 integers, and put the results into bins (an array) to check abundance vs. gap size, I found that twin primes (gap 2) are not the most abundant. In fact, gaps of 6 are most abundant, and then 12, 18, and the other multiples of 6. There is some information on Internet about that. I wanted to do some work on this on my own. I had a hunch that the pattern I had noticed six years ago with Basic on IBM Thinkpad, using graphics to portray how soon integers fail the trial division method, might yield info about the gaps of 6. The pattern seemed to repeat every 50 integers or so, maybe it repeats at 2*3*5 = 30. For the present Ruby problem, I decided to organize all integers up to about 1000, using a display based on 210, which is 2*3*5*7. This is really base 210, and I later found an Internet article that said 210 is indeed a good number for trial division.

The photo shows the tops of the lists of integers. There are indeed patterns to this base-210 display. Little red penciled "p" marks primes. "A" notes the gap size. The dark E bands mark all multiples of 7. Of course, the primes are never on a multiple of 7. It is interesting that many of the primes are on horizontal lines (green, like at "C") right across six columns, which makes them differ from each other by 210. (But some of the green lines terminate at composite integers, they don't go all the way across. Example at "D." For example, 841 isn't a prime, it is 29 squared.) It is like the multiples of 7 channel a lot of the primes.

In the display, "sporadic" missing primes, those not among brothers on a horizontal line, are sometimes multiples of the primes beyond 7, such as 11, 13, and 17. More frequently, they are multiples of 2, 3, and 5.

I had supposed that the many gaps of 6, 12, and 18 would show up somehow in this display. It isn't real obvious, though. Notice at "B" that gaps of 4 and 2 in the fifth column sort of merge to give a 6 in sixth column. Also in fifth column, a 4 and 14 sort of merge to make an 18. I think the "merging" is real, and only appears because of the base-210 display. Note the gaps of 2, 4, and 6 that range across several columns. I notice no instances of gap-of-4 stacked on gap-of-4, but there are many gap-of-2 stacked on gap-of-4. Maybe 2+4 stacks between multiples of 7. Between primes 647 and 653, the gap of six seems to decompose to 2 and 4 in the next column, since 859 is a prime. I had thought that "stacked" gaps of 6 might merge to make 12s and 18s. At 472, not shown in the photo, that does happen. I had thought that many 12s might come from the abundance of 6s. The photo doesn't have enough examples to draw conclusions. All in all, this is interesting, but the Internet has more satisfying reasons. (Satisfying to those who understand it!) Some web sites are cited in sheet 2 or 3 of prime gaps around 2e14 range of 120000 integers.ods on ANODE.

After seeing patterns in the photo above, which is integers starting from 1 and going above 1094, I wondered if I would learn anything new by doing the same display starting at some high integer. I chose a start of 210^5 * 510 +1 which is 208289151000001. This comes in slightly below (in range) of the primes file I have on ANODE for use with irb. (Primes file top prime squared > 208289151000001.) I got it printed and taped together just like the low-range photo above. There are so few primes at the high range that the gaps are large, and I don't see the merging and splitting of gaps like I saw at the low range. But there is still a strong trend for primes to line up horizontally, there are many gaps that are multiples of 6, and "missing" primes have been divided out by 11, 13, 17, etc. or by large factors. This suggests that a Ruby program to simulate the display of primes at base 2*3*5*7*11*13*17 = 510510 would be a neat thing, there would be more lining up of primes, but maybe not horizontally--primes might line up at angles. (This is actually sieving.) So instead of working with printed numbers, it would be better to display primes as dots, that would make visualizing diagonal lines easier. It would also be interesting to arrange all positive integers in a spiral and show how sieving knocks out composites. The spiral display would furl and unfurl to let a sieve be in a straight line until the next sieve is done.

#primesto100vb.rb get around 1000 primes into a file on disk, starting 2 3 5 7 11 and use the file to do screening for primes of some bignum ranges, where candidates go to disk. Finish the bignum ranges by trial division.

m = 208289151000001 #m is a candidate integer 208289151000001 starts a run based on base 210

p = 0 #p is the count of primes

oldprime=0

primeslist = File.new("primesMarch122016.txt", "w")

while p < 200 do #at p<4000, GRID in Ubuntu with Aptana takes 2 seconds, puts m to console and to drive

# at p<4000, the file on drive is only 22100 bytes.

# at p<40000, it takes GRID 46s gets to m=479939 file size 262.7kB

m += 2

n = 2 #n scans up through sqrt of m

maybeprime = true

while ((n < Math.sqrt(m) + 1) && maybeprime ) do

if m % n == 0 then maybeprime = false end

n += 1

end

if maybeprime then

(puts m

primeslist.puts m

primeslist.puts m-oldprime

p += 1 ; oldprime = m )

end

end

primeslist.close # routine skips 2 at the beginning, add that manually

# Ruby program primegapsv3.rb on GRID, now on ANODE for irb Set up array to record how many of each size of gap there is. Note: gaps are all even numbers.

# The ver 1 of the program just recorded to a long text file each gap as it occurred. copied from candidates.rb John Engelbrecht March 9 2016 GRID computer, Ubuntu side

# With success, especially on ANODE using irb, in seeing primes in integer ranges of 10,000 up to 1E14 or so,

# look at gaps, make a graph of gap size vs. abundance in the 1E14 area. Get the program working in Aptana Studio 3 on GRID, then let it run at higher range on ANODE in irb.

Run this program within the sqrt range so the primes are fully trial divided.

# ver 3 is to get a table of integers (every integer, even evens) with gaps shown, to evaluate base 210 patterns on ANODE

lowprimesarray = IO.readlines("primesMarch2016million.txt") #all primes up to abt 15e6

# this is "slurping", is OK if enough memory but yields strings

puts "Primes to do trial divisions by are the first "

puts lowprimesarray.size; puts "---Start---" ; s = 0 ; ar = Array.new(500) ; agaps = Array.new(500)

500.times do

ar[s] = 0 ; agaps[s] = 0 ; s += 1

end

startint = 208289151000001 ; times_thru = 4000 # 210**5 * 510 +1

# with times_thru = 1000, checking 2000 integers, takes GRID 16sec starting from 232000000001

# 16sec 200888000111000222333444555000101

# 19sec 200888000111000222000333000111000222333444555000101

# in 200,000 range of integers around 2E14, gaps are as large as 258.

p=1 ; m = startint ; toofar = lowprimesarray.size; remember_old_prime =0 # a dummy number for 1st time thru

k = 1

while p <= times_thru do

maybeprime = true

j = -1

while maybeprime && j<toofar-1 do

j += 1 ; q = lowprimesarray[j].to_i

if m % q == 0 then maybeprime = false end # end of the if

end # end of the inner while

if maybeprime then

(t = m - remember_old_prime # t is the size of the gap

if t < 3000 then # discard the dummy at the first time through

(puts p

ar[k] = m ; agaps[k] = t ; k += 1 )

end

remember_old_prime = m )

end # end of if

m += 1 ; p += 1

end # end of the outer while

intfile = File.new("integers.txt","w")

gapsfile = File.new("gaps.txt","w")

s1 = 1

499.times do

intfile.puts ar[s1] ; gapsfile.puts agaps[s1] ; s1 += 1

end

intfile.close ; gapsfile.close

A step ahead with Ruby March 29 2016

#file primesto10e7ve.rb on GRID Ruby JE March 29 2016 Ver e goes ahead to take advantage of primes file primesMarch2016_40001qty.txt

In range around 225,225,000,000, 1.5million integers are checked for primeness in 3 hrs, much slower than in the 20million range, where 20million

were checked in .3hr, 145 times faster. Sieving, I think, is not so important when it only sieves up to 13. If you just use trial divisions

with no pre-sieving, it takes just a few divisions to cover the divisions up to 13, then for many integers you have to continue trial divisions

up into the millions, which takes a long time. So I got the program working but it has little advantage when you are finding primes in the 2E11 area. Still, the idea of

grouping integers in columns of 30030, to align factoring of 2, 3, 5, 7, 11, and 13, is a neat idea, shows a considerable structure to primes, and

it is easy to start that near any arbitrary integer like 2E11. Sieving by 2-13 is just like the sieving by 2-7 that is the yellow-tone photo

near the top of this web page, where 2*3*5*7 = 210. Note: 30030 = 2*3*5*7*11*13 newprimes = Array.new primeslist = File.new("primeOverHalfMil.txt", "w") i = 1 ; co1 = Array.new # reference array co1 stays static 30030.times {co1[i] = 0; i += 1 } # prefill with 0 ar_p_to13 = [2,3,5,7,11,13] #primes to sieve with This yellow section is referred to twice below * ar_p_to13.each do |k| ii=k (30030/k).times do # note the paren around 30030/k is needed, 30030/k.times does it wrong co1[ii] = 1 ; ii += k endend # the reference array co1 has 1 at composite numbers, 0 where there are not factors of 2-13, other than index 0-13

This is sieved up through 13. Very neat, very compact.# ---------------- the only coupling from above to below is the co1 array------------------ lowprimesarray = IO.readlines("primesMarch2016_40001qty.txt") #all primes up to 479939, qty 40,001 # this is "slurping",

is OK if enough memory but yields strings multiple_of_30030 = 450450/30030 # an initial value of 15, starting int is 450450while multiple_of_30030 <= 19_999_980/30030 # 666 ending int is 19_999_980 co1index = 0 ; newprimes.clear while co1index <= (30030 - 2) co1index += 1 until co1[co1index] == 0 do co1index += 1 ; if co1index >= 30030 then break end end # this gets to the next m that

doesn't have factors from 2 to 13, as follows on next line m = multiple_of_30030 * 30030 + co1index nohigher = 1.0 + Math.sqrt(m.to_f) # calculate this outside the next loop so it only has to be calculated once lowparlocation = 6 # location of 17 in the prime array primeflag = 1 ; primedivisor = lowprimesarray[lowparlocation].to_i # divisor starts at 17 because sieving has already happened at 13 and below while ((primedivisor.to_f <= nohigher) && (primeflag == 1)) if m % primedivisor == 0 then primeflag = 0 end lowparlocation += 1; primedivisor = lowprimesarray[lowparlocation].to_i # taking advantage of primes file for primedivisor, it takes 1.5s on GRID to go through 30030 integers, checking for primality,

whereas with primedivisor +=2 it took 5s. This is in the area of integers around 10 million end # end of proving one prime number, or finding it is composite if primeflag == 1 then newprimes.push m end end # of checking out 30030 integers newprimes.each { |x| primeslist.puts x } co1index = 0 ; multiple_of_30030 += 1 end # of the requested range of integers primeslist.close

some of the output from version F 225226531141 225226531151 225226531261 225226531289 225226531307 225226531319 225226531339 225226531351 225226531403 225226531417 225226531427 225226531429 225226531469

*The delightful little yellow section above came about from the ponderous section below when I realized it could be condensed.

#file on GRID primesto10e7vc.rb #Use this Ruby program on ANODE to get around 10million primes into files on disk. # Do sieving of 2,3,5,7 using this fact: any integer multiple of 210 that is added to composites from 2 to 209 # is a composite number. Above 2,3,5,7, use trial divisions. # Sieving of 2,3,5,7 can use a reference array co that has ones where composites are, otherwise 0, # co index runs from 1 to 210 and co[0] doesn't matter. co = Array.new # reference array co stays static co1 = Array.new i = 1 210.times do co[i] = 0; co1[i] = 0; i += 1 # prefill with 0 end i = 2 #begin ponderous section 105.times do co[i]=1 ; i +=2 # this takes care of evens end i = 3 70.times do co[i]=1; i += 3 end # You can't miss each loop having a constant related to the current prime number, here 3, 210/3, and +=3 i = 5 42.times do co[i] = 1 ; i += 5 end i = 7 30.times do co[i] = 1 ; i += 7 end #end ponderous section # Now, try doing the above with .each in one loop, and if that works then extend it to sieving to 13. ar_p_to7 = [2,3,5,7] #primes ar_p_to7.each do |k| ii=k (210/k).times do # note the paren around 210/k is needed, 210/k.times does it wrong co1[ii] = 1 ii += k end end j = 1 211.times do print j; print " "; print co[j] ; print " "; print co1[j] ; print " ";puts co[j] == co1[j] ; j += 1 # check the sieve array end

Some thinking about the little yellow section * (2 or 3 screens above) that generates the co1 array, marking co1[]

with the sieve, makes me wonder if a marked co1[] array has much wider usage, like to find gaps or primes at large

integers. This would be done by letting the sieve run, not for 210.times or 30030.times, but 1_000_000_000.times.

I don't think that would work, because the co1 array uses up memory.

#file primesto10e7vm.rb compare two runs of ver j which generates primes from

# 200M to 500M on ANODE, which has a DRAM problem. If the DRAM problem is causing error in the output file,

# running the prime generator twice should cause the DRAM problem to show up as differences between the two

# output files. When I did a 200Million to 500Million integers run, the output file of 164MB is too big to

# open in Notepad or OpenOffice Write. Use Ver k to split the 164MB file of 200M-500M

# down to 100M ranges, ready to read in the pairs and do the compares in version m.

# These are the 100M ranges prime200029831to299999977 prime300000007to399999959 prime400000009to500322743

armain = IO.readlines("prime200029831to299999977.txt") # this is "slurping", is OK if enough memory but yields strings

archeck = IO.readlines("prime200029831to299999977check.txt")

i=0 ;

print armain[0];puts archeck[0]

while armain[i] == archeck[i] # if the loop completes to just past the 299999957 entry, the two files are equal

if ((i<20) || (i % 100000 == 0) ) then print i;print " ";print armain[i].to_i;print " " end # remember, each IF needs an END

if armain[i].to_i>299999957 then break end # I don't yet know how to detect EOF, so just look for next-to-last entry

i += 1

end

puts "done"; print i;print " ";print armain[i].to_i;print " ";print archeck[i];puts

Version M Ruby program detected no DRAM error in the range of primes from 200029831 to 299999977.