Assorted formulas for exponents of Mersenne primes

[Batalov]

Originally Posted by mart_r

See, some years ago I found a formula that seemed to produce ever new primes:
f(n)=41+n*(n-1)
f(1)=41 is prime
f(2)=43 is prime
f(3)=47 is prime
f(4)=53 is prime
...
f(40)=1601 is prime

I thought Euler found it, too.

[science_man_88]

Originally Posted by Batalov

I thought Euler found it, too.

that and number freak has a different f(40) of 1681, if I read it correctly.

[ATH]

Unless there is big breakthrough in algorithm or in quantum computing, I doubt MM127 will "ever" be proven prime, or at least within several hundreds of years.

But it's hard to predict the future, and actually I'd like to be proven wrong.

[CRGreathouse]

Originally Posted by Uncwilly

Doing some rough calculations, here is what I came up with and put in Mersennewiki.org

I'm willing to take 161 million times the age of the Universe to find out, and dedicating the top 250 supercomputers to it isn't a problem. But can we actually run the task in parallel? A trillion times the age of the Universe is right out.

[ewmayer]

Originally Posted by ATH

Unless there is big breakthrough in algorithm or in quantum computing, I doubt MM127 will "ever" be proven prime, or at least within several hundreds of years.

There was a thread along these lines a few years ago...I argued there that based on some plausible "maximum information storage density" heuristics (a kind of quantum-informatic "how many qubits can dance on the head of a pin" deal) the smallest volume of particles needed to simply store M127 bits leads to a sufficiently large minimum per-iteration time for the LL test that it would take far longer than the current lifetime of our universe to complete such a test.

So the only way to resolve the issue seems to be to find an explicit factor.

But it's hard to predict the future, and actually I'd like to be proven wrong.

"It's hard to make predictions, especially about the future." -- Yogi Berra

[CRGreathouse]

Originally Posted by ewmayer

So the only way to resolve the issue seems to be to find an explicit factor.

Or find a better algorithm than LL -- not likely, but then neither is finding an explicit factor (< 50% chance to find one with k under 200 bits).

Do we even have a nontrivial lower bound on the time needed for a primality test? AFAIK all we know is that it must take at least linear time in the worst case...

[Lee Yiyuan]

Originally Posted by CRGreathouse

Or find a better algorithm than LL -- not likely, but then neither is finding an explicit factor (< 50% chance to find one with k under 200 bits).

Do we even have a nontrivial lower bound on the time needed for a primality test? AFAIK all we know is that it must take at least linear time in the worst case...

Or prove that the generating function for Catalan-Mersenne numbers will always produce primes.

[CRGreathouse]

Originally Posted by Lee Yiyuan

Or prove that the generating function for Catalan-Mersenne numbers will always produce primes.

Highly unlikely.

[10metreh]

Originally Posted by science_man_88

that and number freak has a different f(40) of 1681, if I read it correctly.

Think before you question. Look more closely at the formulae for the sequences.

[science_man_88]

Originally Posted by 10metreh

Think before you question. Look more closely at the formulae for the sequences.

according to number freak the formula is f(x)=x^2+x+41 so f(40)= 40^2+40+41 = 1600 + 81 = 1681.

[science_man_88]

things I've PM'd that that are supposedly useless for speeding up LL.

Originally Posted by science_man_88

the numbers the lucas lehmer test uses starting at 4 can be expressed as a addition and subtraction of powers of 2 is there a way anyone could use this to help speed it up ? I'm guessing this has already been picked up on if it's true ? anyways I'm sorry if I bothered you.

Originally Posted by science_man_88

I've recently realized that all members of A003010 after 4 have a sumdigits(x)==5 could this be used to precheck if LL is worth doing because if we allow 9 and 0 to be the same we can use numbers under n in each step and check if the last result is 9 if so then we can check if the full result is a 0, but if it's not 9 or 0 ( remember both used the same) then we don't have to bother it can't be a 0 result and we don't have to do full on LL however unless we can tell when it transfers from the sequence to it's own sequence ( in other words the members of the original sequence is greater than 2^p-1) this may still need numbers that big. okay maybe not a great idea.

this is for the most part what's important to show my ideas I was also thinking if p doesn't work try a possible factor and it may speed it up from 2^p-1, though it appears to loop at last check.