## Other

drummers-lowrise

Message boards : General discussion : Compositorial primes

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 80529 - Posted: 25 Oct 2014 | 8:41:53 UTC

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

JeppeSN

Joined: 5 Apr 14
Posts: 1675
ID: 306875
Credit: 40,313,698
RAC: 9,667

Message 80540 - Posted: 25 Oct 2014 | 17:05:24 UTC

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

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 80956 - Posted: 25 Nov 2014 | 12:04:47 UTC

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.

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 81004 - Posted: 29 Nov 2014 | 5:58:18 UTC

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

Joined: 21 Jan 10
Posts: 13778
ID: 53948
Credit: 343,945,598
RAC: 15,283

Message 81009 - Posted: 29 Nov 2014 | 11:56:59 UTC - in response to Message 81004.

Congratulations!
____________
My lucky number is 75898524288+1

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 82254 - Posted: 8 Jan 2015 | 2:36:45 UTC

We use fpsieve for factorial and primorial sieving:
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.

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 82650 - Posted: 20 Jan 2015 | 13:13:37 UTC

Sieve program has now entered Beta.

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.

JeppeSN

Joined: 5 Apr 14
Posts: 1675
ID: 306875
Credit: 40,313,698
RAC: 9,667

Message 82657 - Posted: 20 Jan 2015 | 15:59:34 UTC - in response to Message 82650.

Good work. /JeppeSN

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 82825 - Posted: 24 Jan 2015 | 23:04:59 UTC

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.

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 82873 - Posted: 26 Jan 2015 | 1:05:42 UTC

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:

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.

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 83253 - Posted: 7 Feb 2015 | 13:08:25 UTC

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

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 83511 - Posted: 23 Feb 2015 | 13:56:06 UTC

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

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 86562 - Posted: 5 Jul 2015 | 11:32:54 UTC

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.

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,621,444
RAC: 0

Message 100864 - Posted: 13 Nov 2016 | 12:19:47 UTC

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]