What is a quick way to "rule out" 10mil digit numbers?

Moloch · 2004-03-27, 22:58

I'm trying to find a 10 million digit mersenne prime, but i've noticed there are a lot of number in the range of M33,000,000 to infinity.
I have about 10 numbers in mind that i'd like to start with in the M42,000,000 range. What would be the fastest way to check for primality (or non-primality)? LL says it will take about 36 days to test each exponent. A year is a bit long for testing only 10 numbers...

I started prime95 factoring one the numbers to 2^69 last night(i'm not really sure what exacly this is even doing; is trying to prove the number is not prime by finding a factor?), and it did 2^65, 2^66, 2^67, and 10% of 2^68 in about 8 hours. Assuming this is about 1/4 through, it should only take about 32 hours to test each number. Quite a bit faster, but what kind of results do i get from "factoring"? Will this rule out some numbers so I dont have to spend 36 days LL testing them?

The setup for "factoring" with prime 95:
worktodo.ini:
Factor=42018157,64
primi.ini:
FactorOverride=69
WellBehavedWork=1

is this even set up right? (I'm n00b to prime95, any help is welcome)

Uncwilly · 2004-03-28, 00:43

The factoring trys to eliminate numbers by looking for small (relativly) factors. What ever the preset limit is is worth the time put into based on experience. The next step of P-1 factoring uses a different scheme that again is worth the effort. Depending on a few things (your memory and the numbers) you may have 50% chance of killing off 1 number through Trial Factorin and P-1.

L-L is the fastest method and P95 is the fastest program for PC's. 36 days each is actually quick, very quick.

How did you choose your numbers, the start and ending limits for Factoring?

Moloch · 2004-03-28, 02:01

I built my computer more for gaming than p95, but until the new games come out I can run p95 in the background and still play games very smoothly. Its running at 3450mhz stable right now. I'm saving up to get a Vapochill Lightspeed AC. Under a 100% load your p4 chip will run at a chill -25.5°C. So now that 3.0ghz can overclock to ~5.0ghz.

The numbers I'm using came from an older post where some guys came up with an MP probability zone chart. They predicted M39? extremely close (although they did predict M39 to be M40). If you take the center of their range for M39 (13430227-13501387), you get 13465807 which is exactly 1110 away from the actual number. Pretty damn close if you ask me.

I wish I knew how they made their original prediction. Then I might be able to find where the extra 1110 came from and make a more accurate prediction for "M43". So I figure while I'm trying to find some better numbers, their range for "M43" at 41976841-42057331 is a good place to start.

Back to my question, is factoring to 2^69 going to eliminate some of the 10 numbers I'm looking at? By 50% did you mean 50% chance of eliminating each number, or 50% of getting 1 out of the 10 numbers?

Also, am I doing the factoring right? I've never done this before, so I'm not really sure its doing anything. Its not done yet so of course I cant see any results. Should I factor all the way out to 2^69, or would it catch most of them if I only went to 2^67 or 2^68?

Is there a faster way to do the factoring? You mentioned P-1, how do I set up for that one? I saw it in the P95 menu, but I'm not sure what I would set the bounds at.

Uncwilly · 2004-03-28, 02:58

Based upon the recent Nofactor.zip The first 10 exponents in your range have been TrialFactored to 69 bits. Here is what I get.

Code:

Test=41976841,69
Test=41977009,69
Test=41977121,69
Test=41977141,69
Test=41977241,69
Test=41977279,69
Test=41977291,69
Test=41977319,69
Test=41977337,69
Test=41977343,69
Test=41977357,69

And from the P95 help file, 69 bits is ad far as it is worth taking it with TF's.

If you change the Test in the lines above to PFactor you can force P95 to only do P-1 factoring. Then after you submit the results, you can test those that had no factor found.

P-1 is a different method that can find a factor. Doing only P-1 (since the TF is done) you may expect that there is about a 25% chance of 1 out of you 10 exponents being successfully P-1 factored (eliminated).

Currently there are a large number of other exponents in the range that you quoted.

Also, M39 has not been proved to be M39. It could be M40....

Moloch · 2004-03-28, 04:02

I think I'm starting to get it now.. so if i use decomp.exe with the nofactor.cmp file and it doesnt output some of the prime numbers that should be there, does that mean it has already been factored?

To make my list I used "decomp -w 4201xxxx 4201xxxx" and there were a few numbers that I had listed from a sieve that werent in the nofactor output file (worktodo.ini). Should I check the extra numbers the sieve spit out, or do those already have known factors?

Does p-1 go about the same speed as trial factoring? Right now I'm getting about 10% an hour for M42018157 at 2^68, and I suspect I will only get about 10% every 2-3 hours if I do 2^69.

Uncwilly · 2004-03-28, 04:51

Quote:

Originally Posted by Moloch

I think I'm starting to get it now.. so if i use decomp.exe with the nofactor.cmp file and it doesnt output some of the prime numbers that should be there, does that mean it has already been factored?

Correct, the ones in nofactor.cmp are those that remain after having had some factoring done to them. (The first 1-55 bits get a lot).

Quote:

Originally Posted by Moloch

To make my list I used "decomp -w 4201xxxx 4201xxxx" and there were a few numbers that I had listed from a sieve that werent in the nofactor output file (worktodo.ini). Should I check the extra numbers the sieve spit out, or do those already have known factors

No, don't check them, they should be found in the factors.cmp

Quote:

Originally Posted by Moloch

Does p-1 go about the same speed as trial factoring? Right now I'm getting about 10% an hour for M42018157 at 2^68, and I suspect I will only get about 10% every 2-3 hours if I do 2^69.

It is a different beast. I personally don't know about the speed of P-1 up in that range. RAM made available to P95 during this time can increase your chances of finding a factor.

You may want to add:
SequentialWorkToDo=0

to your prime.ini. See the help file for more about it.

BTW, be sure to report your results, so somebody else doesn't repeat it.

Uncwilly · 2004-03-28, 05:07

Also, kinda important. I poked around and it appears that others are working in this range (they may not have posted their latest results...).

See this thread:
http://www.mersenneforum.org/showthread.php?t=1839

and in this one:
http://www.mersenneforum.org/showthread.php?t=384
I see that someone is working up in that range.

Quote:

03-04-09 39.5M 40M norbert Factoring to 2^60
03-03-05 41,976,841 42,057,331 wackyeh Factoring to 2^69, P-1
03-20-16 43M 44M antiroach Factoring to 2^62

You may want to co-ordinate with those involved. Hopefully you folks are successful.

Complex33 · 2004-03-28, 05:27

The following have already been tested:
41976841,Net_Force,MFalcon,WY1,00000000
41977141,Net_Force,MFalcon,WY1,00000000
41977241,Net_Force,Butterfly,WY1,00000000
41977279,Net_Force,MFalcon,WY1,00000000
41977337,Net_Force,Butterfly,WY1,00000000
41977343,Net_Force,Butterfly,WY1,00000000
41977357,Net_Force,Butterfly,WY1,00000000

I would suggest before you jump head long into this to do a couple of things. First I would have your machine complete 5 to 10 double checks to ensure it can produce consistant resuslts. After that I would choose the numbers you wish to test and email George so you can get them assigned to you on Primenet. And finally I would set up your worktodo with Test=xxx,bit and let Prime95 perform all the default factoring and P-1 work. It will coordinate the bit depths and factoring bounds based on available resources and the odds of finding a factor to maximize throughput.

Good Luck

Moloch · 2004-03-28, 05:29

So P-1 is very ram intensive? I have a gig of ram running at 920mhz, I dont think that will be much of a problem. Does it matter if I do the P-1, or TF first?

I'm not expecting to really find much in the 42.0 million range. I'm more interested around 33.55 and/or 38.55 million, but I have quite a bit more number crunching before I will have to any specific numbers to test.

Moloch · 2004-03-28, 05:56

I have done some testing to make sure my system is working. I had a few rounding and sumout errors that I fixed by adjusting my ram timings. Since then it has passed the torture tests, and has been running continually error-free for over 48 hours (hasnt been turned off for 3 days). I have run LL tests on M44497, M216091, and M756829, with results below. I know the prime-prime-not prime is accurate, but I'm not sure what those other numbers mean. Feel free to check them out.

[Fri Mar 26 01:04:16 2004]
UID: S181600/CF671E708, M44497 is prime! WZ1: C70CEE73,00000000
UID: S181600/CF671E708, M216091 is prime! WZ1: 8368E9FF,00000000
[Fri Mar 26 01:18:23 2004]
UID: S181600/CF671E708, M756829 is not prime. Res64: 6BBC571BB575B317. WZ1: 6EFD8977,188420,00000000

2004-03-27, 22:58	#1
Moloch Mar 2004 2³·3 Posts	What is a quick way to "rule out" 10mil digit numbers? I'm trying to find a 10 million digit mersenne prime, but i've noticed there are a lot of number in the range of M33,000,000 to infinity. I have about 10 numbers in mind that i'd like to start with in the M42,000,000 range. What would be the fastest way to check for primality (or non-primality)? LL says it will take about 36 days to test each exponent. A year is a bit long for testing only 10 numbers... I started prime95 factoring one the numbers to 2^69 last night(i'm not really sure what exacly this is even doing; is trying to prove the number is not prime by finding a factor?), and it did 2^65, 2^66, 2^67, and 10% of 2^68 in about 8 hours. Assuming this is about 1/4 through, it should only take about 32 hours to test each number. Quite a bit faster, but what kind of results do i get from "factoring"? Will this rule out some numbers so I dont have to spend 36 days LL testing them? The setup for "factoring" with prime 95: worktodo.ini: Factor=42018157,64 primi.ini: FactorOverride=69 WellBehavedWork=1 is this even set up right? (I'm n00b to prime95, any help is welcome)

2004-03-28, 02:01	#3
Moloch Mar 2004 2³·3 Posts	I built my computer more for gaming than p95, but until the new games come out I can run p95 in the background and still play games very smoothly. Its running at 3450mhz stable right now. I'm saving up to get a Vapochill Lightspeed AC. Under a 100% load your p4 chip will run at a chill -25.5°C. So now that 3.0ghz can overclock to ~5.0ghz. The numbers I'm using came from an older post where some guys came up with an MP probability zone chart. They predicted M39? extremely close (although they did predict M39 to be M40). If you take the center of their range for M39 (13430227-13501387), you get 13465807 which is exactly 1110 away from the actual number. Pretty damn close if you ask me. I wish I knew how they made their original prediction. Then I might be able to find where the extra 1110 came from and make a more accurate prediction for "M43". So I figure while I'm trying to find some better numbers, their range for "M43" at 41976841-42057331 is a good place to start. Back to my question, is factoring to 2^69 going to eliminate some of the 10 numbers I'm looking at? By 50% did you mean 50% chance of eliminating each number, or 50% of getting 1 out of the 10 numbers? Also, am I doing the factoring right? I've never done this before, so I'm not really sure its doing anything. Its not done yet so of course I cant see any results. Should I factor all the way out to 2^69, or would it catch most of them if I only went to 2^67 or 2^68? Is there a faster way to do the factoring? You mentioned P-1, how do I set up for that one? I saw it in the P95 menu, but I'm not sure what I would set the bounds at. Last fiddled with by Moloch on 2004-03-28 at 02:09

2004-03-28, 02:58	#4
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 3·7·17·31 Posts	Based upon the recent Nofactor.zip The first 10 exponents in your range have been TrialFactored to 69 bits. Here is what I get. Code: Test=41976841,69 Test=41977009,69 Test=41977121,69 Test=41977141,69 Test=41977241,69 Test=41977279,69 Test=41977291,69 Test=41977319,69 Test=41977337,69 Test=41977343,69 Test=41977357,69 And from the P95 help file, 69 bits is ad far as it is worth taking it with TF's. If you change the Test in the lines above to PFactor you can force P95 to only do P-1 factoring. Then after you submit the results, you can test those that had no factor found. P-1 is a different method that can find a factor. Doing only P-1 (since the TF is done) you may expect that there is about a 25% chance of 1 out of you 10 exponents being successfully P-1 factored (eliminated). Currently there are a large number of other exponents in the range that you quoted. Also, M39 has not been proved to be M39. It could be M40....

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really.	CRGreathouse	Number Theory Discussion Group	51	2018-12-16 21:55
NFS@Home "Status of numbers" page to update	pinhodecarlos	NFS@Home	2	2015-07-04 11:18
Looking for PrimeKit from "Prime Numbers A Computational Perspective"	gszpetkowski	Factoring	13	2014-08-05 11:57
Will the Microsoft release "rule" be broken with Windows 9?	jasong	jasong	7	2014-03-20 06:01
"On factors of Mersenne numbers" - Seiji Tomita	cheesehead	Math	6	2009-12-15 17:45

2004-03-28, 00:43	#2
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 3×7×17×31 Posts	The factoring trys to eliminate numbers by looking for small (relativly) factors. What ever the preset limit is is worth the time put into based on experience. The next step of P-1 factoring uses a different scheme that again is worth the effort. Depending on a few things (your memory and the numbers) you may have 50% chance of killing off 1 number through Trial Factorin and P-1. L-L is the fastest method and P95 is the fastest program for PC's. 36 days each is actually quick, very quick. How did you choose your numbers, the start and ending limits for Factoring?

2004-03-28, 04:02	#5
Moloch Mar 2004 2³·3 Posts	I think I'm starting to get it now.. so if i use decomp.exe with the nofactor.cmp file and it doesnt output some of the prime numbers that should be there, does that mean it has already been factored? To make my list I used "decomp -w 4201xxxx 4201xxxx" and there were a few numbers that I had listed from a sieve that werent in the nofactor output file (worktodo.ini). Should I check the extra numbers the sieve spit out, or do those already have known factors? Does p-1 go about the same speed as trial factoring? Right now I'm getting about 10% an hour for M42018157 at 2^68, and I suspect I will only get about 10% every 2-3 hours if I do 2^69.

2004-03-28, 05:27	#8
Complex33 Aug 2002 Texas 5×31 Posts	The following have already been tested: 41976841,Net_Force,MFalcon,WY1,00000000 41977141,Net_Force,MFalcon,WY1,00000000 41977241,Net_Force,Butterfly,WY1,00000000 41977279,Net_Force,MFalcon,WY1,00000000 41977337,Net_Force,Butterfly,WY1,00000000 41977343,Net_Force,Butterfly,WY1,00000000 41977357,Net_Force,Butterfly,WY1,00000000 I would suggest before you jump head long into this to do a couple of things. First I would have your machine complete 5 to 10 double checks to ensure it can produce consistant resuslts. After that I would choose the numbers you wish to test and email George so you can get them assigned to you on Primenet. And finally I would set up your worktodo with Test=xxx,bit and let Prime95 perform all the default factoring and P-1 work. It will coordinate the bit depths and factoring bounds based on available resources and the odds of finding a factor to maximize throughput. Good Luck

2004-03-28, 05:29	#9
Moloch Mar 2004 30₈ Posts	So P-1 is very ram intensive? I have a gig of ram running at 920mhz, I dont think that will be much of a problem. Does it matter if I do the P-1, or TF first? I'm not expecting to really find much in the 42.0 million range. I'm more interested around 33.55 and/or 38.55 million, but I have quite a bit more number crunching before I will have to any specific numbers to test.

2004-03-28, 05:56	#10
Moloch Mar 2004 2³·3 Posts	I have done some testing to make sure my system is working. I had a few rounding and sumout errors that I fixed by adjusting my ram timings. Since then it has passed the torture tests, and has been running continually error-free for over 48 hours (hasnt been turned off for 3 days). I have run LL tests on M44497, M216091, and M756829, with results below. I know the prime-prime-not prime is accurate, but I'm not sure what those other numbers mean. Feel free to check them out. [Fri Mar 26 01:04:16 2004] UID: S181600/CF671E708, M44497 is prime! WZ1: C70CEE73,00000000 UID: S181600/CF671E708, M216091 is prime! WZ1: 8368E9FF,00000000 [Fri Mar 26 01:18:23 2004] UID: S181600/CF671E708, M756829 is not prime. Res64: 6BBC571BB575B317. WZ1: 6EFD8977,188420,00000000