mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-06-22, 06:53   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default Fermat number factors

I am interested in finding fermat number factors that themselves are generalized fermats.

The only known example is 169*2^63686+1. (Found by looking at factors on prothsearch.net) These seem to be extremely rare. Is it possible to predict their density?

In order to find more of such factors, I have started testing numbers of the form a^2*2^(2*n)+1.

I was just wondering if anyone had any tips on how to approach this problem.

- One of the problems is that the sieve program does not work on primes of the form 4X+1 only, it tries to test if primes of the form 4x+3 will divide the generalized fermats also.

-Secondly, like using Morehead's theorem and similar theorem can some n (exponent) values be removed from the search? I have already figured out algebric factorization for some of the n values.

-Any other ways to speed this up?
-Anyone interested in helping out?

Thank you
Citrix is offline   Reply With Quote
Old 2006-08-06, 23:57   #2
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by Citrix
-Anyone interested in helping out?
From the discusion in this thread I gather you plan to test sequences a^(2^y)*2^(2^y)+1 for small a and with y as large as possible?

I can help with some PRP testing if you want to post some candidates.
geoff is offline   Reply With Quote
Old 2006-08-08, 15:24   #3
Citrix
 
Citrix's Avatar
 
Jun 2003

32×52×7 Posts
Default

I am not at home this week and do not have access to the files. I have only started sieving/PRPing 3^16 and not anything else.

If you want you can start on any other k, or we can sort things out, once I get back, early next week.
Citrix is offline   Reply With Quote
Old 2006-08-09, 05:33   #4
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

I have managed to get 3^16 file. It is sieved upto 165 G, so safe to PRP till 200,000 after that I or someone else will have to sieve it more. I am almost at n=100K. I will reserve 100k -200k for you, if that is ok?

My plan is that, if I do not find a prime until 200k, I will leave this k.
The primes so far were
43046721*2^176+1 is prime! Time: 66.749 ms.
43046721*2^1792+1 is prime! Time: 26.007 ms.
43046721*2^19936+1 is prime! Time: 2.898 sec.
(Not a good k to find primes?)


As for finding fermat factors, a prime is more likely to be a fermat factor if k is small, hence I am thinking of only test small k's. 3^16 was just for fun, it is unlikely it will reveal a fermat factor. (Since till k=600 is being tested by prothsearch.net, I was thinking of searching all the perfect squares under 1024.--beyond that the probability of finding a fermat factor is too low)

So between the ranges 600 and 1024 there are only 3 sqaures, namely 625, 729, 961. If you wish, you can choose one of these k's to work on.

(I do not have any sieve files, since I haven't started on the above 3)

Thanks.
Attached Files
File Type: txt t16_b2_k43046721.txt (190.9 KB, 283 views)
Citrix is offline   Reply With Quote
Old 2006-08-10, 07:38   #5
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Quote:
Originally Posted by Citrix
I have managed to get 3^16 file. It is sieved upto 165 G, so safe to PRP till 200,000 after that I or someone else will have to sieve it more. I am almost at n=100K. I will reserve 100k -200k for you, if that is ok?
OK, I will PRP test (3^16)*2^n+1 for 100,000 < n < 200,000.
geoff is offline   Reply With Quote
Old 2006-08-12, 23:35   #6
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

I finished PRP testing 3^16 for 100,000 < n < 200,000:

3^16*2^168480+1 is prime.

I also tested 3^32, 5^16, 7^16, 11^16, 13^16 for 0 < n < 50,000, the following are prime:

3^32*2^160+1
3^32*2^800+1
3^32*2^1568+1
3^32*2^2176+1

5^16*2^288+1
5^16*2^1264+1
5^16*2^7296+1
5^16*2^19648+1

11^16*2^32+1
11^16*2^64+1
11^16*2^112+1
11^16*2^1504+1

13^16*2^96+1
13^16*2^544+1
13^16*2^2688+1
geoff is offline   Reply With Quote
Old 2006-08-14, 23:41   #7
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

Code:
Primes
43046721*2^176+1 is prime! 
43046721*2^1792+1 is prime! 
43046721*2^19936+1 is prime! 
43046721*2^87520+1 is prime! 
43046721*2^168480+1 is prime!

Ranges
0-100K Citrix
100-200k geoff
200-300K Citrix (At 250k.)
Citrix is offline   Reply With Quote
Old 2006-08-27, 00:04   #8
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Please reserve 300K-400K for me. I will also extend the sieve up to p=1e12 (currently at p=400e9).
geoff is offline   Reply With Quote
Old 2006-08-27, 00:45   #9
Citrix
 
Citrix's Avatar
 
Jun 2003

32×52×7 Posts
Default

Quote:
Originally Posted by geoff View Post
Please reserve 300K-400K for me. I will also extend the sieve up to p=1e12 (currently at p=400e9).
I hadn't updated the thread, but I have PRPed to 325K. Could I have the new sieved file. I would like to work on 400-500K.
Citrix is offline   Reply With Quote
Old 2006-08-27, 01:02   #10
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Quote:
Originally Posted by Citrix View Post
I hadn't updated the thread, but I have PRPed to 325K. Could I have the new sieved file. I would like to work on 400-500K.
OK, so I will PRP 325K-400K. I will PM you with the sieve file tomorrow (it is running on my home machine), and post it here when it is finished to 1e12, probably in a couple of days.
geoff is offline   Reply With Quote
Old 2006-08-31, 01:51   #11
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Attached is the sieve file for (3^16)*2^n+1, sieved to a little over 1e12. I was getting about 12 minutes per factor on a P3/600, so more sieving is worthwhile if you intend to test all of the candidates.
Attached Files
File Type: zip sieve1165e9.zip (29.3 KB, 127 views)
geoff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New Fermat factors philmoore FermatSearch 318 2020-10-12 22:20
Special Form of Mersenne and Fermat Number Factors michael Math 31 2015-09-04 05:57
Number 59649589127497217 is a factor of Fermat number F7 literka Miscellaneous Math 73 2013-11-17 10:33
Fermat number F6=18446744073709551617 is a composite number. Proof. literka Factoring 5 2012-01-30 12:28
Weighted Fermat factors Top 20 Merfighters Factoring 0 2010-04-13 14:16

All times are UTC. The time now is 17:27.

Mon Nov 23 17:27:00 UTC 2020 up 74 days, 14:37, 2 users, load averages: 2.74, 2.61, 2.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.