Prime counting function records

[CRGreathouse]

Originally Posted by ldesnogu

Perhaps someone can add them to OEIS?

The OEIS already has them (except 2^82 which was just posted).

[ldesnogu]

Originally Posted by CRGreathouse

The OEIS already has them (except 2^82 which was just posted).

Oops, I had missed the table was in the links section...

[CRGreathouse]

Originally Posted by ldesnogu

Oops, I had missed the table was in the links section...

Yes, /list (always) just gives the first few lines, the bulk of the sequence is in the b-file.

[D. B. Staple]

Why is the pi(2^m) "only" at 2^81 when pi(10^n) is at 10^26 ~ 2^86.37 ?

Several people have commented on the small stature of 2⁸¹ as compared to 10²⁶.

The reason I hadn't calculated larger powers of two was priority. If I wanted to simultaneously release π(10²⁶), π(2⁸¹), π(2⁸²), π(2⁸³), π(2⁸⁴), π(2⁸⁵), and π(2⁸⁶), then it would have delayed the announcement of π(10²⁶) by several weeks. I estimated the probability of someone else computing π(10²⁶) as perhaps 1% per week, and I viewed this as an unacceptably high risk.

Here are some additional powers of two:
π(2⁸³) = 171136408646923240987028
π(2⁸⁴) = 338124238545210097236684
π(2⁸⁵) = 668150111666935905701562

For esoteric scheduling reasons, π(2⁸⁴) has been computed twice with varying hardware and parameters, but π(2⁸³) and π(2⁸⁵) have only been computed once each. At this point, it is extremely improbable that the redundant calculations will come back inconsistent.

I will also say that I am in the process of calculating π(2⁸⁶), and will post the result here when I have it.

[D. B. Staple]

Also, ldesnogu, you were right on the money: I was happy to have π(2⁸¹) on hand and the others in the works, in case releasing π(10²⁶) started some kind of arms race with one or multiple of Franke, Kleinjung, Büthe and Jost, or perhaps David Platt, or some other dark-horse candidate besides myself. FYI, since releasing the record, the expected but unknown candidate has identified themselves as Kim Walisch. Kim has a very impressive π(x) implementation, and sent me quite a friendly email congratulating me.

Do any of you know Franke, Kleinjung, Büthe, or Jost, or David Platt? I think it is quite interesting that we're now in a situation where two separate lineages of algorithms are very close in capability. Also, if any of them (any of you) are "close" to being able to calculate π(10²⁷), then I suggest that you just tell me that. For my own mental health, I would prefer not to enter into an adversarial relationship with the kind of people that factor RSA-768. Instead, it would be very cool to be able to compute π(10²⁷) in two completely different ways.

[xilman]

Originally Posted by D. B. Staple

Do any of you know Franke, Kleinjung

I've met with Jens and Thorsten on quite a few occasions. Not sure how useful that is, other than providing minor name-dropping rights

PM me if you think it may be useful.

Paul

[R. Gerbicz]

Not mentioned here, but probably you know that there is a fast algorithm to compute the parity of primepi(n), the above results match with these, see http://www.primenumbers.net/Henri/us/ParPius.htm.

[ldesnogu]

Originally Posted by D. B. Staple

FYI, since releasing the record, the expected but unknown candidate has identified themselves as Kim Walisch. Kim has a very impressive π(x) implementation, and sent me quite a friendly email congratulating me.

Google showed this up: kimwalish/primecount. This is a Deléglise-Rivat implementation. I wonder how your implementation (based on Tomás Oliveira e Silva article IIUC) compares.

Do any of you know Franke, Kleinjung, Büthe, or Jost, or David Platt? I think it is quite interesting that we're now in a situation where two separate lineages of algorithms are very close in capability. Also, if any of them (any of you) are "close" to being able to calculate π(10²⁷), then I suggest that you just tell me that. For my own mental health, I would prefer not to enter into an adversarial relationship with the kind of people that factor RSA-768. Instead, it would be very cool to be able to compute π(10²⁷) in two completely different ways.

I think this kind of competition is good because there are basically two kinds of algorithms (I'm in fact surprised the Meissel et al variant is stillcompetitive, I wonder where the crossover is). This could lead both camps to try and improve their algorithms.

[D. B. Staple]

Not mentioned here, but probably you know that there is a fast algorithm to compute the parity of primepi(n), the above results match with these, see http://www.primenumbers.net/Henri/us/ParPius.htm.

Honestly, I remember learning that it is relatively easy to check the parity of π(x), however, I somehow didn't think of this recently. I first worked on π(x) calculations in 2007, then gave up on it until I picked it up again in 2012 and slowly improved the algorithm and implementation until I was able to compute π(10²⁶). So this was forgotten somewhere between 2007 and now. In any case, obviously a very useful fact. Thank you for reminding me of this and for checking the parity of my calculations.

While we're on the subject of triple- and quadruple-checks, it has to be said that the values I posted are in close agreement with the logarithmic integral: approximately half of the digits are identical, as is typical for these large values of x.

[D. B. Staple]

I have calculated one more power of two:
π(2⁸⁶) = 1320486952377516565496055

The double checks for π(2⁸³) and π(2⁸⁵) have now finished and agree with my previously reported values. The double-check for π(2⁸⁶) is underway; I'll post back here when it's complete.

[davar55]

Could you give us an idea of the timings of your runs for 10^n, 2^n, 5^n ?

How high do you intend to go?

Have you considered: 3^n, 7^n, k^n ?