A Desperate appeal! (by Richard K. Guy)... deadline is September 30, 2016

[bsquared]

Originally Posted by CRGreathouse

You're talking about Mr. P-1, right? I laughed.

.

[LaurV]

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...

[Batalov]

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?

[Batalov]

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:

[R.D. Silverman]

Originally Posted by Batalov

A hundred times more people probably think in terms of, say, "Five Easy Pieces"

Do you mean the Houston Comets?

[c10ck3r]

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)?

[philmoore]

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)² (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)² 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)², 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)² = 1 + 131072*n - n² 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 n^1/2 to a probabilistic method of order n^1/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)² where sqrt(N) is the integer truncation of the square-root of N.

[gd_barnes]

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.

[LaurV]

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).

[Prime95]

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.

[LaurV]

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...