PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : A New Sieve? Or just Smoking my Socks!?!

Author Message
Profile SteveRCProject donor
Avatar
Send message
Joined: 22 Mar 10
Posts: 149
ID: 57364
Credit: 461,201,676
RAC: 13,794
Discovered 1 mega primeEliminated 2 conjecture "k"s321 LLR Turquoise: Earned 5,000,000 credits (5,306,247)Cullen LLR Turquoise: Earned 5,000,000 credits (5,756,791)ESP LLR Turquoise: Earned 5,000,000 credits (6,048,277)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (4,688,089)PPS LLR Jade: Earned 10,000,000 credits (17,756,351)PSP LLR Jade: Earned 10,000,000 credits (10,908,511)SoB LLR Jade: Earned 10,000,000 credits (12,428,680)SR5 LLR Jade: Earned 10,000,000 credits (11,522,219)SGS LLR Jade: Earned 10,000,000 credits (13,536,986)TRP LLR Jade: Earned 10,000,000 credits (10,513,978)Woodall LLR Turquoise: Earned 5,000,000 credits (6,452,373)321 Sieve (suspended) Silver: Earned 100,000 credits (246,534)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (6,474,263)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (25,971,807)PPS Sieve Double Bronze: Earned 100,000,000 credits (120,732,256)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,557,924)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,896,883)AP 26/27 Jade: Earned 10,000,000 credits (13,596,609)GFN Double Bronze: Earned 100,000,000 credits (160,719,016)WW Gold: Earned 500,000 credits (720,000)PSA Turquoise: Earned 5,000,000 credits (6,367,890)
Message 151381 - Posted: 4 Sep 2021 | 13:15:37 UTC
Last modified: 4 Sep 2021 | 13:34:49 UTC

I was thinking about Mersenne numbers, wondering what a 'trial-division' table of Mersenne numbers divided by Prime numbers (M MOD P) would look like, so I set up a spreadsheet
https://docs.google.com/spreadsheets/d/1-rJiHZZA-pIp9SRloIZ5p9sqhK2h9Pki/edit?usp=sharing&ouid=109422053006376628543&rtpof=true&sd=true
to try visualize it better.. I was amazed to see the remainders in the columns under the primes were all periodic, with periods(Pd) always less than the Prime numbers themselves..
Excel integers can only calc up to M(52) directly, so I changed the formula at this point to allow calc up to M(104) to enable calc of periods of primes up to 101..
I thought at first no two periods would be the same, but primes 23 and 89 both have Mersenne-Periods of 11!

It occurred to me that this 'periodic-nature' would provide a quick and simple way to sieve big Mersenne numbers using 'n' directly, without ever having to calculate, or work with, (2^n-1)...
So I added a second table under the first, but now instead of calculating (M MOD P), we simply calculate (n MOD Pd)-1 and we get the same zeros (marking composites) in the same places as the upper table! But now 'n' can be as large as we like without any overflow problems!
Seems to me it would be child's play to calculate those Mersenne-Periods for the first few hundred-thousand prime numbers,(sorted and with duplicates removed!) then for each P you only need to calc (n MOD Pd) for the first one of an arbitrarily-large block of Mersenne-exponents (starting wherever u like!), and then just go thru the block, 'crossing-out' every Pd'th exponent in standard Eristothanes-fasion!!
Now I'm a Pretty Good Programmer, but a Lousy Mathematician, so I'll leave it up to those who don't just get a headache like me when trying to understand the concepts behind the maths we use to find these numbers, to punch holes, or explain to me why this is not the way we should do it!!
Or perhaps this (or something even faster) is already being done, but takes a lot longer than I think it should!?! (and what about GFN's? Do they exhibit the same properties??)

Edit: Just noticed Google-Docs number-resolution much crappier than the Open-Office spreadsheet I used!! - will post a fixed sheet for Docs shortly..!!
____________

Profile NickProject donor
Avatar
Send message
Joined: 11 Jul 11
Posts: 1846
ID: 105020
Credit: 4,898,673,882
RAC: 15,418,190
Discovered 9 mega primesFound 5 primes in the 2020 Tour de PrimesFound 2 mega primes in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 2 mega primes in the 2021 Tour de PrimesFound 3 primes in the 2022 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (23,436,311)Cullen LLR Emerald: Earned 50,000,000 credits (50,743,293)ESP LLR Emerald: Earned 50,000,000 credits (50,849,415)Generalized Cullen/Woodall LLR Emerald: Earned 50,000,000 credits (50,473,530)PPS LLR Emerald: Earned 50,000,000 credits (75,402,242)PSP LLR Emerald: Earned 50,000,000 credits (51,069,305)SoB LLR Emerald: Earned 50,000,000 credits (51,885,310)SR5 LLR Sapphire: Earned 20,000,000 credits (40,443,486)SGS LLR Sapphire: Earned 20,000,000 credits (20,482,069)TRP LLR Sapphire: Earned 20,000,000 credits (20,307,419)Woodall LLR Emerald: Earned 50,000,000 credits (51,058,101)321 Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,380,527)Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (744,531)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,007,004)PPS Sieve Double Gold: Earned 500,000,000 credits (631,166,032)TRP Sieve (suspended) Bronze: Earned 10,000 credits (21,181)AP 26/27 Emerald: Earned 50,000,000 credits (50,339,393)GFN Double Gold: Earned 500,000,000 credits (591,721,141)WW Double Ruby: Earned 2,000,000,000 credits (3,113,436,000)
Message 151382 - Posted: 4 Sep 2021 | 14:45:28 UTC

I briefly looked into the phenomena that a small proportion does a lot of it.
It may be a pareto distribution except I remember a different name.
Ah, I remember more.
The sqrt of the number of people do half the work.
This is not problematic until you get to the size of say 10,000 people working in your company.
What I did was compare - as an example 10,000 vs taking away 'the first lot' and then going again. The ratio between them was 1. It was so close to one it was uncanny. Why?
At the most extreme it didn't ever got to 2 - whatever numbers I plugged in.

The problem is this:
A = The sqrt of the number of people do half the work.
B = Take the sqrt of that number away and you have the next level of people to consider.
C = The sqrt of that number of people do half the work, etc.

A/C = 1 (so close to it - always)

I am really sorry if I have stated this incorrectly. I know what I found. It is probably trivial. And I don't have my head around this right now.

Profile SteveRCProject donor
Avatar
Send message
Joined: 22 Mar 10
Posts: 149
ID: 57364
Credit: 461,201,676
RAC: 13,794
Discovered 1 mega primeEliminated 2 conjecture "k"s321 LLR Turquoise: Earned 5,000,000 credits (5,306,247)Cullen LLR Turquoise: Earned 5,000,000 credits (5,756,791)ESP LLR Turquoise: Earned 5,000,000 credits (6,048,277)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (4,688,089)PPS LLR Jade: Earned 10,000,000 credits (17,756,351)PSP LLR Jade: Earned 10,000,000 credits (10,908,511)SoB LLR Jade: Earned 10,000,000 credits (12,428,680)SR5 LLR Jade: Earned 10,000,000 credits (11,522,219)SGS LLR Jade: Earned 10,000,000 credits (13,536,986)TRP LLR Jade: Earned 10,000,000 credits (10,513,978)Woodall LLR Turquoise: Earned 5,000,000 credits (6,452,373)321 Sieve (suspended) Silver: Earned 100,000 credits (246,534)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (6,474,263)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (25,971,807)PPS Sieve Double Bronze: Earned 100,000,000 credits (120,732,256)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,557,924)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,896,883)AP 26/27 Jade: Earned 10,000,000 credits (13,596,609)GFN Double Bronze: Earned 100,000,000 credits (160,719,016)WW Gold: Earned 500,000 credits (720,000)PSA Turquoise: Earned 5,000,000 credits (6,367,890)
Message 151383 - Posted: 4 Sep 2021 | 14:56:27 UTC - in response to Message 151382.
Last modified: 4 Sep 2021 | 15:04:20 UTC

No idea what yr post has to do with my stuff, Nick! Did u post to the correct thread?

Anyway, here is a slightly better spreadsheet for Docs.. (but still conks out before M(100)!)

But anyway, the important stuff is at the bottom half of the spreadsheet, which has no problems with overflow!!

https://docs.google.com/spreadsheets/d/1jSyORkSbdNUweq6JFybXaUCT3oNugGzW/edit?usp=sharing&ouid=109422053006376628543&rtpof=true&sd=true
____________

Profile NickProject donor
Avatar
Send message
Joined: 11 Jul 11
Posts: 1846
ID: 105020
Credit: 4,898,673,882
RAC: 15,418,190
Discovered 9 mega primesFound 5 primes in the 2020 Tour de PrimesFound 2 mega primes in the 2020 Tour de PrimesFound 4 primes in the 2021 Tour de PrimesFound 2 mega primes in the 2021 Tour de PrimesFound 3 primes in the 2022 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (23,436,311)Cullen LLR Emerald: Earned 50,000,000 credits (50,743,293)ESP LLR Emerald: Earned 50,000,000 credits (50,849,415)Generalized Cullen/Woodall LLR Emerald: Earned 50,000,000 credits (50,473,530)PPS LLR Emerald: Earned 50,000,000 credits (75,402,242)PSP LLR Emerald: Earned 50,000,000 credits (51,069,305)SoB LLR Emerald: Earned 50,000,000 credits (51,885,310)SR5 LLR Sapphire: Earned 20,000,000 credits (40,443,486)SGS LLR Sapphire: Earned 20,000,000 credits (20,482,069)TRP LLR Sapphire: Earned 20,000,000 credits (20,307,419)Woodall LLR Emerald: Earned 50,000,000 credits (51,058,101)321 Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,380,527)Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (744,531)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,007,004)PPS Sieve Double Gold: Earned 500,000,000 credits (631,166,032)TRP Sieve (suspended) Bronze: Earned 10,000 credits (21,181)AP 26/27 Emerald: Earned 50,000,000 credits (50,339,393)GFN Double Gold: Earned 500,000,000 credits (591,721,141)WW Double Ruby: Earned 2,000,000,000 credits (3,113,436,000)
Message 151385 - Posted: 4 Sep 2021 | 15:22:30 UTC - in response to Message 151383.

I am sorry about this - I read your post and considered that I have found something to think about. The only connection was ideas.

Profile SteveRCProject donor
Avatar
Send message
Joined: 22 Mar 10
Posts: 149
ID: 57364
Credit: 461,201,676
RAC: 13,794
Discovered 1 mega primeEliminated 2 conjecture "k"s321 LLR Turquoise: Earned 5,000,000 credits (5,306,247)Cullen LLR Turquoise: Earned 5,000,000 credits (5,756,791)ESP LLR Turquoise: Earned 5,000,000 credits (6,048,277)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (4,688,089)PPS LLR Jade: Earned 10,000,000 credits (17,756,351)PSP LLR Jade: Earned 10,000,000 credits (10,908,511)SoB LLR Jade: Earned 10,000,000 credits (12,428,680)SR5 LLR Jade: Earned 10,000,000 credits (11,522,219)SGS LLR Jade: Earned 10,000,000 credits (13,536,986)TRP LLR Jade: Earned 10,000,000 credits (10,513,978)Woodall LLR Turquoise: Earned 5,000,000 credits (6,452,373)321 Sieve (suspended) Silver: Earned 100,000 credits (246,534)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (6,474,263)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (25,971,807)PPS Sieve Double Bronze: Earned 100,000,000 credits (120,732,256)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,557,924)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,896,883)AP 26/27 Jade: Earned 10,000,000 credits (13,596,609)GFN Double Bronze: Earned 100,000,000 credits (160,719,016)WW Gold: Earned 500,000 credits (720,000)PSA Turquoise: Earned 5,000,000 credits (6,367,890)
Message 151405 - Posted: 6 Sep 2021 | 7:01:28 UTC

After making a new (fully expandable!) spreadsheet and writing a little VB program..
https://drive.google.com/drive/folders/1FajFZiDTw1kbqWBi4PtqNiKKDUmAHpSy?usp=sharing

I have come to the conclusion this approach will probably just amount to sieving out the non-prime exponents when they are fairly big... so maybe not that hugely useful... But interesting nonetheless!

Also quite impressed with this code that calculates the first 1M primes and sieves out the first 10M Mersenne-exponents, which got to about 600k primes sieved while I was asleep last night!
Not bad for a few lines of Windows-forms VB code! - But I'm sure those with their heads more in the Maths (Yves!?!) and some super-efficient C++, could do a MUCH better job!!
____________

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 407,815,873
RAC: 10,359
321 LLR Ruby: Earned 2,000,000 credits (2,092,823)Cullen LLR Ruby: Earned 2,000,000 credits (2,315,295)ESP LLR Ruby: Earned 2,000,000 credits (2,151,088)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,620,968)PPS LLR Jade: Earned 10,000,000 credits (10,943,107)PSP LLR Ruby: Earned 2,000,000 credits (2,064,832)SoB LLR Ruby: Earned 2,000,000 credits (2,434,466)SR5 LLR Ruby: Earned 2,000,000 credits (2,065,004)SGS LLR Ruby: Earned 2,000,000 credits (2,027,649)TRP LLR Ruby: Earned 2,000,000 credits (2,089,856)Woodall LLR Ruby: Earned 2,000,000 credits (2,112,258)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Turquoise: Earned 5,000,000 credits (5,096,952)AP 26/27 Turquoise: Earned 5,000,000 credits (5,797,662)GFN Jade: Earned 10,000,000 credits (10,874,159)WW Double Silver: Earned 200,000,000 credits (349,980,000)PSA Amethyst: Earned 1,000,000 credits (1,042,601)
Message 151421 - Posted: 7 Sep 2021 | 5:53:03 UTC - in response to Message 151381.

Maybe I got you completely wrong since I'm not a Math guy, but isn't that periodicity just due to Fermat's little theorem? If so, it's already used a lot by GIMPS to make finding factors via trial division and P-1 easier.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

Post to thread

Message boards : General discussion : A New Sieve? Or just Smoking my Socks!?!

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2022 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.35, 1.71, 1.71
Generated 4 Jul 2022 | 3:07:18 UTC