## Other

drummers-lowrise

Message boards : General discussion : Prime Number Search Method

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
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

Message 131023 - Posted: 10 Jul 2019 | 20:48:34 UTC - in response to Message 131021.

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!

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

Message 131042 - Posted: 11 Jul 2019 | 14:37:38 UTC - in response to Message 131021.

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.

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 :)

Message boards : General discussion : Prime Number Search Method