-   3*2^n-1 Search (
-   -   What is the status of the search and another link (

wblipp 2003-05-14 14:56

[quote="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).[/quote]

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 [url=]paper on weights[/url] and Jack Brennen's [url=]Java calculator[/url] 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.

TTn 2003-05-14 18:53

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!

paulunderwood 2003-05-18 06:38

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 :evil: . 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 2003-05-25 11:42

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 :banana:

paulunderwood 2003-06-01 12:08

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 2003-06-05 12:51

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 2003-06-22 05:03

:rolleyes: 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 2003-06-30 19:46

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 2003-07-16 05:42

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 2003-08-26 00:07

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:


paulunderwood 2003-12-22 22:03

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 :whistle:

All times are UTC. The time now is 00:45.

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