mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > 3*2^n-1 Search

 
 
Thread Tools
Old 2003-05-14, 14:56   #34
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

26·37 Posts
Default

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.
wblipp is offline  
Old 2003-05-14, 18:53   #35
TTn
 

5·1,759 Posts
Default

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!
:(
 
Old 2003-05-18, 06:38   #36
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1111000011012 Posts
Default

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.
paulunderwood is offline  
Old 2003-05-25, 11:42   #37
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,853 Posts
Default

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
paulunderwood is offline  
Old 2003-06-01, 12:08   #38
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,853 Posts
Default

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.
paulunderwood is offline  
Old 2003-06-05, 12:51   #39
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,853 Posts
Default

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.
paulunderwood is offline  
Old 2003-06-22, 05:03   #40
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,853 Posts
Default

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 ;)
paulunderwood is offline  
Old 2003-06-30, 19:46   #41
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

385310 Posts
Default

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 :(
paulunderwood is offline  
Old 2003-07-16, 05:42   #42
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1111000011012 Posts
Default

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. :(
paulunderwood is offline  
Old 2003-08-26, 00:07   #43
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

385310 Posts
Default

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
paulunderwood is offline  
Old 2003-12-22, 22:03   #44
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,853 Posts
Default 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
paulunderwood is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Forum Donation and Expense List Xyzzy Lounge 135 2021-10-02 13:00
link to status table paulunderwood 3*2^n-1 Search 2 2004-05-17 22:13
Status of Fermat Search rogue Factoring 13 2004-05-01 14:48
Interesting link... Xyzzy Hardware 0 2003-08-21 00:06
Nice link... Xyzzy Lounge 4 2003-06-28 13:37

All times are UTC. The time now is 03:59.


Mon Oct 18 03:59:44 UTC 2021 up 86 days, 22:28, 0 users, load averages: 1.19, 0.99, 0.94

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.