mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Software (https://www.mersenneforum.org/forumdisplay.php?f=10)
-   -   fpcsieve version 0.1.1 released (https://www.mersenneforum.org/showthread.php?t=20035)

TheCount 2015-02-03 12:23

fpcsieve version 0.1.1 released
 
I've taken Geoffrey Reynolds fpsieve from [URL]https://sites.google.com/site/geoffreywalterreynolds/programs/testing[/URL] and ported it to VS2012 and added Compositorial sieving support to create fpcsieve.
Windows version 0.1.1 binaries are available at:
[URL]https://github.com/RogerKarpin/fpcsieve/tree/master/bin[/URL]
GitHub is new to me but looks really good.

The only changes from fpsieve to include Compositorial sieving are additions to app.c and app.h.
If someone could compile the original code base with these changes and produce linux binaries that would be appreciated.

This is a CPU sieve that has multithreaded support.
Won't port well to GPU as needs to refer to list of Composites in memory (just like Primorial does to list of Primes).
See here for more info:
[URL]http://www.primegrid.com/forum_thread.php?id=5952[/URL]
I've started sieving n<1M. Currently up to 3.8G.
PM me if your interested in Compositorial prime searching.
This is one of the baseless prime searches like Factorial and Primorial.
Will need to reach n>80k to get in the top 5,000 list. Currently only searched to n=16k which is ridiculous for this day and age:
[URL]https://primes.utm.edu/primes/search.php?Number=200&Comment=orial[/URL]
This is my first new thread post on mersenneforum. Hopefully many more to come.

Batalov 2015-02-06 22:34

[URL="http://primes.utm.edu/primes/page.php?id=119245"]96835!/96835# + 1 is prime[/URL]

paulunderwood 2015-02-07 06:11

[QUOTE=Batalov;394753][URL="http://primes.utm.edu/primes/page.php?id=119245"]96835!/96835# + 1 is prime[/URL][/QUOTE]

Congrats :banana:

Are there any gaps in this table?

[code]
----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
2209 96835!/96827#+1 398821 p381 2015 Compositorial (**)
[COLOR="Green"] ---- 41400!/41400#-1 155301 p381 2015 Compositorial[/COLOR]
[COLOR="Green"] ---- 33684!/33684#-1 123321 p381 2015 Compositorial[/COLOR]
40882 20943!/20939#-1 72401 p16 2000 Compositorial
42827 18160!/18149#-1 61635 p16 2000 Compositorial
44240 17258!/17257#+1 58207 p16 2000 Compositorial
47617 15250!/15241#-1 50623 p16 2000 Compositorial
48663 13917!/13913#+1 45631 p16 2000 Compositorial
49214 13724!/13723#-1 44919 p16 2000 Compositorial
51963 10977!/10973#-1 34876 p16 2000 Compositorial
56655 8711!/8707#-1 26816 p7 1999 Compositorial
59086 6851!/6841#+1 20374 p34 2000 Compositorial
60838 6187!/6173#+1 18135 p7 1999 Compositorial
68706 3692!/3691#+1 9996 p7 1999 Compositorial
----- -------------------------------- ------- ----- ---- --------------
[/code]

Batalov 2015-02-07 07:16

There must be!
...'cause I started from 90,200, really, and went up, only until one on either side... well, maybe I'll hunt for the minus side, as well.

[COLOR="Green"]Found in gaps:
Feb 9 18:39:34 PST: 33684!/33684#-1 is prime (123321 digits)
Feb 9 23:11:33 PST: 41400!/41400#-1 is prime (155301 digits)[/COLOR]

TheCount 2015-02-07 14:04

[QUOTE=paulunderwood;394780]Are there any gaps in this table?
[/QUOTE]
Was previously tested to 14000 on both the Plus and Minus sides according to OEIS.
[URL]https://oeis.org/A049420[/URL]

Before implementing the sieving program I double checked this initial range and continued on to:
- Compositorial Plus side: 21706
- Compositorial Minus side: 20621

I've now completed sieving n<1M up to 10G.
969528 terms remain (total of both sides).

Batalov 2015-02-07 17:46

I've briefly searched google for "Daniel Heuer compositorial" and I think some traces (and possibly DH's limits) can be found in the archives of the primeform yahoo group. E.g. [URL="https://groups.yahoo.com/neo/groups/primeform/conversations/messages/3978"]this[/URL] (about C(20493)-1 which you will soon double-check) ...and this appears to be [URL="https://groups.yahoo.com/neo/groups/primeform/search/messages?advance=true&am=CONTAINS&at=email:heuer@&dm=IS_ANY&fs=false&count=1000"]all of his messages[/URL] (API of yahoo groups changed so many times over years; the new API is so inconvenient).

Daniel was active in many curious projects. I stumble over his decade old contributions in many areas.

Maybe Paul has Daniel's contacts? Paul "was always there", as they say.

Antonio 2015-02-07 17:58

There is a bug in the on screen status display. On my machine (Windows 7 64bit i5 3570k @ 4.4GHz) it displays: -

p=309370883, 18.19K p/sec, [COLOR=red]3.94x0MHz[/COLOR] CPU, 0.0% done

(This is with the 64bit version)

Question - wouldn't it sieve a lot faster if it didn't print the factors found file - fpfactors.txt?

paulunderwood 2015-02-07 19:18

[QUOTE=Batalov;394826]

Daniel was active in many curious projects. I stumble over his decade old contributions in many areas.

Maybe Paul has Daniel's contacts? Paul "was always there", as they say.[/QUOTE]

[url]http://primes.utm.edu/bios/page.php?id=223[/url] has his email address, but Daniel may have moved on.

rogue 2015-02-07 23:36

I see no reason why this can't be built upon fpsievecl, the OpenCL implementation of fpsieve. The reason is that this form only requires the exclusion of certain numbers from the multiplication of the factorial. It is possible that global memory access might cause slowdowns though.

TheCount 2015-02-08 08:03

[QUOTE=Antonio;394828]There is a bug in the on screen status display. On my machine (Windows 7 64bit i5 3570k @ 4.4GHz) it displays: -

p=309370883, 18.19K p/sec, [COLOR=red]3.94x0MHz[/COLOR] CPU, 0.0% done

(This is with the 64bit version)[/QUOTE]
I already posted this issue on GitHub:
[URL]https://github.com/RogerKarpin/fpcsieve/issues/2[/URL]
"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."
Its a low priority issue.

[QUOTE]Question - wouldn't it sieve a lot faster if it didn't print the factors found file - fpfactors.txt?[/QUOTE]

You can use -c option to set the checkpoint period, default is every 5 minutes. Set to 0 if you don't want it to periodically checkpoint.
I wouldn't think writing a checkpoint file would affect performance much.

TheCount 2015-02-08 11:36

[QUOTE=rogue;394868]I see no reason why this can't be built upon fpsievecl, the OpenCL implementation of fpsieve. The reason is that this form only requires the exclusion of certain numbers from the multiplication of the factorial. It is possible that global memory access might cause slowdowns though.[/QUOTE]
Worth a try. I'd love to get a GPU sieve for Compositorial. I could have my GPU sieving while PRP testing on my CPU.

fpsievecl? I didn't know you'd extended it to Primorial. If you hadn't yet I would extend to Primorial while adding Compositorial. We can see if it's worthwhile after its implemented.

Is v1.0.8 the latest version? If so I already have it downloaded and know how to fix a bug:
[URL]http://www.primegrid.com/forum_thread.php?id=1163&nowrap=true#80600[/URL]

If Compositorial implemented would the new program be called fpcsievecl? I'd add a new GitHub repo.

rogue 2015-02-08 13:47

[QUOTE=TheCount;394896]Worth a try. I'd love to get a GPU sieve for Compositorial. I could have my GPU sieving while PRP testing on my CPU.

fpsievecl? I didn't know you'd extended it to Primorial. If you hadn't yet I would extend to Primorial while adding Compositorial. We can see if it's worthwhile after its implemented.

Is v1.0.8 the latest version? If so I already have it downloaded and know how to fix a bug:
[URL]http://www.primegrid.com/forum_thread.php?id=1163&nowrap=true#80600[/URL]

If Compositorial implemented would the new program be called fpcsievecl? I'd add a new GitHub repo.[/QUOTE]

I tried an OpenCL primorial sieve, but the problem with was extra I/O between the GPU and CPU and more global memory access. For compositorial each chunk of work in the GPU would require less I/O as fewer primes would be sent in each chunk than for primorial. As I think about it, it might not be any faster.

Antonio 2015-02-08 22:32

[QUOTE=TheCount;394884]

You can use -c option to set the checkpoint period, default is every 5 minutes. Set to 0 if you don't want it to periodically checkpoint.
I wouldn't think writing a checkpoint file would affect performance much.[/QUOTE]

If you re-read my question you will see that I was not asking about the checkpoint file, I was referring to the file listing the eliminated candidates and their factors.

TheCount 2015-02-09 11:02

[QUOTE=Antonio;394941]If you re-read my question you will see that I was not asking about the checkpoint file, I was referring to the file listing the eliminated candidates and their factors.[/QUOTE]
Currently when the program finds a factor it prints it on the console window and appends it to the factors file on disk. This will slow the program early in the sieve when lots of factors are found, but its not like it re-writes the whole file each time. It would be faster early in the sieve not to report factors, but if you don't write to disk you'll lose the factor information. I suppose if your only interested in the sieve file then suppressing this output would be useful. From an admin point of view you'd want to still verify the factors found. Later on in the sieve writing to the factor file will make no real difference. Let me know if you still think an option to suppress factor reporting would be worthwhile. Would be easy to implement.

pdazzl 2015-02-10 04:34

[QUOTE=Batalov;394826]I've briefly searched google for "Daniel Heuer compositorial" and I think some traces (and possibly DH's limits) can be found in the archives of the primeform yahoo group. E.g. [URL="https://groups.yahoo.com/neo/groups/primeform/conversations/messages/3978"]this[/URL] (about C(20493)-1 which you will soon double-check) ...and this appears to be [URL="https://groups.yahoo.com/neo/groups/primeform/search/messages?advance=true&am=CONTAINS&at=email:heuer@&dm=IS_ANY&fs=false&count=1000"]all of his messages[/URL] (API of yahoo groups changed so many times over years; the new API is so inconvenient).

Daniel was active in many curious projects. I stumble over his decade old contributions in many areas.

Maybe Paul has Daniel's contacts? Paul "was always there", as they say.[/QUOTE]

Yes

[url]http://factordb.com/index.php?id=1000000000011970967&prp=Assign+to+worker[/url]

Batalov 2015-02-10 19:59

[QUOTE=Batalov;394826]... (about C(20493)-1 which you will soon double-check) ...[/QUOTE]
This did not imply that C(20493)-1 needs a double-check of primality. It was known that it is prime since 2000.
This meant "you will soon double-check its position in sequence OEIS sequence [URL="http://oeis.org/A140293"]A140293[/URL]".

Additionally, if you meant the "Create time : Before March 17, 2011, 12:27 am" in "More information" section, note that all of them have been apparently [URL="http://factordb.com/index.php?query=99998%21%2F99998%23-1"]entered into the factorDB up to 99,999[/URL] very long ago, before Syd started recording insertion dates.

Batalov 2015-02-22 02:22

Not quite compositorial, but "near-factorial" primes...
All in one place for convenience:
[CODE]Numbers k such that k!/m-1 is prime:
/1 see A002982 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546, 974, 1963, 3507, 3610, 6917, 21480, 34790, 94550, 103040, 147855 *
/2 see A082671 3, 4, 5, 6, 9, 31, 41, 373, 589, 812, 989, 1115, 1488, 1864, 1918, 4412, 4686, 5821, 13830 * [20000]
/3 see A139056 4, 6, 12, 16, 29, 34, 43, 111, 137, 181, 528, 2685 * [30000] ...and [URL="http://primes.utm.edu/primes/page.php?id=119403"]98166[/URL]
/4 see A139199 4, 5, 6, 7, 8, 10, 15, 18, 23, 157, 165, 183, 184, 362, 611, 908 * 2940
/5 see A139200 5, 11, 12, 16, 36, 41, 42, 47, 127, 136, 356, 829, 1863, 2065, 2702 * 4509
/6 see A139201 4, 5, 7, 8, 11, 14, 16, 17, 18, 20, 43, 50, 55, 59, 171, 461, 859 * 2830, 3818, 5421, 5593
/7 see A139202 7, 9, 20, 23, 46, 54, 57, 71, 85, 387, 396, 606, 1121, 2484 *
/8 see A139203 4, 6, 8, 10, 11, 16, 19, 47, 66, 183, 376, 507 * 1081, 1204
/9 see A139204 6, 15, 17, 18, 21, 27, 29, 30, 37, 47, 50, 64, 125, 251, 602, 611, 1184, 1468, 5570 *
/10 see A139205 5, 6, 7, 11, 13, 17, 28, 81, 87, 433, 640, 647 * 798, 1026, 1216, 1277, 3825

Numbers k such that k!/m+1 is prime:
/1 see A002981 0, 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427, 872, 1477, 6380, 26951, 110059, 150209 *
/2 see A082672 2, 4, 5, 7, 8, 13, 16, 30, 43, 49, 91, 119, 213, 1380, 1637, 2258, 4647, 9701, 12258 * [20000]
/3 see A089085 3, 5, 6, 8, 11, 17, 23, 36, 77, 93, 94, 109, 304, 497, 1330, 1996, 3027, 3053, 4529, 5841 * 20556, 26558, 28167 [30000]
/4 see A139061 4, 5, 6, 13, 21, 25, 32, 40, 61, 97, 147, 324, 325, 348, 369 * 1290, 1342, 3167
/5 see A139058 7, 9, 11, 14, 19, 23, 45, 121, 131, 194, 735, 751 * 1316, 1372, 2084, 2562, 5678, 5758
/6 see A139063 3, 4, 10, 11, 13, 14, 17, 21, 82, 115, 165, 167, 173, 174, 208, 225, 380, 655, 1187 * 2000, 2568, 3010, 4542
/7 see A139065 11, 15, 16, 25, 35, 59, 64, 68, 82, 121, 149, 238 * 584, 912, 3349, 4111, 4324
/8 see A151913 7, 9, 10, 12, 14, 20, 23, 24, 29, 44, 108 * 2049, 3072, 4862
/9 see A137390 8, 46, 87, 168, 259, 262, 292, 329, 446, 1056, 3562, 11819, 26737 *
/10 see A139071 5, 6, 11, 12, 15, 23, 26, 37, 45, 108, 112, 129, 137, 148, 172, 248 * 760, 807, 975, 1398, 5231

Numbers k such that m*k!-1 is prime:
2* A076133 2, 3, 4, 5, 6, 7, 14, 15, 17, 22, 28, 91, 253, 257, 298, 659, 832, 866, 1849, 2495, 2716, 2773, 2831, 3364, 5264, 7429, 28539, 32123, 37868 *
3* A076134 0, 1, 2, 3, 4, 5, 9, 12, 17, 26, 76, 379, 438, 1695 * [6000]
4* A099350 0, 1, 2, 3, 5, 6, 10, 11, 51, 63, 197, 313, 579 * 1264, 2276, 2669, 4316, 4382, 4678
5* A099351 3, 5, 8, 13, 20, 25, 51, 97, 101, 241, 266, 521 * 1279, 1750, 2204, 2473, 4193
6* A180627 0, 1, 2, 5, 8, 42, 318, 326, 1054, 2987 *
7* A180628 2, 3, 4, 5, 6, 7, 8, 12, 23, 25, 31, 57, 74, 86, 140, 240, 310, 703, 713, 796, 1028, 1102 * 1924
8* A180629 0, 1, 3, 4, 8, 33, 121, 177, 190, 276, 473, 484, 924, 937, 1722, 2626, 4077, 4464 *
9* A180630 2, 3, 12, 15, 16, 25, 30, 38, 59, 82, 114, 168, 172, 175, 213, 229, 251, 302, 311, 554 *
10*A180631 2, 3, 4, 33, 55, 95, 110, 148, 170, 612, 1155 * 2295

Numbers k such that m*k!+1 is prime:
2* A051915 0, 1, 2, 3, 5, 12, 18, 35, 51, 53, 78, 209, 396, 4166, 9091, 9587, 13357, 15917, 17652, 46127 *
3* A076679 2, 3, 4, 6, 7, 9, 10, 13, 23, 25, 32, 38, 40, 47, 96, 3442, 4048 * 4522, 4887 [6000]
4* A076680 0, 1, 4, 7, 8, 9, 13, 16, 28, 54, 86, 129, 190, 351, 466, 697, 938, 1510, *2748, 2878*, 3396, 4057, 4384 *
5* A076681 2, 3, 5, 10, 11, 12, 17, 34, 74, 136, 155, 259, 271, 290, 352, 479, 494, 677, 776, 862, 921, 932, 2211, 3927 * 4688
6* A076682 0, 1, 2, 3, 7, 8, 9, 12, 13, 18, 24, 38, 48, 60, 113, 196, 210, 391, 681, 739, 778, 1653, 1778, 1796, 1820, *2391*, 2505, 4595 *
7* A076683 3, 7, 8, 15, 19, 29, 36, 43, 51, 158, 160, 203, 432, 909, 1235, 3209 *
8* A178488 2, 4, 9, 10, 11, 12, 15, 25, 31, 46, 53, 78, 318, 615, 955 * 1646
9* A180626 2, 6, 7, 10, 13, 15, 24, 29, 33, 44, 98, 300, 548, 942, 1099, 1176, 1632, 1794, 3676, 3768 *
10*A126896 0, 1, 3, 4, 5, 23, 32, 39, 61, 349, 718, 805, 1025, 1194 * 1550, 1774
[/CODE]

TheCount 2015-02-24 12:28

Golden Prime Search
 
OEIS seems to classify:
"-1" forms as "Almost-* primes" and;
"+1" forms as "Quasi-* primes"
[URL]https://oeis.org/wiki/Base-independent_classifications_of_prime_numbers[/URL]

I can suggest the following names:
[CODE]Form Description
n!/k-1 Almost-k divisor-Factorial prime
n!/k+1 Quasi-k divisor-Factorial prime
k*n!-1 Almost-k multiplier-Factorial prime
k*n!+1 Quasi-k multiplier-Factorial prime
n#/k-1 Almost-k divisor-Primorial prime
n#/k+1 Quasi-k divisor-Primorial prime
k*n#-1 Almost-k multiplier-Primorial prime
k*n#+1 Quasi-k multiplier-Primorial prime
n!/(k*n#)-1 Almost-k divisor-Compositorial prime
n!/(k*n#)+1 Quasi-k divisor-Compositorial prime
k*n!/n#-1 Almost-k multiplier-Compositorial prime
k*n!/n#+1 Quasi-k multiplier-Compositorial prime[/CODE]
Well done Batalov on your Almost-k divisor-Factorial prime
[URL="http://primes.utm.edu/primes/page.php?id=119403"]98166!/3 - 1[/URL]

Orial means Golden in Latin.

Batalov 2015-02-24 20:30

Well, in OEIS, "Almost-" and "Quasi-" prefixes sound rather arbitrary, and your full-length names are truly cumbersome to pronounce ;-).

I am not sure about "k divisor-Factorial" nomenclature: they are instead factorials with some terms [I]skipped[/I] (the shorthand form shouldn't fool, just like with compositorials: yes, n!/n# is easy to write and will be understood by humans and parsed by most programs, but what it conceptually is a product of "not all sequential" numbers, in this case, all composite numbers). Some of them are permutation numbers P[SUB]n,k[/SUB] (e.g. n!/2 or n!/6).

P.S. It goes without saying (but I didn't mention it before) that fpsieve is easily modified for these forms and that's what I indeed used before primality tests.

TheCount 2015-02-24 23:22

Maybe these terms better suit:
skipped k-Factorial
k-Factorial
skipped k-Primorial
k-Primorial
skipped k-Combinatorial
k-Combinatorial

This nomenclature works except when the k your dividing isn't a Prime/Composite respectively, so isn't skipped as such.

TheCount 2015-02-25 00:24

Indeed if k has prime factors with multiplicities then n#/k will be a fraction and so n#/k+/-1 can't be a prime.

TheCount 2015-06-08 12:15

48934!/48934# + 1 is prime

Submitted edit to OEIS A140294.
Proposed to give Daniel Heuer credit for 17258!/17257# + 1

Fully searched Compositorial up to n=45,000. Continuing to 50k.

I am going to extend the "near-factorial" sequences 3*k!+/-1 [A076679, A076134] next by adding multiplier support to fpcsieve.

TheCount 2015-07-11 02:14

Completed check of k!/k#+-1 to 50,000.
Updated OEIS.

Completed adding multiplier support to fpcsieve. So now can sieve these forms: m*k!+-1, m*k#+-1, m*k!/k#+-1.
Committed changes to GitHub, version 0.2.0.
Multiplier=M can be 1 <= M < 2^31 (default=1).
Sieve files are backward compatible.

I wonder if S/R type conjectures are possible for Orials.


All times are UTC. The time now is 13:58.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.