PRP for F33?

[LaurV]

Originally Posted by retina

The main difference between F33 and pi is that

me, me, pick me, pick me!
...one is integer and the other is irrational?...

[JeppeSN]

And the difference between F0 and pi is negative. /JeppeSN

[kriesel]

Originally Posted by JeppeSN

MM82589933 = 2^(2^82589933-1) - 1 is a prime.

Now please prove me wrong - any prime factor of that number would be the largest prime ever found.

/JeppeSN

Sure, write me some error free code that runs in O(ln(n)) or faster and I'll try it.
The odds of n being prime ~1/ln(n), are very much against your assertion of primality for MMp51*.

Now could we all please return to on-topic for the thread? Perhaps some comments on posts 12 or 13?

I read in https://www.mersenneforum.org/showpo...1&postcount=64 that Ernst is making progress in coding P-1 factoring in Mlucas v20.

[bbb120]

Originally Posted by bsquared

I didn't know much about the algorithm either, really, but after looking at it for a few minutes I'll illustrate how I think it works. I'm going by the recursive description here:
numberworld.org/y-cruncher/internals/binary-splitting-library.html#pi_chudnovsky

Say you want to compute pi to 1000 decimal places. With ~15 digits per term, you need about 67 terms. So n=67 and we therefore need to compute P(0,67) and Q(0,67), after which we can get pi by doing a few more multiplications/divisions/additions by constants.

I am not going to spell out every single recursive step, but lets look at just the P term, starting with P(0,67):

Need P(0,67), Q(0,67)
Pick m=33
P(0,67)=P(0,33)Q(33,67)+P(33,67)R(0,33)
Q(0,67)=Q(0,33)Q(33,67)
R(0,67)=R(0,33)R(33,67)

Need P(0,33)
Pick m=16
P(0,33)=P(0,16)Q(16,33)+P(16,33)R(0,16)

Need P(0,16)
Pick m=8
P(0,16)=P(0,8)Q(8,16)+P(8,16)R(0,8)

Need P(0,8)
Pick m=4
P(0,8)=P(0,4)Q(4,8)+P(4,8)R(0,4)

Need P(0,4)
Pick m=2
P(0,4)=P(0,2)Q(2,4)+P(2,4)R(0,2)

Need P(0,2)
Pick m=1
P(0,2)=P(0,1)Q(1,2)+P(1,2)R(0,1)

Now we have a bunch of terms of the form P(b-1,b), Q(b-1,b), and R(b-1,1), for which we have explicit formulas. Following the recursion back upward, each multiplication is now of two (large) numbers of approximately equal size, so we can take advantage of asymptotically fast multipliers.

The number of steps in the recursion is logarithmic in 'n'. So, you can see now, hopefully, that we are not really iterating anything. We are recursively multiplying numbers of equal size, using fast multiplication algorithms. Hence arriving at O(n (log n)^3).

Fermat tests *do* have to iterate, on each binary bit of the exponent. Each iteration also uses fast multiplication algorithms, but we have way more terms to iterate over than we would have steps in the recursive computation of pi.

I encourage you to go through all of the recursive steps in this process. Getting your hands dirty like this is a great way to learn something. For a small enough target (pi to 1000 digits is probably doable), you can do all of the computing with mathematica and track the intermediate products in a text file.

http://www.numberworld.org/y-crunche...#pi_chudnovsky
maybe this is answer

[jyb]

Originally Posted by bbb120

F33=2^(2^33)+1=2^8589934592+1
(F33-1)/2=2^4294967296
3^((F33-1)/2)=-1(mod F33) <=> F33 is a prime number
it needs 4294967296 iterations

You may want to check your math again. How many iterations are required?

[Happy5214]

Originally Posted by jyb

You may want to check your math again. How many iterations are required?

Yeah, that's off slightly. (Several orders of magnitude, in fact.) It's more like 2^(2^33-1) iterations.

[LaurV]

Originally Posted by bbb120

F33=2^(2^33)+1=2^8589934592+1
(F33-1)/2=2^4294967296

Yep, in his mind, 2⁹/2 is not 2⁸, but it is 2^4.5

[sweety439]

I think that F33 may be prime!!!

Since (see http://www.prothsearch.com/fermat.html) F20 was proven composite in 1987, and F24 was proven composite in 1999, and the largest known prime number in the electronic era has grown roughly as a double exponential function of the year, and indeed the Fermat numbers have double exponential function behavior, thus, the Fermat number Fn may be a linear function of the year (if the Fn is composite and with no small prime factor (like F20, F24, and F33), or if the Fn is prime, which year the primality of Fn will be known):

F20 = 1987 **
F21 = 1990
F22 = 1993
F23 = 1996
F24 = 1999 **
F25 = 2002
F26 = 2005
F27 = 2008
F28 = 2011
F29 = 2014
F30 = 2017
F31 = 2020
F32 = 2023
F33 = 2026

See the table, F33 corresponding to the year 2026, and 11/13/2026 is the technological singularity, predicted by Heinz von Foerster, by the formula, in 2026 the world population will be infinity.

[Viliam Furik]

Originally Posted by sweety439

I think that F33 may be prime!!!

I hope that was a joke.

[mathwiz]

Originally Posted by sweety439

I think that F33 may be prime!!!

Well, I mean, it *may* be prime. And it may not be prime. The latter is just way, way, way, way, WAY more likely....

[Dr Sardonicus]

Originally Posted by sweety439

<snip>
by the formula, in 2026 the world population will be infinity.

That's what I would call a good reason to question the formula's validity.

I am reminded of a (then) fellow grad student who told me of a problem his actuarial science prof had assigned, as an exercise in showing the unsustainability of exponential growth: Given the current population, and assuming the population grows at 1% per year, (unrealistically assuming sufficient inflow of resources, and making some assumption about how densely human beings can be packed in) calculate how long it would be until the human population were literally expanding at the speed of light.

Meanwhile, back in the real world,as documented here, a factor for F₁₀₃ has been found:

103 7595155767819149 105 31 Dec 2020 P. Strasser & Woltman