mersenneforum.org A Desperate appeal! (by Richard K. Guy)... deadline is September 30, 2016
 Register FAQ Search Today's Posts Mark Forums Read

2013-10-02, 01:08   #23
bsquared

"Ben"
Feb 2007

22·23·37 Posts

Quote:
 Originally Posted by CRGreathouse You're talking about Mr. P-1, right? I laughed.
.

 2013-10-02, 07:09 #24 LaurV Romulan Interpreter     Jun 2011 Thailand 11·853 Posts You all seem like you are sure that Mr. Guy will die in 3 years... Who the hack cares about factors for Fermat numbers? I wish that none would be found till 2026 and Mr. Guy lose the bet, but personally pay the 20 bucks with his own hand after the expiration in 2026... Last fiddled with by LaurV on 2013-10-02 at 07:09
2013-10-02, 08:30   #25
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100101011112 Posts

Quote:
 Originally Posted by LaurV You all seem like you are sure that Mr. Guy will die in 3 years...
I cannot believe I've just read that. Rude? Illogical? Both?

 2013-10-02, 09:11 #26 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 939110 Posts the tyranny of evil men Always wanted to find this speech, but it is too obscure for people to know. And it's a shame. A hundred times more people probably think in terms of, say, "Five Easy Pieces", you know, or Jules-"I'm-trying-real-hard-to-be-the-shepherd" from Pulp Fiction. (And by all means, go ahead thinking that we are the tyranny of evil men, complete with a Mr.9 mm in your face while reading from the Bible. "But that sh!t ain't the truth either." "Go.") But here's an explanation that really matters, in my opinion:
2013-10-02, 13:08   #27
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by Batalov A hundred times more people probably think in terms of, say, "Five Easy Pieces"
Do you mean the Houston Comets?

2013-10-02, 19:00   #28
c10ck3r

Aug 2010
Kansas

547 Posts

Quote:
 Originally Posted by c10ck3r So, toying with this idea further...how hard would it be to make a script to do a false sieve for this? I imagine (no experience with programming beyond BASIC) that one could create a script to find all factors of numbers of the form F(X)-(sqrt(F(X)-1)-n) below, say, 1M, then either a) write the n value to postsieve.txt if all factors are to an even power, then increase the n value by 1 and continue or b) increase the n values by one and continue without writing. @RDS- please, don't bother lecturing me about the fact that this is not a feasible effort. If you care to explain how high the n value would be expected to reach before success as a function of X or F(X), however, feel free, I would enjoy seeing how that would be approximated. Caution: F(X) is assumed to be the Xth Fermat number.
Can someone at least confirm that the above equation would be right for finding these types of numbers (sums of squares for Fermat numbers)?

2013-10-02, 23:25   #29
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

111910 Posts

Quote:
 Originally Posted by c10ck3r So, toying with this idea further...how hard would it be to make a script to do a false sieve for this? I imagine (no experience with programming beyond BASIC) that one could create a script to find all factors of numbers of the form F(X)-(sqrt(F(X)-1)-n) below, say, 1M, then either a) write the n value to postsieve.txt if all factors are to an even power, then increase the n value by 1 and continue or b) increase the n values by one and continue without writing. Caution: F(X) is assumed to be the Xth Fermat number.
We actually want to look at the expression F(X)-(sqrt(F(X)-1)-n)2 (note the exponent) and determine if it is a perfect square rather than find its factors. The value for n = 0 is trivially the square 1, so we start at n = 1 and increase it. In general, we can eliminate non-squares by sieving. Any square must be congruent to 0, 1, or 4 mod 8, for example, so any values of F(X)-(sqrt(F(X)-1)-n)2 which are congruent to 2, 3, 5, 6, or 7 mod 8 need not be further considered. This immediately eliminates all values of n congruent to 2 mod 4. Next we consider that any square must be congruent to 0 or 1 mod 3. This eliminates all values of n congruent to 1 mod 3. (Or we could say congruent to 0, 1, 4, or 7 mod 9 to eliminate more values of n.) In general, we set up a table for each prime p that we use for sieving that allows us to infer from n's congruence class mod p whether the above expression is a non-square or possibly a square. After we sieve with a reasonable number of different p's (Lehmer used all p's less than or equal to 127 in his Delay Line Sieve, later increased to 157) we expect that the few remaining n values are good candidates for generating perfect squares in the above expression. We can then test those candidates for each remaining n by taking the integer square root of F(X)-(sqrt(F(X)-1)-n)2, squaring that, and seeing if it is equal to the original expression.

I have coded such a sieve in C, but to optimize it, the sieving routines should be done in assembly language. It would be a good learning exercise, though, to code it in a higher level language. The integer square-root function is only called occasionally, and the C routine in GMP or MPIR would probably work just fine. Or you could just write the candidate n values to a list (there shouldn't be very many) and check to see if the resulting expression is a square using PARI or some other computational package. Try it with F5. You are sieving values of F5 - (65536 - n)2 = 1 + 131072*n - n2 by all small primes p to eliminate all values of n for which this expression is not a perfect square mod p. If you set up an array to check all n values from 1 to say, 20,000, you should find that the only value of n which gives you a perfect square will be 3272 = 65536 - 62264.

There is more to my method than this, I suggested working in general on trying to find sums of squares representations of N, where N could be a Fermat number, or a composite factor of a Fermat number, or either of these two possibilities multiplied by a product of distinct prime factors which all have representations of sums of squares. Or N could be any other number whose factors are all equal to 1 mod 4. The possibilities of trying many multipliers takes this from being a deterministic method of order n1/2 to a probabilistic method of order n1/4. The method of sieving was around for centuries before the Lehmers used an electronic device to automate and speed up the sieving. In general, we sieve on N - (sqrt(N) - n)2 where sqrt(N) is the integer truncation of the square-root of N.

 2013-10-03, 03:00 #30 gd_barnes     May 2007 Kansas; USA 2·7·739 Posts Hum. Factoring a 1133-digit number or primality testing a 2.58+ billion-digit number? Which will require more CPU time assuming an "average" number of factors and difficulty for the 1133-digit number? My guess is that the factorization would require more CPU time in the long run assuming that it was "average" with today's knowledge and technology. BUT...2 factors (pun intended) weigh in favor of doing the factorization: 1. It can be distributed across 1000s of computers. To the best of my knowledge, the primality test cannot. (At least not yet anyway.) 2. We might get lucky and factor it quickly. There would be no equivalent probability of "luckiness" for the primality test. It would be interesting to see a project set up specifically to fully factor F12. Even with many computers running it, I think it would be unlikely to complete its task in 3 years. It would become the equivalent of a "Riesel Sieve" or 17-or-bust type project where the goal is a finite one but will likely take decades to finish. Personally, I find huge finite projects to be much more interesting than open-ended ones that have no purpose other than to just find primes until they get tired of searching for them. Last fiddled with by gd_barnes on 2013-10-03 at 03:03
 2013-10-03, 03:33 #31 LaurV Romulan Interpreter     Jun 2011 Thailand 11×853 Posts third factor: (in favor of factorization) 3. you may finish the primality test and find out that F33 is composite, therefore you are back at the starting point (edit: which would - most probably - be the case, because the general belief/heuristic/probabilistic/etc is that all fermat numbers are composite, except the first 5). Last fiddled with by LaurV on 2013-10-03 at 03:37
2013-10-03, 04:27   #32
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

22×17×109 Posts

Quote:
 Originally Posted by gd_barnes It would be interesting to see a project set up specifically to fully factor F12.
Or make it a simple 3-year challenge: "Save Richard Guy $20" project. Hmm, not catchy. How 'bout the "save Richard Guy from bankruptcy" project. 2013-10-03, 04:32 #33 LaurV Romulan Interpreter Jun 2011 Thailand 11×853 Posts Quote:  Originally Posted by Prime95 "Save Richard Guy$20"
What do you mean by that? If I would be the lucky son of the gun to factor some Fm, then I WILL take his \$10, and I will expressly ask him to send me a signed check... After 50 years that will worth a fortune! I will make my grandchildren happy and they won't need to work for all their lives...

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Lounge 5 2016-11-18 00:43 Batalov Puzzles 8 2016-10-04 14:10 amphoria YAFU 22 2016-09-17 09:47 cheesehead Soap Box 50 2014-06-30 01:06 dave_dm GMP-ECM 0 2005-06-29 02:23

All times are UTC. The time now is 16:05.

Tue Apr 20 16:05:52 UTC 2021 up 12 days, 10:46, 1 user, load averages: 2.73, 2.76, 2.51