Catalan sequence (is C5 prime?)

[Orgasmic Troll]

is anybody putting any work in on this? ran across it on the Prime Pages

sure, the exponent is 170141183460469231731687303715884105727, but it seems like if anybody was going to bang away at it, it would be someone in here.[/url]

[jocelynl]

Hi Travist,

Look further on the prime page you'll see the link to http://www.ltkz.demon.co.uk/ar2/mm61.htm Tony Forbes search for factors

Joss[/url]

[nomadicus]

This is M170141183460469231731687303715884105727.

*If* prime95 could handle a number that large (C5 is much, much larger then prime95's maximum (somewhere around M77000000)), I suspect with current technology it would take a century or two to compute (or is that a millenium or two?); that is, of course, if the current technology could even begin to handle a number this large.

[Orgasmic Troll]

just for clarification, I didn't expect anyone to be trying to prove primality, just looking for factors. Thanks for the link, jocylenl

[Citrix]

What number will be MM127 expected to be for example the MP 40 is currently being searched.

Citrix

[cheesehead]

Originally posted by nomadicus
This is M170141183460469231731687303715884105727.

*If* prime95 could handle a number that large (C5 is much, much larger then prime95's maximum (somewhere around M77000000)), I suspect with current technology it would take a century or two to compute (or is that a millenium or two?);

Oh, much, much, much, much longer than a millenium!

The exponent is more than 2*10^30 times Prime95's current maximum exponent (79,300,000).

2*10^30 > 2^100.

Doubling the exponent multiplies the execution time by more than a factor of 2, so multiplying the exponent by 2^100 raises the time by more than 2^100. We're talking about longer than nonillions (1 nonillion = 1 trillion * 1 billion * 1 billion) of years.

that is, of course, if the current technology could even begin to handle a number this large.

Order of 10^38 bits or so.

Giga- = 10^9
Tera- = 10^12
Peta- = 10^15
Exa- = 10^18
Zetta- = 10^21
Yotta- = 10^24

Need those petayottabyte memory sticks.

[cheesehead]

(Curses on the %$$& 5-minute editing deadline!

Yeah, I know it's for the greater good.)

My nonillion-year estimate was based on just the ratio of times for single L-L iterations. There's an additional factor of 2*10^30 on the number of iterations required. So it's 2*10^30 nonillion years.

But ... if there's a "Moore's Law"yerish doubling of speeds every 18 months ...

Oh, someone _else_ figure that one!

[Maybeso]

Well, my lunch napkin is too small for working that one out.

But we can say that Moore's "Law" implies it is a waste of time to start now, since using next years machine will save more than a year of time ...

That argument does make sense in this case, because passing this problem from today's machine to next years would be fairly difficult. Switching machines in the middle of an LL this big is impossible, for factoring it would be merely "challenging".

[ixfd64]

And by several decades, we'll probably have quantum computers that can factor MM127 in less than a second...

[Orgasmic Troll]

My knowledge of quantum computers is pretty small, but does the computation time increase for factoring larger numbers?

[xilman]

Originally posted by TravisT
My knowledge of quantum computers is pretty small, but does the computation time increase for factoring larger numbers?

My knowledge is far from encyclopaedic, but I do know the time on a QC grows polynomially with the number of bits in the number to be factored. The best algorithms we know for factoring on conventional computers are superpolynomial, though subexponential.

I think it is likely to be a long time before we can factor general integers the size of C5. As far as I am aware, the record still stands at 15 for a factorization by a QC.

Paul