Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
General discussion :
Compositorial primes
Author |
Message |
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
The following is just for interest, that's why I am posting this in the General discussion thread.
Definition
Iago Camboa pointed out that n!/n# (n-factorial divided by n-primorial) is the product of all the composite numbers less than or equal to n and suggested the name compositiorial.
The numbers n!/n# +/- 1 (when prime) might be given the name compositorial prime (like factorial prime and primorial prime).
Numbers n such that n!/n# + 1 is prime, where n# is the primorial function (A140294):
0, 1, 2, 3, 4, 5, 8, 14, 20, 26, 34, 56, 104, 153, 182, 194, 217, 230, 280, 281, 462, 463, 529, 1445, 2515, 3692, 6187, 6851, 13917
Numbers n such that n!/n# - 1 is prime (A140293):
4, 5, 6, 7, 8, 16, 17, 21, 34, 39, 45, 50, 72, 73, 76, 133, 164, 202, 216, 221, 280, 281, 496, 605, 2532, 2967, 3337, 8711, 10977, 13724
Notice that 280!/280# + 1 (= 281!/281# + 1) are twin primes!
Reference: The Prime Glossary.
Testing
How would one go about testing for Compositorial primes?
PRP test:
>pfgw.exe -f0 -l -q"13917!/13917#+1"
PFGW Version 3.3.6.20100908.Win_Stable [GWNUM 25.14]
Output logging to file pfgw.out
No factoring at all, not even trivial division
13917!/13917#+1 is 3-PRP! (90.8241s+0.0107s)
Prove Primality:
>pfgw.exe -t -f0 -l -q"13917!/13917#+1"
PFGW Version 3.3.6.20100908.Win_Stable [GWNUM 25.14]
Output logging to file pfgw.out
No factoring at all, not even trivial division
Primality testing 13917!/13917#+1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 6959
Calling Brillhart-Lehmer-Selfridge with factored part 34.39%
13917!/13917#+1 is prime! (135.9171s+0.0130s)
(-t switch for the plus side -OR- -tp switch for the minus side)
____________
| |
|
|
Listing both 280 and 281 seems unnatural. It would be like saying that 31#+1, 32#+1, 33#+1, 34#+1, 35#+1, and 36#+1 are all primorial primes. If you avoid duplicates like that, you get A049420 and A049421. /JeppeSN | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
I've completed testing 1<=n<=14,000 and my results agree with those listed.
PRP tests at this level take 93 seconds.
I found a little bit of trial factoring reduces average time per test by 40%. So after I am now using:
>pfgw.exe -f50 -l c-test.txt
Where the c-test.txt file contains a list of tests created with a spreadsheet:
1!/1#-1
2!/2#-1
3!/3#-1
4!/4#-1
...
Using the formula for number of expected primes A to B = e^γ (ln(B) – ln(A))
Where γ is the Euler–Mascheroni constant = 0.577215664901533...
I would expect one new prime on both the plus and minus side by 25,000 and another by 45,000.
So I plan on continuing testing to 50,000 then submitting primes to OEIS. | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
Hit gold early on. Announcing new Compositorial primes:
15250!/15250#-1
17258!/17258#+1
I've submitted these to OEIS. Even had the founder N. J. A. Sloane approve some of them.
____________
| |
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13778 ID: 53948 Credit: 343,945,598 RAC: 15,283
                              
|
Congratulations!
____________
My lucky number is 75898524288+1 | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
We use fpsieve for factorial and primorial sieving:
https://sites.google.com/site/geoffreywalterreynolds/programs/testing
I successfully compiled fpsieve with Visual Studio 2012.
I've also completed modifying the code to additionally support compositorial sieving.
Now in the testing phase. Main problem is that the factors its reporting are incorrect. Needs debugging.
You can check factors found with pfgw. In version 3.7.8 you can run as "pfgw factors.txt" and if all lines return "is Zero", then they are valid factors. | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
Sieve program has now entered Beta.
Tasks completed with 1<n<200k:
1. Confirmed all factors found p=0-1M (86550) are correct with pfgw.
2. Confirmed all factors found p=1-10M (39605) are correct with pfgw.
3. Confirmed remaining terms sieved to p=1G (184916) in sieve file are correct.
4. Some terms with factors were reported twice in cfactors_1-10M and some factored terms appeared in sieve file. Reran 1-10M to see if repeated. Didn't repeat, assume one off memory error. Terms with factors in rerun were identical, so no terms missed factors or incorrectly reported factors. So can rely on factors reported but need to check 'terms'-'terms with factors'='terms in sieve file', otherwise can't rely on sieve file and need to rerun range, (or can run dat-less sieve).
5. Confirmed multithreaded usage scales linearly.
Bugfixes implemented:
1. Fixed compositorial reporting incorrect factors by correcting initial value of remainder in sieve, i.e. REM[j] = 1;
2. Fixed ability to read from input compositorial sieve file by adding numbers to composite list from last prime+1 to nmax.
i.e. composites_to_reserve = nmax-prime_count-1;
...
for (i = last_prime + 1; i <= nmax; i++)
sieve_composites[composite_count++] = i;
Known bugs/To-do list:
1. Not accepting -w argument for compositorial. Made compositorial the default search as a work around.
2. Speed of CPU in periodic report not working for 64bit. Need separate asm file to read CPU speed as VS2012 does not compile C file with assembler inline.
3. Average processor utilisation reported incorrectly for short executions.
4. Need to get app compiled with GNU C library for linux and windows. This provides large ~40% speedup.
5. Need to notify author and release. | |
|
|
Good work. /JeppeSN | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
Decided to rename the sieve program fpcsieve to avoid any issues.
Windows version 0.1.0 binaries are available at:
https://github.com/RogerKarpin/fpcsieve/tree/master/bin
I'll work on adding the existing issue list and code base to GitHub.
Feel free to test.
Example command line:
fpsieve.exe -icsieve_10M.txt -ocsieve100M.txt -fcfactors_10-100M.txt -p10M -P100M
Here the:
- input sieve file is called "csieve_10M.txt",
- the output sieve file is "csieve100M.txt",
- the output factor file is "cfactors_10-100M.txt", and
- we're sieving 10,000,000 < p < 100,000,000.
If you want to start a new sieve specify max n with the -N command line option and don't use -i.
Input and output sieve files are optional.
rogue said he might add Compositorial support to PRPNet. | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
I've fixed the -w argument so its working and put Factorial back as the default when starting a new sieve.
The source code has now been posted to GitHub along with the latest 0.1.1 binaries.
The only changes from fpsieve to include Compositorial sieving are additions to app.c and app.h.
If someone could compile Geoffrey Reynolds original code base with these changes and produce linux binaries that would be appreciated:
https://sites.google.com/site/geoffreywalterreynolds/programs/testing
Now that I've finished coding it's time for me to start sieving n<1M and finish taking the Compositorial prime search to n=50,000. | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
Well done to Batalov for finding the first Compositorial prime to make it into the Top 5000:
https://primes.utm.edu/primes/page.php?id=119245
Is the 7th largest "-orial" prime found so far:
https://primes.utm.edu/primes/search.php?Number=10&Comment=orial | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
Batalov has extended some of the prime sequences:
- k!/m-1
- k!/m+1
- m*k!-1
- m*k!+1
http://www.mersenneforum.org/showpost.php?p=396047&postcount=17
His "near-factorial" find 98166!/3 - 1 made it into the top 5000:
http://primes.utm.edu/primes/page.php?id=119403
He credits fpsieve, so he must have altered the sieving code to help find this large prime.
If anyone is interested in continuing his efforts let me know and I'll add proper support to fpcsieve for the forms:
- k!/m-1
- k!/m+1
- m*k!-1
- m*k!+1
- k#/m-1
- k#/m+1
- m*k#-1
- m*k#+1
- k!/(m*k#)-1
- k!/(m*k#)+1
- m*k!/k#-1
- m*k!/k#+1
OEIS seems to classify:
- "-1" forms as "Almost-* primes" and;
- "+1" forms as "Quasi-* primes"
https://oeis.org/wiki/Base-independent_classifications_of_prime_numbers
How would you classify "m*" and "/m" forms?
My current goal is to check k!/k#+-1 to 50,000.
Batalov has additionaly reported finding primes:
- 33684!/33684#-1
- 41400!/41400#-1 | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
48934!/48934#+1 is prime
Completed check of k!/k#+-1 to 50,000.
I estimate it would take my CPU another 15 months PRP testing to reach 100,000. Additional time for the sieving.
That compares to 1.3 months for the range 15-50k.
That's why I next plan on extending the "near-factorial" sequences 3*k!+/-1 [A076679, A076134] by adding multiplier support to fpcsieve. | |
|
RogerVolunteer developer Volunteer tester
 Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0
                    
|
Finished adding multiplier support to fpcsieve.
Windows version 0.2.0 binaries are available at:
https://github.com/RogerKarpin/fpcsieve/tree/master/bin
Tested by completing 3-factorial search up to k=50,000.
Found new primes:
3*7033!+1
3*9528!+1
3*12915!+1
3*31762!+1 [A076679]
3*6709!-1
3*13313!-1
3*18504!-1
3*19021!-1
3*24488!-1
3*45552!-1
3*49085!-1 [A076134]
Contemplating adding divisor support next. | |
|
Message boards :
General discussion :
Compositorial primes |