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 : Prime Number Search Method

Author Message
archeye
Send message
Joined: 16 Jan 13
Posts: 6
ID: 189852
Credit: 1,780,674
RAC: 6
Cullen LLR Bronze: Earned 10,000 credits (18,092)Woodall LLR Bronze: Earned 10,000 credits (37,607)GFN Amethyst: Earned 1,000,000 credits (1,712,534)
Message 131021 - Posted: 10 Jul 2019 | 20:39:03 UTC

Hi,
So maybe you may want to push me into the math stupid category but really we all need to start somewhere ;)

After running 1 x Cullen and 2 x Woodall CPU tasks to completion I started to think about how I would go about searching for a prime number.

Maybe it is explained somewhere on the site how a WU (task) is organised but I did not find such descriptions so I came up with my own methodology.

Prime Number Search Criteria

I define candidate number as a number that shall be tested as a prime number.

Scope of the candidate number.

Candidate number is greater than 10 and this increases to be the next known sequential prime number + 1.
(Basically the latest sequential prime plus 1 (then continual plus 1 until next prime found))

Numbers to ignore are; ("non useful numbers")

ends in an even number (0, 2, 4, 6, 8)

ends in a 5

Also multiples of a known prime number will be ignored.

This leaves numbers to be checked that would end in,

1, 3, 7, 9

Divisors for these numbers cannot be

An even number

A 5 or any multiple of 5

There is no purpose using a divisor of 0, or 1 or the candidate number itself


Algorithm (in text form)

Candidate number is (10 or (if higher) the latest known sequential prime number) + 1

(1) if (candidate number is greater than 10) and not
(an even number) and not
(least significant digit is 5) and not
(a multiple of a lower value prime number) then

sequentially divide this candidate number by the following numbers

3, 7, 9

if the division has a decimal component for all 3 divisors then

the number is prime

else increment candidate number by 1 and try again

I believe it would be very easy to generate a list of "non useful numbers" to test and then just send out tasks for the numbers that match the condition (1) above.

Why should some Primegrid tasks take such a long time? It does not make sense to me.

Perhaps I miss something significant and if so then please tell me straight as I am always open for learning :)

Thanks

Profile Crun-chiProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Nov 09
Posts: 2793
ID: 50683
Credit: 52,558,486
RAC: 53
Eliminated 1 conjecture "k"Found 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Ruby: Earned 2,000,000 credits (2,982,840)PSP LLR Silver: Earned 100,000 credits (104,385)SoB LLR Silver: Earned 100,000 credits (106,117)SR5 LLR Silver: Earned 100,000 credits (139,802)SGS LLR Amethyst: Earned 1,000,000 credits (1,073,792)TRP LLR Silver: Earned 100,000 credits (122,712)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve Silver: Earned 100,000 credits (104,900)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,599)Generalized Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (515,556)PPS Sieve Jade: Earned 10,000,000 credits (11,343,583)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,575,874)GFN Sapphire: Earned 20,000,000 credits (23,247,434)PSA Turquoise: Earned 5,000,000 credits (7,522,050)
Message 131023 - Posted: 10 Jul 2019 | 20:48:34 UTC - in response to Message 131021.
Last modified: 10 Jul 2019 | 20:49:51 UTC

I believe it would be very easy to generate a list of "non useful numbers" to test and then just send out tasks for the numbers that match the condition (1) above.



Primgrid is like big self-sustained organism. :)
You explain sieving : process that will be eliminate all candidates that can be divided with any other number then 1 and yourself. If candidate can be divided with third number it cannot be prime.
So after this process is done you got list of candidates and those candidates are sent to users to finally check is candidate prime or not


Why should some Primegrid tasks take such a long time? It does not make sense to me.


Primegrid search for primes in range from 380.000 digits to 24.000.000 digits. So now you understand why for some candidates you need more time then for others.

Cullen and Woodall are example of long task. PPSE is example of short tasks
____________
314187728^131072+1 GENERALIZED FERMAT :)
93*10^1029523-1 REPDIGIT PRIME
31*332^367560+1 CRUS PRIME
Proud member of team Aggie The Pew. Go Aggie!

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 964
ID: 306875
Credit: 11,356,014
RAC: 9,983
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (184,660)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 131036 - Posted: 11 Jul 2019 | 8:15:27 UTC - in response to Message 131021.


sequentially divide this candidate number by the following numbers

3, 7, 9

if the division has a decimal component for all 3 divisors then

the number is prime



I think you are too focused on decimal representation.

There is no need to trial divide by 9, because if you already know 3 does not divide, then certainly 9 will not divide either.

You cannot stop after 9 (or 7), of course. Candidates such as 121 or 143 are not prime, even though they end in a "legal" decimal digit and are not divisible by any single-digit number (i.e. the primes 2, 3, 5, 7 are not sufficient to prove that 121 (or 143 etc.) has a factor).

The methods you consider here, work, when done correctly, but are very very very inefficient when it comes to big numbers.

Consider a number with 50 digits, say:

77230846651917257282881737242736965043155981238583

Your methods will not be efficient enough to determine whether this number is prime.

Now, PrimeGrid considers much larger numbers. Instead of 50 digits, it may be 1000000 digits. But only specially "simple" numbers are considered, for which there is a proof that the efficient methods used here, always give the correct result.

/JeppeSN

Profile Nicholas Peter Bamber
Send message
Joined: 23 Dec 18
Posts: 78
ID: 1087751
Credit: 2,951,831
RAC: 8,431
321 LLR Silver: Earned 100,000 credits (141,616)Cullen LLR Silver: Earned 100,000 credits (286,464)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (235,077)PPS LLR Silver: Earned 100,000 credits (195,127)SGS LLR Silver: Earned 100,000 credits (113,315)TRP LLR Bronze: Earned 10,000 credits (14,994)Woodall LLR Silver: Earned 100,000 credits (224,018)321 Sieve Gold: Earned 500,000 credits (504,985)Generalized Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (104,315)PPS Sieve Gold: Earned 500,000 credits (519,134)AP 26/27 Silver: Earned 100,000 credits (327,483)GFN Silver: Earned 100,000 credits (214,375)PSA Bronze: Earned 10,000 credits (69,031)
Message 131042 - Posted: 11 Jul 2019 | 14:37:38 UTC - in response to Message 131021.
Last modified: 11 Jul 2019 | 14:38:41 UTC

Hi,

This leaves numbers to be checked that would end in,

1, 3, 7, 9



This might not be an efficient means of calculating prime numbers. It is however a feasible method of calculating prime numbers in your head without any paper. This could come in handy if your country goes fascist and you get locked up in solitary confinement for political reasons.

As the OP points out for numbers above 10 the final digit must be one of 1,3,7 or 9. This is effectively a sieve for multiples of 2 and 5. You can easily add 3 to the sieve as the pattern repeats every 30 numbers and the pattern is easily visualizable. So in every 30 numbers there are 8 candidates.

Now all you need to do is hold in your head a finite sequence of numbers associated the next few primes:

P(7), P(11), P(13), ....


Initially the sequence consists only of P(7) = 49. So starting at 10 you work through the candidates. Any candidate not in the sequence is a prime number.

When there is a match say P(k), you need to adjust the sequence.

If P(k) is the final member of the sequence, then you need to replace P(k) with P(k)' and P(l)', where

l is the next prime number after k. (This may sound circular but l and k are much smaller than the prime numbers you are calculating.)
P(k)' is the smallest multiple of k that is > P(k) but is not a multiple of 2,3 or 5. (This is easier to calculate then it sounds. The hint is that always it P(k)'-P(k) will be either 2k, 4k or 6k.)
P(l)' = l^2

If P(k) is not the final member of the sequence then P(k)' = smallest multiple of k that is > P(k) but is not a multiple of 2,3 or 5.

With a little practice every day you can progress by about a 100 numbers every few days.

archeye
Send message
Joined: 16 Jan 13
Posts: 6
ID: 189852
Credit: 1,780,674
RAC: 6
Cullen LLR Bronze: Earned 10,000 credits (18,092)Woodall LLR Bronze: Earned 10,000 credits (37,607)GFN Amethyst: Earned 1,000,000 credits (1,712,534)
Message 131401 - Posted: 23 Jul 2019 | 6:19:31 UTC - in response to Message 131042.

Thanks for the replies and now I see the much bigger picture.

My thinking was much too small scale but now I know a lot more.

Cheers :)

Post to thread

Message boards : General discussion : Prime Number Search Method

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2019 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.99, 1.48, 1.62
Generated 17 Nov 2019 | 19:02:55 UTC