What a difference 30 years makes!
 

Here's an interesting quote from "What Drives An Aliquot Sequence?", from Mathematics of Computation, 1975. This is regarding the 276 sequence, and the state-of-the-art knowledge back then:[quote]Lehmer has computed a further 200 terms which show an erratic upward tendency. The extent of our present knowledge is[indent]107100047962427456048833497403019424 = 276:433 = [tex]2^53*199*c[/tex][/indent]where [i][b]c[/b][/i] is a 31-digit composite with no small factors.[/quote]Kinda unbelievable when you think about it....

BTW, the c31 factors as 1171449981591251 * 4785657413964331.

[quote=schickel;167217]BTW, the c311 factors as 1171449981591251 * 4785657413964331.[/quote]

When was it a C311? (I wonder whether we'll be onto C311s in 30 years' time...)

BTW, how long did it take to factor the C31, and what method was used?

[SIZE=1]{Heh, no "beat you to the edit" this time!}[/SIZE]

I don't know what method schickle used, but it took me less than a tenth of a second, not counting the time it took to type in the command:

[code]echo 107100047962427456048833497403019424 | ecm -t 200 -c 10 7000
GMP-ECM 6.2 [powered by GMP 4.2.2] [ECM]
Input number is 107100047962427456048833497403019424 (36 digits)
********** Factor found trial div: 2
Found proven prime factor of 1 digits: 2^5
********** Factor found trial div: 3
Found proven prime factor of 1 digits: 3
********** Factor found trial div: 199
Found proven prime factor of 3 digits: 199
Using B1=7000, B2=754806, polynomial x^1, sigma=4282110816
Step 1 took 44ms
Step 2 took 40ms
********** Factor found in step 2: 1171449981591251
Found probable prime factor of 16 digits: 1171449981591251
Probable prime cofactor 4785657413964331 has 16 digits

real 0m0.098s
user 0m0.096s
sys 0m0.004s[/code]

[quote=Mr. P-1;167228]I don't know what method schickle used, but it took me less than a tenth of a second, not counting the time it took to type in the command:

[code]echo 107100047962427456048833497403019424 | ecm -t 200 -c 10 7000
GMP-ECM 6.2 [powered by GMP 4.2.2] [ECM]
Input number is 107100047962427456048833497403019424 (36 digits)
********** Factor found trial div: 2
Found proven prime factor of 1 digits: 2^5
********** Factor found trial div: 3
Found proven prime factor of 1 digits: 3
********** Factor found trial div: 199
Found proven prime factor of 3 digits: 199
Using B1=7000, B2=754806, polynomial x^1, sigma=4282110816
Step 1 took 44ms
Step 2 took 40ms
********** Factor found in step 2: 1171449981591251
Found probable prime factor of 16 digits: 1171449981591251
Probable prime cofactor 4785657413964331 has 16 digits

real 0m0.098s
user 0m0.096s
sys 0m0.004s[/code][/quote]

I mean, what method was originally used?

[QUOTE=Mr. P-1;167228]I don't know what method schickle used, but it took me less than a tenth of a second, not counting the time it took to type in the command:[/QUOTE]Read a little closer.....that was [b]quoted from an article from 1975[/b].

I was comparing "state of the art" then and now......

[QUOTE=10metreh;167229]I mean, what method was originally used?[/QUOTE]I don't know. It was factored some time after the original 1975 article.....I guess someone could contact Lehmer and see if he remembers factoring it way back then.

[quote=schickel;167231]I don't know. It was factored some time after the original 1975 article.....I guess someone could contact Lehmer and see if he remembers factoring it way back then.[/quote]

I thought he had died back in '91 or some time around then.

[QUOTE=10metreh;167232]I thought he had died back in '91 or some time around then.[/QUOTE]
OK, we could call Jennifer Love Hewitt, then.....:razz:

[QUOTE=schickel;167230]Read a little closer.....that was [b]quoted from an article from 1975[/b].

I was comparing "state of the art" then and now......[/QUOTE]

I understood the point of your post. I took 10metreh's question to mean how long did it take [i]you[/i] to factorize using today's technology. (I assumed that you had, since you posted the factors.)

The point being that what was infeasible in 1975 took less than a tenth of a second in 2009 on a commodity processor which was nowhere near the fastest available even when I bought it three years ago.

I wonder how much of the advance in 30 years has been due to faster hardware, and how much due to better algorithms.

[QUOTE=Mr. P-1;167249]I wonder how much of the advance in 30 years has been due to faster hardware, and how much due to better algorithms.[/QUOTE]

I doubt whether faster hardware could've contributed to more than a factor of 1e6 in performance gain in 30 years.

So, my vote is for the bulk of the improvement due to faster algos.

[quote=Mr. P-1;167249]I understood the point of your post. I took 10metreh's question to mean how long did it take [I]you[/I] to factorize using today's technology. (I assumed that you had, since you posted the factors.)

The point being that what was infeasible in 1975 took less than a tenth of a second in 2009 on a commodity processor which was nowhere near the fastest available even when I bought it three years ago.

I wonder how much of the advance in 30 years has been due to faster hardware, and how much due to better algorithms.[/quote]

Well, [url=http://en.wikipedia.org/wiki/Pollard's_rho_algorithm]Pollard's Rho[/url] algorithm was available at some point in 1975, and with a commodity processor I can factor the C31 in about 20 seconds using Rho with 10e6 iterations on the poly x^2 + 1. Admittedly this is using Brent's faster variation, which wasn't available until 1980. If "infeasible" is defined as 1 week, then this is at least 30 thousand times faster hardware.

With QS it factors in 3 hundredths of a second on the same processor, so algorithms contribute another ~700x speed improvement.