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 : Project Staging Area : Chance of a Factorial Prime

Author Message
Profile Roger
Volunteer developer
Volunteer tester
Avatar
Send message
Joined: 27 Nov 11
Posts: 1137
ID: 120786
Credit: 267,301,821
RAC: 8,447
Found 1 prime in the 2018 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,037,982)Cullen LLR Ruby: Earned 2,000,000 credits (2,015,907)ESP LLR Ruby: Earned 2,000,000 credits (2,232,391)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,088,705)PPS LLR Ruby: Earned 2,000,000 credits (2,962,062)PSP LLR Ruby: Earned 2,000,000 credits (2,539,644)SoB LLR Ruby: Earned 2,000,000 credits (2,122,524)SR5 LLR Ruby: Earned 2,000,000 credits (2,238,295)SGS LLR Ruby: Earned 2,000,000 credits (3,915,665)TRP LLR Ruby: Earned 2,000,000 credits (2,125,391)Woodall LLR Ruby: Earned 2,000,000 credits (2,037,732)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,190,731)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (207,387)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,049,697)PPS Sieve Double Bronze: Earned 100,000,000 credits (100,422,123)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (3,227,972)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,021,659)AP 26/27 Sapphire: Earned 20,000,000 credits (20,651,644)GFN Emerald: Earned 50,000,000 credits (57,918,585)PSA Sapphire: Earned 20,000,000 credits (43,298,465)
Message 80804 - Posted: 16 Nov 2014 | 5:09:37 UTC
Last modified: 16 Nov 2014 | 6:21:28 UTC

Prime Number Theory says that the chance of a random integer x being prime is about 1/log x
For x = n!+/-1, chance is about w/log n!
To find the probability over a given range we integrate from n = A to n = B.
You can use approximation to Stirling's Formula, where n! ~= n^n * e^-n and some log identities, i.e.

1/log(n^n * e^-n)
= 1/(log(n^n) + log(e^-n))
= 1/(n*log(n) - n*log(e))
= 1/(n*log(n) - n)

Integrating 1/(n*log(n) - n) gives log(log(n)-1) so:
Number of Primes = w * (log(log(B)-1) - log(log(A)-1))

Weight is scaled so w=1.0 has the same density of primes as a randomly chosen set of odd numbers of the same magnitude.
You can use fpsieve to find P1e6; the number of candidates remaining after testing the range n=100001 to 110000 for factors up to 1 million.
>fpsieve -n 100001 -N 110000 -P 1e6 -x

Running this I found:
2528 terms with factors for n!-1, so 7472 remain and
2651 terms with factors for n!+1, so 7349 remain.

That's a good start. I'll finish trying to crack it later, unless someone else wants to take on the challenge.

JimBProject donor
Honorary cruncher
Send message
Joined: 4 Aug 11
Posts: 917
ID: 107307
Credit: 974,340,904
RAC: 5,325
Discovered 1 mega prime321 LLR Ruby: Earned 2,000,000 credits (2,691,081)Cullen LLR Turquoise: Earned 5,000,000 credits (5,031,868)ESP LLR Turquoise: Earned 5,000,000 credits (5,064,082)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,038,750)PPS LLR Turquoise: Earned 5,000,000 credits (5,000,220)PSP LLR Turquoise: Earned 5,000,000 credits (7,674,374)SoB LLR Sapphire: Earned 20,000,000 credits (42,604,648)SR5 LLR Jade: Earned 10,000,000 credits (11,829,173)SGS LLR Ruby: Earned 2,000,000 credits (2,257,698)TRP LLR Ruby: Earned 2,000,000 credits (2,291,092)Woodall LLR Turquoise: Earned 5,000,000 credits (5,046,412)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,057,614)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,005,451)PPS Sieve Emerald: Earned 50,000,000 credits (52,042,965)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Jade: Earned 10,000,000 credits (10,742,251)GFN Emerald: Earned 50,000,000 credits (50,000,251)PSA Double Gold: Earned 500,000,000 credits (728,547,693)
Message 80805 - Posted: 16 Nov 2014 | 10:13:09 UTC

Rather than use fpsieve, why not just grab the sieve file that we use to generate work? It contains all n < 1M and has been sieved to p=5.505T.

rogue
Volunteer developer
Avatar
Send message
Joined: 8 Sep 07
Posts: 1200
ID: 12001
Credit: 18,565,548
RAC: 0
PPS LLR Bronze: Earned 10,000 credits (31,229)PSA Jade: Earned 10,000,000 credits (18,533,435)
Message 80810 - Posted: 16 Nov 2014 | 14:25:22 UTC

Sieving for min n > 2 would require some optimizations to fsievecl and fpsieve.

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 620
ID: 164101
Credit: 304,931,125
RAC: 4,845
GFN Double Silver: Earned 200,000,000 credits (304,931,125)
Message 80811 - Posted: 16 Nov 2014 | 15:00:31 UTC - in response to Message 80804.

Weight is scaled so w=1.0 has the same density of primes as a randomly chosen set of odd numbers of the same magnitude.

w > 1 because if p | n!+/-1 then p > n.
See http://www.ams.org/journals/mcom/2002-71-237/S0025-5718-01-01315-1/home.html.

Profile Roger
Volunteer developer
Volunteer tester
Avatar
Send message
Joined: 27 Nov 11
Posts: 1137
ID: 120786
Credit: 267,301,821
RAC: 8,447
Found 1 prime in the 2018 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,037,982)Cullen LLR Ruby: Earned 2,000,000 credits (2,015,907)ESP LLR Ruby: Earned 2,000,000 credits (2,232,391)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,088,705)PPS LLR Ruby: Earned 2,000,000 credits (2,962,062)PSP LLR Ruby: Earned 2,000,000 credits (2,539,644)SoB LLR Ruby: Earned 2,000,000 credits (2,122,524)SR5 LLR Ruby: Earned 2,000,000 credits (2,238,295)SGS LLR Ruby: Earned 2,000,000 credits (3,915,665)TRP LLR Ruby: Earned 2,000,000 credits (2,125,391)Woodall LLR Ruby: Earned 2,000,000 credits (2,037,732)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,190,731)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (207,387)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,049,697)PPS Sieve Double Bronze: Earned 100,000,000 credits (100,422,123)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (3,227,972)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,021,659)AP 26/27 Sapphire: Earned 20,000,000 credits (20,651,644)GFN Emerald: Earned 50,000,000 credits (57,918,585)PSA Sapphire: Earned 20,000,000 credits (43,298,465)
Message 80819 - Posted: 17 Nov 2014 | 12:01:50 UTC - in response to Message 80805.

Rather than use fpsieve, why not just grab the sieve file that we use to generate work? It contains all n < 1M and has been sieved to p=5.505T.

Looking at the sieve file fsieve_5505G.txt there are 3474 terms remaining for n!-1 and 3495 for n!+1 in the range n=100001 to 110000 for factors up to 1 million.
Using a deeper sieved file will give a more accurate result for the chance value.

Sieving for min n > 2 would require some optimizations to fsievecl and fpsieve.

Not sure what you mean by this. Please elaborate.

w > 1 because if p | n!+/-1 then p > n.
See http://www.ams.org/journals/mcom/2002-71-237/S0025-5718-01-01315-1/home.html.

Cool. I didn't know about this paper. I'll have to study it. Has anything been done on compositorial? As far as I can tell its only been searched to 14,000. I searched to 11,000 with 2 cores in only 2 days.

rogue
Volunteer developer
Avatar
Send message
Joined: 8 Sep 07
Posts: 1200
ID: 12001
Credit: 18,565,548
RAC: 0
PPS LLR Bronze: Earned 10,000 credits (31,229)PSA Jade: Earned 10,000,000 credits (18,533,435)
Message 80828 - Posted: 17 Nov 2014 | 22:40:43 UTC - in response to Message 80819.

Sieving for min n > 2 would require some optimizations to fsievecl and fpsieve.

Not sure what you mean by this. Please elaborate.


The current software starts at n=2 and iteratively multiplies terms up to minn. That's fine for the project, but if someone wants to go above n=1e6 (the maxn of the current range being sieved), then there are some optimizations that could be made to compute 1000001! % p where n=1000001 would be the minn of the next range.

Profile Roger
Volunteer developer
Volunteer tester
Avatar
Send message
Joined: 27 Nov 11
Posts: 1137
ID: 120786
Credit: 267,301,821
RAC: 8,447
Found 1 prime in the 2018 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,037,982)Cullen LLR Ruby: Earned 2,000,000 credits (2,015,907)ESP LLR Ruby: Earned 2,000,000 credits (2,232,391)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,088,705)PPS LLR Ruby: Earned 2,000,000 credits (2,962,062)PSP LLR Ruby: Earned 2,000,000 credits (2,539,644)SoB LLR Ruby: Earned 2,000,000 credits (2,122,524)SR5 LLR Ruby: Earned 2,000,000 credits (2,238,295)SGS LLR Ruby: Earned 2,000,000 credits (3,915,665)TRP LLR Ruby: Earned 2,000,000 credits (2,125,391)Woodall LLR Ruby: Earned 2,000,000 credits (2,037,732)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,190,731)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (207,387)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,049,697)PPS Sieve Double Bronze: Earned 100,000,000 credits (100,422,123)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (3,227,972)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,021,659)AP 26/27 Sapphire: Earned 20,000,000 credits (20,651,644)GFN Emerald: Earned 50,000,000 credits (57,918,585)PSA Sapphire: Earned 20,000,000 credits (43,298,465)
Message 80894 - Posted: 22 Nov 2014 | 9:04:11 UTC - in response to Message 80811.

w > 1 because if p | n!+/-1 then p > n.
See http://www.ams.org/journals/mcom/2002-71-237/S0025-5718-01-01315-1/home.html.

I didn't think w=1.0, I just hadn't put a formula to it yet.

Caldwell and Yves Paper starts off with Stirlings Formula like I did but then says n!+/-1 does not behave like a random variable so has weight e^γ ln(n),
where γ is the Euler–Mascheroni constant = 0.577215664901533...
(Don't think I would have figured that out in a hurry.)
Before the start of the challenge Leading edge of the Factorial prime search was up to 165415 on both the plus and minus sides.
At the end of the challenge leading edge was up to about 171716 (that's the last one I completed crunching anyway).
From the paper number of Factorial primes expected in range A to B = e^γ (ln(B) – ln(A)) = 0.0665844691
So we had a 6.6% chance of finding a prime!

In the paper Primorial ends up with the same formula.
Before the start of the challenge Leading edge of the Primorial prime search was up to 1,790,070 on both the plus and minus sides.
At the end of the challenge leading edge was up to about 1,865,579 (that's the last one I completed crunching anyway).
From the paper number of Primorial primes expected in range A to B = e^γ (ln(B) – ln(A)) = 0.0735880979
So we had a 7.3% chance of finding a prime#

Can this formula be extended to Compositorial? Formula expects 17 primes for n<=14,000
Ignoring n's yielding same primes we see 19 primes found on the plus side and 22 on the minus side, for n<=14,000.
This is similar to the difference between expected and actual for Factorial/Primorial, so I'll adopt it.

The current software starts at n=2 and iteratively multiplies terms up to minn. That's fine for the project, but if someone wants to go above n=1e6 (the maxn of the current range being sieved), then there are some optimizations that could be made to compute 1000001! % p where n=1000001 would be the minn of the next range.

I don't think we're going to need minn > 2 for a long time.

Message boards : Project Staging Area : Chance of a Factorial Prime

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2020 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 3.21, 3.77, 3.89
Generated 3 Dec 2020 | 17:17:25 UTC