mersenneforum.org What is the status of the search and another link
 Register FAQ Search Today's Posts Mark Forums Read

2003-05-14, 14:56   #34
wblipp

"William"
May 2003
New Haven

1001010001012 Posts

Quote:
 Originally Posted by TTn If no one opposes this statement: "If p divides k, then p does not divide k*2^n-1. This means that N=k*2^n-1 is prime with probability k/phi(k) * 1/ln(N) instead of probability 1/ln(N).
You're looking for an adjustment to the probability of prime estimated from the Prime Number Theorem as 1/ln(x). That estimate applies to consecutive integers; in consecutive integers we know that 1/2 are divisible by 2, 1/3 of the remainder are divisible by 3, 1/5 of the remainder are divisible by 5, 1/7 of the remainder are divisible by 7 etc. You correctly note that divisibility is different for k. But it's different for other numbers, too. 3*2^k-1 is never divisible by 2, 7, 17, 31 and others. 1/4 are divisible by 5 and 1/18 are divisible by 19, but half of the numbers divisible by 19 are also divisible by 5.

What you need is the "Proth-Minus" Weight of k, analogous to Proth Weight. Proth Weight is the adjustment needed for k*2^n+1. Yves Gallot's paper on weights and Jack Brennen's Java calculator are places to start learning about Proth Weight. The concepts for k*2^n-1 should be identical.

From personal experience, the best way to estimate these weights is to use the follow the methods of Brennen and Gallot to calculate the approximate effect of large numbers of primes. I tried calculating the exact effect of small numbers of primes, and ended up with inferior estimates that gradually converge to the Brennan and Gallot estimates as the "small number" gets bigger.

 2003-05-14, 18:53 #35 TTn   5A416 Posts I've been studying the proth weights too, and will add some info to my website about it. Though there is some validity to my 15k search. BTW my project has just found 465*2^248940-1 is prime! :(
 2003-05-18, 06:38 #36 paulunderwood     Sep 2002 Database er0rr 22·1,093 Posts A 1.4 trillion range of divisors has been completed in 5 days; My 1GHz Athlon removed 56 candidates -- no change over previous weeks rate of candidate elimination . Have set up another 2 trillion range of divisors which will take the maximum divisor tested to over 10 trillion. There is no hurry. Let me sieve and sieve. And when I say "ok" then join in in force. Otherwise things are ticking over nicely on the participants' testing side of the search.
 2003-05-25, 11:42 #37 paulunderwood     Sep 2002 Database er0rr 22×1,093 Posts The maximum divisor in the sieve has reached 10.2 trillion on the range 455,000 to 1,000,000 with 34,940 candidates left. In 165 hours my 1 GHz Athlon computer eliminated 62 candidates -- about one every 2:40 hours. I have set four computers sieving a further 2.8 trillion range of divisors. I feel the sieving phase is going to be completed with in the next week or two after which I will have a chance of finding a prime by doing some testing myself. Using the formulae based on the approximation that testing time quadruples for doubling of size in 'n', we can see the project's progress has reached ( assuming all tests given out have been completed ): (455000^3-191600^3)/(1000000^3-191600^3) = 0.08778
 2003-06-01, 12:08 #38 paulunderwood     Sep 2002 Database er0rr 22·1,093 Posts The fourth machine I used for sieving was a 2.4 GHz P4 and it behaved like a 1 GHz Athlon. Fortunately, Thomas Ritschel is helping me out with a fast Athlon and I have put the P4 on LLR testing 8) We have reached a maximum divisor of 12.8 trillion. My 1 GHz Athlon eliminated 52 candidates in 165 hours -- one every 3:10 hours.
 2003-06-05, 12:51 #39 paulunderwood     Sep 2002 Database er0rr 104248 Posts My 1 GHz Athlon eliminated 23 candidates in 114 hours -- one every 4:57 hours. We have now stopped sieving with the maximum divisor at 14.7 trillion. There are 32,283 candidates left over between 490,000 and 1,000,000. I have tried to contact Edward Dillio who has seven ranges booked out for testing but he is very difficult to get hold of. I will give him two more weeks to get in touch and if there is no communication with him I will re-assign his ranges.
 2003-06-22, 05:03 #40 paulunderwood     Sep 2002 Database er0rr 22×1,093 Posts Edward Dillio's ranges have been put back in the pool of those to be tested freeing up 9 times 5000 'n' blocks. Perhaps there is a prime or two in these ;)
 2003-06-30, 19:46 #41 paulunderwood     Sep 2002 Database er0rr 104248 Posts Ed tells me his computers got fried by a lightening strike -- ouch! We have covered his ranges and the results are coming in, but no primes yet. Ed has taken out a new range. We are now at 553,333 +. I suppose that the primes are going to be large :(
 2003-07-16, 05:42 #42 paulunderwood     Sep 2002 Database er0rr 104248 Posts I have cut down the size of each range to 2,500 and they will be cut progressively as we test for larger prime numbers. 25,831 candidates are left available for testing -- 592,000-1,000,000 We are 18% done on this project. :(
 2003-08-26, 00:07 #43 paulunderwood     Sep 2002 Database er0rr 22×1,093 Posts This project is moving along nicely as we are about to start testing the primality of numbers with greater than 200,000 decimal digits. In terms of work, this is about 1/3 of the way to a million bits, the initial goal of this project. With the sieving being completely done, it only remains to test the remaining 21,433 candidates ( which can so easily be done with the wonderful client computer programs we use. ) I'd guess there are about 8-9GHz years of number crunching left to do and at the current rate we will complete in about 8 months -- with more help even sooner -- hint, hint. The kind people who have contributed to date can be found at: http://primes.utm.edu/bios/page.php?id=479 Last fiddled with by paulunderwood on 2003-09-15 at 21:59
 2003-12-22, 22:03 #44 paulunderwood     Sep 2002 Database er0rr 22×1,093 Posts Merry Xmas and a primeful New Year! 220,000 computers! Hoping for extra computing power for the project in the new year especially if we see a IBDWT LLR

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Lounge 148 2022-11-01 18:30 paulunderwood 3*2^n-1 Search 2 2004-05-17 22:13 rogue Factoring 13 2004-05-01 14:48 Xyzzy Hardware 0 2003-08-21 00:06 Xyzzy Lounge 4 2003-06-28 13:37

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

Thu Dec 1 20:05:20 UTC 2022 up 105 days, 17:33, 0 users, load averages: 0.77, 0.87, 0.94