Other

drummers-lowrise

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

 Post to thread Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
SteveRC

Joined: 22 Mar 10
Posts: 149
ID: 57364
Credit: 461,201,676
RAC: 13,794

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
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..!!
____________

Nick

Joined: 11 Jul 11
Posts: 1846
ID: 105020
Credit: 4,898,673,882
RAC: 15,418,190

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.

SteveRC

Joined: 22 Mar 10
Posts: 149
ID: 57364
Credit: 461,201,676
RAC: 13,794

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!!

____________

Nick

Joined: 11 Jul 11
Posts: 1846
ID: 105020
Credit: 4,898,673,882
RAC: 15,418,190

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.

SteveRC

Joined: 22 Mar 10
Posts: 149
ID: 57364
Credit: 461,201,676
RAC: 13,794

Message 151405 - Posted: 6 Sep 2021 | 7:01:28 UTC

After making a new (fully expandable!) spreadsheet and writing a little VB program..

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!!
____________

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 407,815,873
RAC: 10,359

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

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