Operation Megabit Twin
 

This is a side project that looks for twins and sophies of the form k*2^1000000+/- 1. It's a hybrid of the n=390000 effort and Primegrid's n=666666 Sophie Germain search. Basically, there are three stages of sieving: in the first stage, everything from k=1-120T was sieved up to p=100G with NewPGen's "LM" (lucky minus) option. This stage was finished in mid-July, and the contributors are shown below.

[code]
Range of k User
0T-1T Oddball
1T-3T amphoria
3T-4T Oddball
4T-7T Flatlander
7T-8T amphoria
8T-9T Merfighters
9T-10T Flatlander
10T-12T amphoria
12T-13T Flatlander
13T-14T amphoria
14T-16T Flatlander
16T-17T Oddball
17T-18T amphoria
18T-19T Flatlander
19T-20T amphoria
20T-21T Lennart
21T-22T amphoria
22T-23T Oddball
23T-29T amphoria
29T-32T Oddball
32T-34T amphoria
34T-65T Flatlander
65T-69T amphoria
69T-73T Oddball
73T-76T Flatlander
76T-79T amphoria
79T-83T Flatlander
83T-87T amphoria
87T-90T Oddball
90T-94T Flatlander
94T-98T amphoria
98T-100T Oddball
100T-104T amphoria
104T-106T Oddball
106T-109T amphoria
109T-111T Oddball
111T-114T amphoria
114T-118T Flatlander
118T-120T Oddball
[/code]In the next stage, the range was sieved from p=100G to p=45T for twins only. It was broken down into 6 files that are 20T each. This stage was finished on September 18, 2010, and the contributors are shown below.

[code]
Range of k User
0-20T amphoria
20T-40T amphoria
40T-60T amphoria
60T-80T Flatlander
80T-100T Flatlander
100T-120T amphoria
[/code]The 6 sieved files are combined into one file, which is sieved [B]only for twins[/B] from p=45T to p=100P. If you're interested in participating, use NewPGen to sieve an available range below and upload the NewPGen.del file to sendspace when you're done. Currently, the status looks like this:

[code]
Range of p User Status
45T-60T amphoria complete
60T-61T Dougal complete
61T-62T Oddball complete
62T-70T Dougal complete
70T-80T amphoria complete
80T-100T Dougal complete
100T-140T amphoria complete
140T-240T Dougal complete
240T-350T amphoria complete
350T-500T Dougal complete
500T-550T amphoria complete
550T-750T Dougal complete
750T-800T amphoria complete
800T-801T firejuggler complete
801T-4000T amphoria complete
4000T-4800T Puzzle-Peter complete
4800T-5000T monst complete
5000T-5800T amphoria complete
5800T-6000T amphoria complete
6000T-6400T amphoria complete
6400T-6405T firejuggler complete
6405T-6600T amphoria complete
6600T-7600T KEP complete
7600T-10100T amphoria complete
10100T-12500T amphoria complete
12500T-14800T amphoria complete
14800T-17000T amphoria complete
17000T-17200T Neo complete
17200T-17443T Neo complete
17443T-18000T amphoria in progress
18000T-18200T Neo complete
18200T-18500T amphoria in progress
18500T-18735T Neo complete
18735T-19000T amphoria in progress
19000T-20000T odicin complete
20000T-20300T odicin complete
20300T-20400T odicin complete
20400T-20800T odicin in progress
20800T-21000T odicin complete
21000T-23200T amphoria complete
23200T-26200T amphoria complete
26200T-26600T amphoria in progress
26600T-27800T amphoria complete
27800T-29000T amphoria in progress
29000T+ available
[/code]Eventually, LLR testing will be opened, and Operation Megabit Twin will be declared a success if and when a n=1,000,000 twin is found.

You have three chances of getting a world record if a prime is found. For example, if 66555*2^1000000-1 is prime, 66555*2^1000000+1 will be checked for twins. Later, both 66555*2^999999-1 and 66555*2^1000001-1 will be checked for sophies. Even if neither of those three numbers are prime, your original prime will still be able to get into the top 5000 list.

Sieve file: [URL]http://www.amphoria.co.uk/megabit-twin/[/URL]

Stats:
[code]
Rank User T sieved
1 amphoria 20991
2 odicin 1600
3 KEP 1000
4 Neo 878
5 Puzzle-Peter 800
6 Dougal 479
7 monst 200
8 Flatlander 94
9 Oddball 23
10 firejuggler 6
11 Merfighters 1
11 Lennart 1
[/code]The stats are calculated based on T sieved. If you sieved k=10T-11T in stage 1, you'll get one point. If you sieved k=20T-40T in stage 2, you get 20 points. If you sieved the file from p=45T-50T in stage 3, you get 5 points.

Taking k=1T-2T.

File for k=1-205G, sieved to 24G:

[url]http://www.sendspace.com/file/onovek[/url]

No, this isn't intended to be a list of numbers to be LLRed; it's just a save point for my progress. I'm running it on an old computer, so I'm a bit worried that the hard drive may crash.

Just throwing some numbers around:

Odds that a random candidate in this file will yield a twin: 1 in 266 million
Odds of hitting the Powerball jackpot if you buy one ticket: 1 in 195 million
Odds of hitting the Mega Millions jackpot if you buy one ticket: 1 in 176 million
Odds that a random candidate in this file will yield a sophie germain: 1 in 133 million
Odds that a random candidate in this file will yield either a twin or a sophie germain: 1 in 89 million

Odds of getting a straight flush if you're dealt five cards: 1 in 72200
Odds of having all tails or all heads if you flip a coin 15 times: 1 in 16400
Odds that a random candidate in this file will be prime: 1 in 16300
Odds of getting four of a kind if you're dealt five cards: 1 in 4200

Odds of getting snake eyes twice in a row if you roll two dice: 1 in 1300
Odds that one of the candidates in the file will yield a twin: 1 in 1000
Odds that one of the candidates in the file will yield a sophie germain: 1 in 500
Odds that one of the candidates in the file will yield either a twin or a sophie germain: 1 in 340

Estimated number of single primes in the file: 16
Number of miles in an average American's commute: 16

Nice project! :smile:
I'm going to contribute to this project as soon as my computer finishes the current work.

1T-2T complete to p=100G.

Taking 2T-3T.

[url]http://www.sendspace.com/file/o90yun[/url]

should "verify results" be checked?

[QUOTE=agent1;216507]should "verify results" be checked?[/QUOTE]
It's highly recommended for stage 1 (lucky minus sieve to p=100G) and required for stage 2 (twin sieve past 100G). But if you run the sieve on stable hardware and forget to check "verify results" for stage 1, you don't have to re-do the sieve.

Here's what the NewPGen contents file has to say about it:
[quote]it is recommended that it is always checked, particularly as p gets large (where the scope for programming errors increases), and only uncheck it during the early parts of the sieving if you are using a primorial mode and many k's are being thrown out every second. If you are not using a primorial sieve then leave this checked, as then it makes no difference to NewPGen's performance.[/quote]

Hi

Approx. how long would it take to sieve 1T on 1 core of a Q6700 @ 2.66GHz?

Chris

[QUOTE=Flatlander;216662]Hi

Approx. how long would it take to sieve 1T on 1 core of a Q6700 @ 2.66GHz?

Chris[/QUOTE]

I am sieving on a slower processor. But extrapolating from that I would guess about 2.5 days.

Okay, thanks.

Taking [B]4T-5T[/B].
(I started a few hours ago but didn't want to commit myself. Didn't want to wake to find myself overlapping someone else's work by taking 3T-4T. :smile: )

Off topic edit:
(Hmmm. Time for me to find a new avatar.)

4T-5T is complete:
[URL="http://www.sendspace.com/file/83jz7t"]http://www.sendspace.com/file/83jz7t[/URL]
1,002,729 candidates. (iirc)

Took about 26 hrs @ 2.66GHz on one C2Quad core. :smile:
Most of which was NewPGen splitting the sieve into little pieces and taking it to 1G; despite reserving 485Mb. 1G to 100G only took about 3 hrs. I asked Paul Jobling some time ago if it was possible to increase the 485Mb limit but he said that Windows wouldn't let him reserve more.
Nobody has mentioned this splitting. I assume I'm doing things right?

Taking 5T-[B]7T[/B] on one core. (Leaving the gap at 3T-4T.)

[QUOTE=Flatlander;216729]4T-5T is complete:
[URL="http://www.sendspace.com/file/83jz7t"]http://www.sendspace.com/file/83jz7t[/URL]
1,002,729 candidates. (iirc)[/quote]
I think you uploaded the wrong file. That one is ~40% bigger than amphoria's one, and it's only sieved to p=16G. I haven't checked yet, but I think it contains a lot more than 1,002,729 candidates.

[quote]
Took about 26 hrs @ 2.66GHz on one C2Quad core. :smile:
Most of which was NewPGen splitting the sieve into little pieces and taking it to 1G; despite reserving 485Mb. 1G to 100G only took about 3 hrs. I asked Paul Jobling some time ago if it was possible to increase the 485Mb limit but he said that Windows wouldn't let him reserve more.
Nobody has mentioned this splitting. I assume I'm doing things right?
[/QUOTE]
That seems right; the splitting is the most time consuming part of the sieve. If you upload the file to p=100G, I can check a few small random parts of it (4.10T-4.101T, for example) to make sure nothing looks wrong.

[quote]
Off topic edit:
(Hmmm. Time for me to find a new avatar.)[/quote]
I don't know whether you've used it before, but judging from your username, you might want to get a picture of the flat earth. Something like this:

[url]http://www.christopherfowler.co.uk/blog/wp-content/uploads/2010/02/Flat-earth.jpg[/url]

edit:
[quote](Leaving the gap at 3T-4T.)[/quote]
My 0-1T range should be done in two days, so I'll fill up the gap.

[QUOTE=Oddball;216752]I think you uploaded the wrong file. That one is ~40% bigger than amphoria's one, and it's only sieved to p=16G.
...[/QUOTE]

Sorry. I rebooted the PC and started with a new filename at 16G.
[URL="http://www.sendspace.com/file/l1ebau"]Correct 4T-5T[/URL]

(Thanks for digging up the avatar. I did have one similar to that many moons ago. I think the fact that I keep changing it must be an identity/mid-life crisis!)

2T-3T complete.

Taking 7T-8T.

[url]http://www.sendspace.com/file/n9p2iy[/url]

I want to join this.
Due to doing something else, I'm just taking the range 8T-9T. :smile:

Edit: I don't want to consume too much time,
so I'm releasing 8.6T~9T.
Edit again: I decided again. I'm not releasing 8.6T~9T. :smile:

[QUOTE=Merfighters;216928]I want to join this.
Due to doing something else, I'm just taking the range 8T-9T. :smile:

Edit: I don't want to consume too much time,
so I'm releasing 8.6T~9T.
Edit again: I decided again. I'm not releasing 8.6T~9T. :smile:[/QUOTE]
Welcome to TPS! I've added your reservation to the first post.

Elapsed time: About 12 hours.
19% of 8T to 9T sieved to 1000000007.

I'm using 300Mb of memory. That's about 10% of the whole memory.
Do I need to use more?

5T-7T is complete:
[URL="http://www.sendspace.com/file/rifct6"]http://www.sendspace.com/file/rifct6[/URL]

[QUOTE=Merfighters;217063]Elapsed time: About 12 hours.
19% of 8T to 9T sieved to 1000000007.

I'm using 300Mb of memory. That's about 10% of the whole memory.
Do I need to use more?[/QUOTE]
It's up to you. You might see a efficiency increase if you go to 485Mb, but if it's slowing your PC down because you need the memory for other things ...
It's a low priority project after all.

Running a 2T sieve took 4hrs longer than if I had done 2 x 1T sieves. NewPGen was using 400Mb of RAM even when past 1G. Must be a memory bottleneck? I expect there is a sweet-spot somewhere but I'll probably stick to 1T reservations.

Taking 9T-10T.

0-1T complete with 1004859 candidates:

[url]http://www.sendspace.com/file/apf3ld[/url]

gribozavr, do you think you can do the bookkeeping for this subproject too? I'm already storing the files on my PC, but it'll be nice to have a backup.

I can do the bookkeeping. I've downloaded all files.

7T-8T complete.

Taking 10T-11T.

[url]http://www.sendspace.com/file/hd9qqi[/url]

amphoria: I've downloaded your file.

9T-10T is complete:
[URL="http://www.sendspace.com/file/udvmke"]http://www.sendspace.com/file/udvmke[/URL]

Accidentally sieved to 132G. :blush:

Flatlander: I've downloaded your file.

Thanks.
I've also downloaded all the files in this thread. They are then automatically backed up on-line. (Not sure I'll manage to keep it up to 500T and beyond though!)

Half done!

8T-8.5T, sieved to 100G:
[URL]http://www.sendspace.com/file/v4k6zs[/URL]
1002830 k's (including even ones)

[QUOTE=Merfighters;217459]Half done!

8T-8.5T, sieved to 100G:
[URL]http://www.sendspace.com/file/v4k6zs[/URL]
1002830 k's (including even ones)[/QUOTE]

My wild guess that they are sieving only the odd k values. Just download some file.

[QUOTE=R. Gerbicz;217462]My wild guess that they are sieving only the odd k values.[/QUOTE]
That's right. But if you've also sieved the even ones, it's not a problem.

10T-11T complete.

Taking 11T-12T.

[url]http://www.sendspace.com/file/civkm0[/url]

Taking 12T-13T.

11T-12T complete.

Taking 13T-14T.

[url]http://www.sendspace.com/file/zxr4cm[/url]

Taking 14-15T.
(12-13T results to follow.)

8.5T-9T(without even ones) sieving to 1G is nearly completed.

I sieved the range to 1G before, but accidently deleted the file... :unsure:

[QUOTE=Flatlander;217966]Taking 14-15T.
(12-13T results to follow.)[/QUOTE]
12-13T is complete.
[URL="http://www.sendspace.com/file/3fz0fb"]http://www.sendspace.com/file/3fz0fb[/URL]

Also taking 15-16T.

8.5T to 9T, sieved to 100G :razz:

[URL]http://www.sendspace.com/file/xxyrci[/URL]

Edit: I made my own program to merge the results. :smile:

I've downloaded all files.

Too many zeros.
 

15-16T is complete.
[URL="http://www.sendspace.com/file/d90x5i"]http://www.sendspace.com/file/d90x5i[/URL]
Again over-sieved. (To 436G. I had max. p set to 100T! :blush:)

It looks like I'll be joining the oversieving party.

3T-4T complete, slightly oversieved to 101.1G:

[url]http://www.sendspace.com/file/npyny5[/url]

Taking 16T-17T.

14-15T is complete.
[URL="http://www.sendspace.com/file/5ynnga"]http://www.sendspace.com/file/5ynnga[/URL]

13T-14T complete.

[url]http://www.sendspace.com/file/frl5d8[/url]

Taking 17T-18T.

Taking 18-19T.

[URL]http://uwin.mine.nu/TPS/out1000000_20_21.7z[/URL]


Is done with axn new sieve and npg.

Lennart

18-19T is complete.
[URL="http://www.sendspace.com/file/4shhdr"]http://www.sendspace.com/file/4shhdr[/URL]

17T-18T complete.

[url]http://www.sendspace.com/file/yzertx[/url]

Taking 19T-20T.

19T-20T complete using axnSieve to p=100e6.

[url]http://www.sendspace.com/file/5yu9nc[/url]

I am currently running some tests with axnSieve from 50T.
I will post some results soon then start working backwards!

Taking 21T-22T.

16T-17T complete:

[url]http://www.sendspace.com/file/zvt0dp[/url]

Reserving 22T-23T.

I've downloaded all files.

Also taking 23T-24T.

[QUOTE=Flatlander;219014]I am currently running some tests with axnSieve from 50T.
I will post some results soon then start working backwards![/QUOTE]
50-58T should finish tomorrow.
58-65T about Monday.

50-58T is complete.
[url]http://www.sendspace.com/file/r84q33[/url]

[B]edit:[/B]
Reserving 40T-50T

23T-24T complete.

[url]http://www.sendspace.com/file/g2f8gu[/url]

Taking 24T-25T.

gribozavr, could you replace Merfighters 8T-9T range with this file:

[url]http://www.sendspace.com/file/fpnxbb[/url]

I double checked the last part of my range with Merfighters 8.5T-9T file to confirm that axnSieve works. The first 8T-8.5T part of my range will replace Merfighters range, since the first half of his/her range has even k's.

Oddball, you don't need to give me credit for this range.

I've downloaded all files.

Historian: done.

21T-22T complete.

[url]http://www.sendspace.com/file/ugylxf[/url]

I have also had to redo 23T-24T due to a bug in axnSieve.

[url]http://www.sendspace.com/file/7erdyk[/url]

Taking 25T-29T.

24T-25T complete.

[url]http://www.sendspace.com/file/jt6gzv[/url]

22T-23T complete:

[url]http://www.sendspace.com/file/aizsoh[/url]

My newly reserved 29T-32T range should be done later this week.

58-65T is complete.
[url]http://www.sendspace.com/file/rrlmvh[/url]

25T-27T complete.

[url]http://www.sendspace.com/file/l798bu[/url]

Taking 32T-34T.

Taking 34-40T.

27T-29T complete.

[url]http://www.sendspace.com/file/u4lgmf[/url]

32T-34T complete.

[url]http://www.sendspace.com/file/tyx11i[/url]

Taking 65T-69T.

40-50T is complete.
[url]http://www.sendspace.com/file/hpbm8s[/url]

29T-32T complete:

[url]http://www.sendspace.com/file/8kct0o[/url]

Taking 69T-71T.

34-40T is complete.
[url]http://www.sendspace.com/file/3rkyis[/url]

69T-71T complete:

[url]http://www.sendspace.com/file/sf0071[/url]

Taking 71T-73T.

Taking 73-76T.

I've downloaded all files.

65T-69T complete.

[url]http://www.sendspace.com/file/zjtxs9[/url]

Taking 76T-79T.

Taking 79-83T

73-76T is complete.
[url]http://www.sendspace.com/file/j2dd77[/url]

76T-79T complete.

[url]http://www.sendspace.com/file/p8yc5r[/url]

Taking 83T-87T.

71T-73T complete:

[url]http://www.sendspace.com/file/xtd18z[/url]

I'll get 87T-90T.

Taking 90-94T.

79-83 is complete.
[url]http://www.sendspace.com/file/wk9xb1[/url]

90-94T is complete.
[url]http://www.sendspace.com/file/1i6vz8[/url]

I've downloaded all files.

Taking 94T-98T.

87T-90T complete:

[url]http://www.sendspace.com/file/qwm2g8[/url]

Reserving 98T-100T.

83T-87T complete.

[url]http://www.sendspace.com/file/u1160y[/url]

94T-98T complete.

[url]http://www.sendspace.com/file/y4ws6k[/url]

Taking 100T-104T.

98T-100T complete:

[url]http://www.sendspace.com/file/5oht2u[/url]

I'll get 104T-106T.

gribozavr, could you merge the 0-100T files and tell us:

- how many candidates are in that big file
- how much RAM is needed to sieve the file for twins using NewPGen
- how much RAM is needed to sieve the file for twins using tpsieve

I've downloaded all files.

File 000T-100T.txt contains 99946129 k's. The file itself is 2.2 Gb, but only 300 Mb when compressed with xz.

tpsieve (64-bit) refuses to sieve it:
[code]tpsieve version 0.3.4 (testing)
Compiled Sep 7 2009 with GCC 4.3.3
kmax-kmin < 3*2^36 is required[/code]

NewPGen refuses to open the 0T-100T file ("Cannot open the input file"). It seems that it doesn't like large (2 Gb +) files. NewPGen successfully opens a file for 0T-80T and uses 610 Mb of RAM. But it is really sloooooow (removing 1 k every 0.5 seconds).

[QUOTE=gribozavr;220696]
NewPGen refuses to open the 0T-100T file ("Cannot open the input file"). It seems that it doesn't like large (2 Gb +) files. NewPGen successfully opens a file for 0T-80T and uses 610 Mb of RAM. But it is really sloooooow (removing 1 k every 0.5 seconds).[/QUOTE]
I see. If only 0-55T is sieved, what is the removal rate? Also, what's the removal rate if only 0-35T is sieved? I'm interested in knowing where the slowdown starts.

[QUOTE=Oddball;220703]I see. If only 0-55T is sieved, what is the removal rate? Also, what's the removal rate if only 0-35T is sieved? I'm interested in knowing where the slowdown starts.[/QUOTE]

I did a test using a smaller set of k's last weekend and the change from fastarray mode to array mode appeared to occur between 20T and 25T k's.

[QUOTE=amphoria;220722]I did a test using a smaller set of k's last weekend and the change from fastarray mode to array mode appeared to occur between 20T and 25T k's.[/QUOTE]
I don't think fastarray is any better than array mode for large p's. I tried sieving a big 43.9 million candidate file at p=78T, and NewPGen needed 335Mb of RAM. It used array mode, and sieving progressed quite quickly (87 million p/sec). That 87 million p/sec rate remains the same even if the number of candidates is reduced to less than a thousand.

[QUOTE=Oddball;220723]I don't think fastarray is any better than array mode for large p's. [/QUOTE]

For the present purposes, p=100e9 should not be considered "large".

[QUOTE=axn;220732]For the present purposes, p=100e9 should not be considered "large".[/QUOTE]

I can confirm this. 20T-40T gives 48 k's per sec whereas 20T-50T gives 0.4 sec per k.

Taking 106T-109T.

104T-106T complete:

[url]http://www.sendspace.com/file/1rgo42[/url]

Reserving 109T-111T. I've decided to stop phase 1 of the sieve at 120T. There's no point in going higher than that; even at a high sieve depth, the file will be too large for NewPGen to sieve at once, and any work done from 120T and up will be useless if a megabit twin is found before that point.

Phase 2 will involve sieving 6 files for twins only: 0-20T, 20T-40T, and so on until 100T-120T. It'll start sometime next week. Once those files reach a higher sieve depth, there'll be fewer candidates, and array mode will be about the same speed as fastarray mode. The 6 files will then be merged into one giant 0-120T file, which will be sieved at once.

For those of you who're interested, there's a 40% chance that one of the k's in the 0-120T range will yield a twin.

[QUOTE=Oddball;220857]
I've decided to stop phase 1 of the sieve at 120T. There's no point in going higher than that; even at a high sieve depth, the file will be too large for NewPGen to sieve at once, and any work done from 120T and up will be useless if a megabit twin is found before that point.

Phase 2 will involve sieving 6 files for twins only: 0-20T, 20T-40T, and so on until 100T-120T. It'll start sometime next week. Once those files reach a higher sieve depth, there'll be fewer candidates, and array mode will be about the same speed as fastarray mode. The 6 files will then be merged into one giant 0-120T file, which will be sieved at once.
[/QUOTE]

Oddball,

I have already started sieving 0-20T on one core of a Core i7 @ 3.6 Ghz. This was to determine the sieve depth to leave ~4M k's remaining with a view to combining 5 such files which could still be sieved in fastarray mode. It is currently at 985 billion and removing ~29 k's per sec with 17.23 M k's remaining. I could carry on sieving this range until the removal rate reaches 0.4 k's per sec which would then set the target where fastarray mode and array mode are approx equal on this processor if this would be useful. It is currently removing about 3 M k's per day so will reach the initial target of 4M k's within a week.

Dave

100T-104T complete.

[url]http://www.sendspace.com/file/yz39ua[/url]

[QUOTE=amphoria;220861]Oddball,

I have already started sieving 0-20T on one core of a Core i7 @ 3.6 Ghz. This was to determine the sieve depth to leave ~4M k's remaining with a view to combining 5 such files which could still be sieved in fastarray mode. It is currently at 985 billion and removing ~29 k's per sec with 17.23 M k's remaining. I could carry on sieving this range until the removal rate reaches 0.4 k's per sec which would then set the target where fastarray mode and array mode are approx equal on this processor if this would be useful. It is currently removing about 3 M k's per day so will reach the initial target of 4M k's within a week.
[/QUOTE]
Sounds good. I'll start sieving the 20T-40T range.

amphoria, Oddball: do you have the merged files? Should I upload them?