Prime factors of number near googolplexplex
Dario Alpern
In (probably) the first page on Internet about numbers near
googolplexplex, that is, 10^googolplex, I put the prime factors I
found using trial division of numbers in the range googolplexplex-999
to googolplexplex+999.
The URL is: http://www.alpertron.com.ar/GOOGOLP.HTM
Best regards,
Dario Alejandro Alpern
Buenos Aires - Argentina
http://www.alpertron.com.ar/ENGLISH.HTM
fishfry
alpe...@hotmail.com (Dario Alpern) wrote:
Very impressive. How'd you do that? I would think that factoring numbers
that large would not be possible on any computing equipment or software
available today.
Theorist
factor.
Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com
Virgil
Alex...@hotmail-dot-com.no-spam.invalid (Theorist) wrote:
> He didn't factor those numbers, just guessed some of their small
> factor.
>
Well, he might have factored googleplexplex itself, since it factors
into the form 2^n*5^n, and all he would have to do is work out the value
of n.
Tim Smith
> He didn't factor those numbers, just guessed some of their small
> factor.
I'm curious how one guesses small factors like 3898556974549, 2000665038247,
1301687275127, 2017970156617, or 2184279173669?
--
--Tim Smith
Denis Feldmann
The trick is to find the modular residue of 10^(10^(10^100)) modulo n, for n
"small", which is not so hard (as, say, here it is modulo 7 : (10^a) mod
7=[1,3,2,6,4,5,1,...] so you need to find a mod 6. But (10^b) mod
6=[1,4,4,4....], so your answer is 4. For higher n, you may have to use the
method 3 or 4 times, though...)
Phil Carmody
Dario's 'small' factors (<10^14) were found by sieving.
Calculate r = (10^10^100 % p) ?
p is a factor of 10^10^100-r, obviously.
If r is >-1000 and <1000, then Dario recorded that fact.
The larger factors of numbers of the form 10^10^100+/-10^x for
various small x were found usinga similar process, but were
restricted to searches with p having the form k*c+1 where the
multiplicative constant c is one of the factors of (10^100-x)
Some such c are pretty large, and hence >100 digit factors
were found by David Broadhurst, myself and others. There are
still plenty of factors out there to be found if anyone's
interested in looking for them
Phil
--
1st bug in MS win2k source code found after 20 minutes: scanline.cpp
2nd and 3rd bug found after 10 more minutes: gethost.c
Both non-exploitable. (The 2nd/3rd ones might be, depending on the CRTL)
Dario Alpern
Yes, there is a trick using the Fermat theorem.
I have to compute 10^(10^(10^100)) modulo p for p prime.
When p is 2 or 5 the solution is trivial (zero).
When p is not 2 or 5 we know that 10^E = 10^(E mod(p-1)) (mod p)
So I have to compute F = E mod (p-1) = 10^10^100 mod (p-1) which I do
in my program using 400 modular multiplications. Then I compute 10^F
(mod p) very easily.
The primes are found easily by using a sieve.
Dario Alpern
> Tim Smith <reply_i...@mouse-potato.com> writes:
>
> > In article <4041d8c6$1...@Usenet.com>, Theorist wrote:
> > > He didn't factor those numbers, just guessed some of their small
> > > factor.
> >
> > I'm curious how one guesses small factors like 3898556974549, 2000665038247,
> > 1301687275127, 2017970156617, or 2184279173669?
>
> Dario's 'small' factors (<10^14) were found by sieving.
> Calculate r = (10^10^100 % p) ?
> p is a factor of 10^10^100-r, obviously.
> If r is >-1000 and <1000, then Dario recorded that fact.
>
> The larger factors of numbers of the form 10^10^100+/-10^x for
> various small x were found usinga similar process, but were
> restricted to searches with p having the form k*c+1 where the
> multiplicative constant c is one of the factors of (10^100-x)
>
> Some such c are pretty large, and hence >100 digit factors
> were found by David Broadhurst, myself and others. There are
> still plenty of factors out there to be found if anyone's
> interested in looking for them
>
> Phil
Phil,
Notice that this is a new page. The text you wrote is about numbers
near googolplex ( http://www.alpertron.com.ar/GOOGOL.HTM ). This
thread is about the new page about factors of number near
googolplexplex ( http://www.alpertron.com.ar/GOOGOLP.HTM ). Of course,
prime factors of googolplexplex-1, -10 or +10 are very easy to find
using the methods you mention above.
Phil Carmody
> Phil,
>
> Notice that this is a new page. The text you wrote is about numbers
> near googolplex ( http://www.alpertron.com.ar/GOOGOL.HTM ). This
> thread is about the new page about factors of number near
> googolplexplex ( http://www.alpertron.com.ar/GOOGOLP.HTM ). Of course,
> prime factors of googolplexplex-1, -10 or +10 are very easy to find
> using the methods you mention above.
Aha, my window was too narrow!EItherthat ore I thought there
was an echoecho.
Just out of curiosity, I started generating factors of 10^10^10^100-1,
and there aren't as many as I'd thought.
The biggest so far is:
2900240811398724360969936242327094078063964843751
I'm generating them at about 5 seconds per prime, but that will
slow down as they get larger. Shall I just mail you the whole log
in a day, or do you want me to use the form on the web-page?
Oooh:
27985968577282083202817375422455370426177978515625000001
To avoid anyone else duplicating my search space, it's:
(10k+{1,3,7,9}) * 2^a * 5^b + 1 k=0..99; a+b<1000)
10^10^10^100-100 looks like a more interesting beast so I'll
look at that next. However, 10^10^10^100-10 looks like it's a
complete orgy of factors, and you may as well generate those
locally, or your inbox will fill quicker than a quickly-filling
thing. 10^10^10^100+100 looks interesting too.
10^10^10^100+1 looks, ahem, either interesting or incredibly
boring. I won't be looking there.
Ooooh:
41020767071492613881409885394704883943006734625669196248054504394531251
Phil
39316827516215228381720551693694065686912608725833706557750701904296875001
Dario Alpern
Phil,
Since 10^10^100-1 is a factor of 10^10^10^100-1, all 1965 prime
factors of the first number that are already in my site must be
factors of the second number. It would be interesting to find factors
of (10^10^10^100-1)/(10^10^100-1), or prime factors of 10^10^10^100+1.
Phil Carmody
> factors of the first number that are already in my site must be
> factors of the second number. It would be interesting to find factors
> of (10^10^10^100-1)/(10^10^100-1), or prime factors of 10^10^10^100+1.
That small sliver was hardly worth excluding, I decided to duplicate
even your small factors just as a verification. My main interest lies
in numbers such as
4005533629136876668255363232411572926006364236370205836232150527516038692523665202658730639571332046375335740815095810063352808205217028956393221050990526411431876849102071814928676713740705607342132916792729681678735119296285074495304535413180515614779766771198941110523698109673669965485887090039796021301299333572387695312500000001
Phil
Phil Carmody
> alpe...@hotmail.com (Dario Alpern) writes:
Dario,
>4000 factors are on their way to that hotmail address.
If it's an unread account, just dop me a note, and
I can get them to you via some other means.
Dario Alpern
> Phil Carmody <thefatphi...@yahoo.co.uk> writes:
> > alpe...@hotmail.com (Dario Alpern) writes:
>
> Dario,
> >4000 factors are on their way to that hotmail address.
> If it's an unread account, just dop me a note, and
> I can get them to you via some other means.
>
> Phil
I've just uploaded the new version of the Perl script and data for the
factors of googolplexplex - 1 that includes 5482 prime factors up to
413 digits using the data provided by Phil Carmody.
The URL is: http://www.alpertron.com.ar/glpxm1.pl