2^859-1 sieving
 

After a discussion thread which came to a consensus which turned out not to be usable, I've decided to pick a number out of the air. Please finish any jobs you've agreed to run on 109!+1 before starting on this one.

2^859-1 is the smallest Mersenne number whose complete factorisation is unknown; C203 cofactor, SNFS difficulty 258.58.

[b]Reservations closed at 1030 28 May[/b]

Sieve 40M - 120M both sides; use lasieve4I15e; 1MQ a+r will take about 14 days on a 2.4GHz Core2. Polynomial is the very boring

[code]
n: 40408389115643940521033480968678506700953715205316912938887204062563858647028004670539633098136029193976662157464610911705434456944861732186510748004762758405328979466396236111507945374914053285803350311
c6: 2
c0: -1
Y1: -1
Y0: 11150372599265311570767859136324180752990208
type: snfs
skew: 0.89
rlambda: 2.6
alambda: 2.6
lpbr: 31
lpba: 31
mfbr: 62
mfba: 62
alim: 100000000
rlim: 100000000
[/code]and the upload directory is the equally predictable M859.

[B]Contributions[/B]
Xyzzy 40M-48M (done 9/5 in 1600 pieces;A 13132578, R 13961984;11.6Mcpus on ZX-81 cluster)
bsquared 48M-54M (done 19/5; A 9575224, R 10210440; 14Mcpus on K8/1400 cluster)
fivemack 54M-60M (done 26/5; A 9386197, R 9992498; 8453kcpus on various machines)
J.F. 60M-70M (done 6/5) - around 10.3Mcpus on K8/2000 cluster
fivemack 70M-71M (done 11/5) (A 1445551, R 1553368)
fivemack 71M-74M (done 1/5) (A 4396628, R 4763914)
fivemack 74M-75M (done 28/4) (A 1447669, R 1572047) (1118kcpus on C2/3000)
fivemack 75M-77M (done 8/5) (A 2897367, R 3138691) (2252kcpus on C2/3000)
fivemack 77M-78M (done 12/5) (A 1444820, R 1562767) (1128kcpus on C2/3000)
fivemack 78M-80M (done 11/5) (A 2582239, R 2805728)
J.F. 80M-81M (done 21/4) (A 1428284, R 1554945)
J.F. 81M-90M (done 28/4); 10.47Mcpus on K8/2000 cluster
batalov 90M-91M (R received 30/4, A received 2/5)
antiroach 91-92M (done 2/6)
fivemack 92M-96M (done 26/5) (A 5538324, R 5978357) (5499kcpus on Q6600 and K8/2500)
bsquared 96M-100M (arrived 29/5) (A 5483932, R 5921254) (10Ms, K8/1400 cluster)
fivemack 100M-110M (done 31/5) (A 12046700, R 13011689) (<=32 cores, various machines over about a week)
bsquared 110M-115M (done 1/6)
fivemack 115M-120M (done 2/6) (A 6444955, R 6879805) (26 cores, various machines over about five days)


[b]Counts[/b]
16 May: 39MQ, 120831808 relations. 22173399 dup, 98658409 unique. All gone by end of singleton removal.
27 May: 55MQ, 171449528 relations. 42781888 dup, 128667640 unique. 32M/36M left by end of singleton removal.

We'll take 40-48M.

How soon are you looking at having all this done?

[b]fivemack:[/b] It's about 30 CPU-months of effort, I suspect I'll be able to scare up about 30 CPUs and so finish sieving mid-May

First pancakes are on me!
Fivemack: would you please taste 'm first, before I start 81-90?

[b]fivemack:[/b] those appear to be fine pancakes, go ahead with 81-90

best packing for FTP
 

Let's revive the "best packing" topic.

[FONT=Courier New]7z[/FONT] is OK but needs installation etc etc. [FONT=Courier New]bzip2[/FONT] is definitely better than [FONT=Courier New]gzip[/FONT].
But whatever you use, I recommend the following filter (you can call it [FONT=Courier New]lc[/FONT] if you don't have a [FONT=Courier New]tr [/FONT]binary ) -- it reformats the file to lowercase letters (and digits of course):
[code]#!/usr/bin/perl
while(<>) { print lc($_); }[/code]
or use
[code]cat myRels | tr '[A-Z]' '[a-z]' | bzip2 -9c > Axx.bz2[/code]
Results (on A80-81M.bz2 file):
[code]76221762 2009-04-25 21:32 a80-81M.bz2 (this file is all lowercase)
78670955 2009-04-21 09:41 A80-81M.bz2
85365026 2009-04-25 21:22 a80-81M.gz (gzip for comparison)
[/code]
[FONT=Courier New]msieve[/FONT] doesn't need the uppercase letters in the reln files.
Neither do any other filtering programs.

[QUOTE=Batalov;170988]Let's revive the "best packing" topic.

[FONT=Courier New]7z[/FONT] is OK but needs installation etc etc. [FONT=Courier New]bzip2[/FONT] is definitely better than [FONT=Courier New]gzip[/FONT].
[/QUOTE]By "better" do you mean "uses several times the amount of computation"?

At FlyBase we ship multi-gigabyte gzipped files around. The uncompressed data is around 20GB per file.

We found that the time taken to transfer a somewhat larger gzipped file was much less than the increased time to bzip2 and bzcat the same data.

YMMV

Paul

[QUOTE=xilman;170996]We found that the time taken to transfer a somewhat larger gzipped file was much less than the increased time to bzip2 and bzcat the same data.[/QUOTE]

That is a good point that people should consider. It all depends on your transfer speed, if you get charged by the GB or have a monthly bandwidth cap, and how many processors you have available to compress/uncompress the data. 7zip get better compression than zip and the speed isn't bad either, much faster than bzip2, plus it can use multiple processors so in certain cases it would be faster than using gzip and get better compression.

The lower-case conversion in this case seems like a very fast thing to do in order to get better compression from whatever algorithm you are using.

Of course if you are going to use bzip2 and you have multiple cores, you should consider using [URL="http://compression.ca/pbzip2/"]pbzip2[/URL] which can use them.

Paul, my message was about using lowercase. (This reduces alphabet of the file and it will pack better with any compressor, even RLE. :smile:)
And I don't think anyone will argue that [FONT=Courier New]tr[/FONT] takes any appreciable time.
Everything else was already discussed before, so it was not my intention to add any oil to that fire.

[QUOTE=Batalov;171047]Paul, my message was about using lowercase.[/QUOTE]

What's the deal with uppercase in reln files, anyway. I mean, is the siever trying to tell us that some primes are WAY TOO IMPORTANT for lowercase?

And airplane food: What's the deal with airplane food? Don't they feed the jets enough when they're on the ground?

I am pretty sure that there was never any deal with it, just indifference.

Printing lowercase is a side-effect of the mpz_str_out (which can print in up to base-62 (or 64?) system, in which case it would have used all digits and letters); for OBASE 16, it prints digits and lowercase.
The rest of primes are printf'ed with "%X", so they are uppercase.
I've spoken with Jason (just in case I've missed something) and I've checked both codebases - nothing there assumes upper-lower-case differences.

Ha, just checked another thing: the line siever in msieve printfs with "%x", so all is lowercase for line-sieved rels.
There is no reason to print in hex, either (I bet pure decimals might compress better!), but it's now well used, so no reason to cha[SIZE=1](lle)[/SIZE]nge this convention.

5% better compression [I]for free[/I] sounds like a good idea to me. Everything else has its pros and cons, and I am not talking about anything else.

81-90M is finished. I was quite surprised by the hint from Batalov, and indeed: 3.0% savings of the tolower conversion before applying bzip2. Didn't do "best" bzip2 (option -9) though because I don't want to stress the cluster front-end server.

80-90M A+R took 10.47M sec on dualcore Opterons @2Ghz.

Reserving 60-70M.

[QUOTE=FactorEyes;171082]What's the deal with uppercase in reln files, anyway. I mean, is the siever trying to tell us that some primes are WAY TOO IMPORTANT for lowercase?

And airplane food: What's the deal with airplane food? Don't they feed the jets enough when they're on the ground?[/QUOTE]I've always wondered about people who think that using vacuum cleaners is worth the effort.

Paul

[QUOTE=xilman;172059]I've always wondered about people who think that using vacuum cleaners is worth the effort.[/QUOTE]

Some people are very particular about their empty spaces and want them more than averagely clean.

Hi!

Does anybody know into which numbers this composite (and other ones) splits?

Thank you!

[quote=CedricVonck;172279]Hi!

Does anybody know into which numbers this composite (and other ones) splits?

Thank you![/quote]
This database contains information on factors of numbers and certain types of sequences:
[url]http://factorization.ath.cx/[/url]
Here's its entry on this number:
[url]http://factorization.ath.cx/search.php?query=M859[/url]

60-70M done
 

I ran into the badsched bug...
Note the drop in yield for 67.5M to 68M:

[code]
A00670a: total yield: 72908, q=67050043 (0.70423 sec/rel)
A00670b: total yield: 74765, q=67100009 (0.62354 sec/rel)
A00671a: total yield: 72979, q=67150001 (0.62131 sec/rel)
A00671b: total yield: 74502, q=67200011 (0.71199 sec/rel)
A00672a: total yield: 76703, q=67250021 (0.62796 sec/rel)
A00672b: total yield: 75435, q=67300027 (0.70644 sec/rel)
A00673a: total yield: 76052, q=67350029 (0.62942 sec/rel)
A00673b: total yield: 76986, q=67400009 (0.71050 sec/rel)
A00674a: total yield: 76340, q=67450013 (0.62818 sec/rel)
A00674b: total yield: 76363, q=67500007 (0.70336 sec/rel)
A00675a: total yield: 71028, q=67550009 (0.62990 sec/rel)
A00675b: total yield: 72257, q=67600003 (0.71044 sec/rel)
A00676a: total yield: 2086, q=67650043 (5.48700 sec/rel)
A00676b: total yield: 0, q=67700011 (inf sec/rel)
A00677a: total yield: 14293, q=67750021 (1.23527 sec/rel)
A00677b: total yield: 12991, q=67800001 (1.24436 sec/rel)
A00678a: total yield: 35928, q=67850011 (0.77824 sec/rel)
A00678b: total yield: 36948, q=67900003 (0.75815 sec/rel)
A00679a: total yield: 62312, q=67950013 (0.63421 sec/rel)
A00679b: total yield: 60444, q=68000003 (0.63617 sec/rel)
[/code]Got myself the new binary from [URL="http://www.mersenneforum.org/showpost.php?p=168934&postcount=19"]here[/URL], it seems to work perfectly. I did A67.5-68 again and put those relations in a separate file.

Total time estimation: 10.3M sec. This is from summing completion times of dualcore jobs. Actual time should therefore be doubled, I guess. Even better: subtract a few percent, because when one core finishes its 50K range, it remains idle until the other core finishes.

I've been a bit slow at keeping this updated; had quite a full weekend.

We're two-thirds of the way through the sieving; can I inspire people to a swift race to the finish-line and beyond?

I'll take 48M-54M both sides.

I've got 2 machines free and I can contribute to the sieving for a couple of weeks. Can someone provide the command that needs to be ran to sieve this number? Thanks.

Assuming you have the ggnfs binaries (if not, you can get them from [URL="http://gilchrist.ca/jeff/factoring/index.html"]here[/URL]), create a poly file, say 2-859.poly and copy the [code] stuff from the first post into it. reserve a range (2 cpus for 2 weeks could probably do 1M both sides; 91M is open ...). then get into a command prompt (windows or linux shell) and type:

[code]gnfs-lasieve4I15e -r 2-859.poly -f 91000000 -c 1000000 -o 91M-92M-rat.dat[/code]

then get into another command prompt (or use & after the previous command if you're in a linux environment) and do the same command but use -a 2-859.poly instead and use a different output file name like -o 91M-92M-alg.dat. The -r and -a flags instruct ggnfs to sieve special-q on the rational vs the algebraic side.

-c controls how many special-q to do. If you need to shut down your PC, I believe the new binaries have a resume option, else, there are other ways to determine manually where it left off.

Is that enough to get you started?

Thanks bsquared! Thats perfect. I'll take 91M - 92M a+r.

Taking 96M-100M.

[QUOTE=bsquared;174162]Taking 96M-100M.[/QUOTE]

Thanks! Please PM me if you have any problems uploading; the OS on the machine was upgraded on Sunday, and I was getting 'too many connections' messages this morning which I'd not seen before.

It looks as if the duplication rate is higher than I'd expected, so we should probably go up to 120M rather than 100M. Best of luck with the sieving.

[quote=fivemack;174168]Thanks! Please PM me if you have any problems uploading; the OS on the machine was upgraded on Sunday, and I was getting 'too many connections' messages this morning which I'd not seen before.[/quote]

I was seeing those same messages last night, but this morning everything seems to be working fine. A-side has been uploaded, R is on its way (from the 48-54 reservation).

Timings:
14Msec on K8/1400: approx. total A+R time for 48-54M.

96-100 done. Took 10MQ on k8/1400. 11405186 relations.

taking 110-115.

edit2:
I'm seeing the "too many connections" error on the ftp server again. will try again in the morning.

The sysadmin on the ftp-server machine has been informed; it looks as if the connection-tracking is not noticing when some kinds of connection are closed. I suspect that he'll want to investigate further rather than simply bumping up the limit again.

In the meantime, try anonymous ftp to [i]my username[/i].dyndns.org and put the relations in directory M859. It's not as well-armoured a machine as chiark, so it will not be up indefinitely (also the partition has only 4GB free space), and it may come down rather briskly if it ends up full of warez, but it'll do for today.

Update:

I only got about 19MB uploaded before I got > Netout: Connection reset by peer.

It won't let me re-upload, saying it can't create the file.

And chiark is still refusing new connections.

An Idea for now might be [url]http://www.rapidshare.com/[/url] - there you can upload up to 200 MB.

[quote=fivemack;174955]In the meantime, try anonymous ftp to [I]my username[/I].dyndns.org and put the relations in directory M859. It's not as well-armoured a machine as chiark, so it will not be up indefinitely (also the partition has only 4GB free space), and it may come down rather briskly if it ends up full of warez, but it'll do for today.[/quote]
Would putting a username/password on it (and publishing the password here) work? That's what I do for the FTP server I run for the Aliquot Sequences team sieves, and I haven't gotten any warez (yet). :smile:

[QUOTE=bsquared;174984]Update:

I only got about 19MB uploaded before I got > Netout: Connection reset by peer.

It won't let me re-upload, saying it can't create the file.

And chiark is still refusing new connections.[/QUOTE]

I'll pester chiark's sysadmin again tomorrow: he spends Wednesday evenings rock-climbing in a town fifty miles away. Does trying to upload to the other ftp server under a different filename work?

[quote=fivemack;175018]I'll pester chiark's sysadmin again tomorrow: he spends Wednesday evenings rock-climbing in a town fifty miles away. Does trying to upload to the other ftp server under a different filename work?[/quote]


Can't seem to connect there now either:

[CODE]X:\buhrow\ggnfs\2-859>ftp *.dyndns.org
Connected to *.dyndns.org.
Connection closed by remote host.[/CODE]

* = your username

[quote=Andi47;174985]An Idea for now might be [URL]http://www.rapidshare.com/[/URL] - there you can upload up to 200 MB.[/quote]

There are just shy of 700 zipped MB of relations. I guess I could break them up into smaller chunks or something, but seems like too much of a pain. I have plenty of disk, and the relations seem to be content there for now.

If you guys can't get fivemack's server to work and need a spot for uploads, feel free to use the Aliquot sequence server I'm running at nplb-gb1.no-ip.org. Instructions for uploading can be found in any of the team sieve threads in the Aliquot Sequences forum; just replace the respective subdirectory name with "M851". :smile:

[quote=mdettweiler;175038]If you guys can't get fivemack's server to work and need a spot for uploads, feel free to use the Aliquot sequence server I'm running at nplb-gb1.no-ip.org. Instructions for uploading can be found in any of the team sieve threads in the Aliquot Sequences forum; just replace the respective subdirectory name with "M851". :smile:[/quote]

How on earth are you going to do the postprocessing? :missingteeth:

[QUOTE=bsquared;175035]Can't seem to connect there now either:

[CODE]X:\buhrow\ggnfs\2-859>ftp *.dyndns.org
Connected to *.dyndns.org.
Connection closed by remote host.[/CODE]

* = your username[/QUOTE]

My ADSL went down at midnight; the fault has been reported ...

[quote=10metreh;175047]How on earth are you going to do the postprocessing? :missingteeth:[/quote]
Nah, of course I wouldn't be doing the postprocessing...providing an FTP server doesn't always entail that. :wink: Besides, I don't think the chiark server is at fivemack's place either--correct me if I'm wrong, but I'm pretty sure he has to download them rather than having them plopped directly on one of his machines.

Actually, my nplb-gb1.no-ip.org FTP server is at a friend's place, not mine, so I don't have direct access to it, either. Everything that goes up has to come down as well. :smile:

[QUOTE=fivemack;175067]My ADSL went down at midnight; the fault has been reported ...[/QUOTE]

Suppose this isn't the best time to report another 100M relations for
12, 256+ C228? I ended up sieving 200M-260M-(a+r), 66.3M unique
from -r, 200M-250M-a done so far on the other side (so I'm working
on the last 10M-a). -Bruce

It's always good to hear of an enormous chunk of relations available; I'll be in the pub with chiark's sysadmin tonight so there's the dimmest fragment of hope of some progress in that direction by the middle of tomorrow.

My equipment is entirely dedicated to sieving 2-859 at the moment, but I can run about 1800kQ on that in 24 hours at home plus around another 900kQ/day at work and have abut 12000kQ left to do, so will be ready for the 'small' filtering job on 2^859-1 and the larger filtering job on 12^256+1 by the middle of next week.

*.dyndns.org does seem to be up again and I have managed to push a 35M file to it; you can't overwrite files which are there already, so each upload attempt needs to be under a different name.

Sysadmin successfully contacted. ftp on chiark now seems to work.

Upload quickly before the intermittent connection-hangs-forever bug happens 100 times, which took about ten days last time.

AR110-115 data is on its way to dyndns.org as chiark was giving me login problems again.

13494312 relations taking 12.5Msec on k8/1400.

May the bandwidth rise for these relations,
May the wind be always at msieve's back....

Good luck with the post-processing :)

hey fivemack, ive uploaded what ive sieved of my range. its about 0.75M

[b]fivemack:[/b]Thanks, got it and am finishing the last piece now

Finished!
 

After 31000 Core2/2.4GHz-hours-equivalent of sieving
+ 11 hours * 1 Barcelona/2.5GHz core for the linalg setup
+ 649 hours * 4 Barcelona/2.5GHz cores for linalg on
[code]
matrix is 14478333 x 14478581 (4129.3 MB) with weight 1004273913 (69.36/col)
sparse part has weight 937694692 (64.76/col)
[/code]

+ 4 hours * 80% of one Barcelona/2.5GHz core * 3 attempts for sqrt, I get

[code]
2^859-1 = 7215601 * 13183242101527799620391251382520507315529510625017 *
58609898712737781434024027899110611446341212502589792599097337 *
689446492881618336328109432708356177701201033295524648341682389467628713061286698944336488056955742457364564837248234865096219153030243215903
[/code]

where the two small factors were already known and the two larger factors are new.

Matrix time on quad Barcelona continues to fit quite nicely the curve T = 1.5 hours * (matrix columns in millions)^2.3

Congratulation @ all! Good work
:party::groupwave::curtisc:

Congrats to all involved (which doesn't include me) for factoring the smallest remaining Mersenne number!
:party:
:bow wave:
:groupwave:
I've added the new factors to Syd's factoring DB. [URL="http://factorization.ath.cx/search.php?id=1788"]c259[/URL] = p7*p50*p62*p141
Going to take a whack at M863 next?
How does this factor get added to PrimeNet v5 and properly credited? [url]http://www.mersenne.org/report_factors/?exp_lo=859&exp_hi=&exp_date=&fac_len=&dispdate=1&B1=Get+Factors[/url]

We're currently attacking M877, since I like alternating GNFS and SNFS runs; come to the neighbouring thread and join us! One million Q takes about eight days on one core of a 2.4GHz Core2 running 64-bit Linux, probably about twice that if you're using Windows; 133 million Qs remain unclaimed.