mersenneforum.org Fun with partition function
 Register FAQ Search Today's Posts Mark Forums Read

 2015-04-26, 21:06 #1 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,329 Posts Fun with partition function Partition function is available in GP/Pari (p(n) = numbpart(n)), but it is slow for large values of n. It is possible to calculate p(n) with the Arb implementation. Some interesting ideas to try: - write a sieve (currently, it is faster to calculate values with Arb and do some fast tests before dumping the number and feed it to PFGW) - find large primes and PRPs For example, the first (PR)prime value for n>=1010 is p(10000076282) and has 111391 decimal digits.
 2015-04-26, 21:11 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×3,329 Posts Here is a sample C code with Arb that can be freely reused. (this variant outputs nothing if the value is not going to be (PR)prime) Code: #include "fmpz.h" #include "arb.h" #include "partitions.h" #include "stdlib.h" int main(int argc,char **argv) { fmpz_t p,g,r; unsigned long long n; if(argc<2) {perror(" Use: Part i_num (not 4|5, not 5|7, not 6|11 !)\n"); exit(-1);} n=atoll(argv[1]); if(n%5==4) {if(0)printf("# n=4 (mod 5) => 5 | p(n)\n"); exit(0);} if(n%7==5) {if(0)printf("# n=5 (mod 7) => 7 | p(n)\n"); exit(0);} if(n%11==6) {if(0)printf("# n=6 (mod 11) => 11 | p(n)\n"); exit(0);} partitions_fmpz_ui(p, n); fmpz_set_ui(g , 614889782588491410ULL); fmpz_mul_ui(g,g,3749562977351496827ULL); fmpz_mul_ui(g,g,4343678784233766587ULL); // =139# fmpz_gcd(r,p,g); if(fmpz_is_one(r)) { fmpz_print(p); printf("\n"); } exit(0); }
2015-05-07, 16:26   #3
axn

Jun 2003

34·67 Posts

Quote:
 Originally Posted by Batalov - write a sieve (currently, it is faster to calculate values with Arb and do some fast tests before dumping the number and feed it to PFGW)
Idea for a "sieve". There is a recurrence relation for calculating p(n) which requires O(sqrt(n)) operations if we memoize all previous entries. It would require too much memory to store the partition numbers themselves, but we can stored p(n) mod 47# in a 64-bit integer. A 47# sieve might be able to progress through a range of 10^5 to 10^6 numbers per second, in which case, it would take about 100-1000 sec before it will pass thru the alread completed range (~ 10^8) before reaching new territory. Empirically, about 1 in 11.6 partition numbers survive a 47# sieve (which is less than expected for general numbers). The output can then be fed to further sieving or PFGW.

I will need to code it up to see actual performance. Is this something that looks useful?

 2015-05-07, 17:29 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3·3,329 Posts I thought along the same lines. The Euler's pentagonal recurrence is elegant and easily coded. Also, some compression would be possible for the three known major modular restrictions (on 5, 7, and 11) but these values will be needed for the recurrence calls, so not useful and it would have been minor anyway (4/5 * 6/7 * 10/11 ~= 62.3%) The proof (of speed performance) of the pudding is in the eating though. Also, hmmm, I don't know if there is a big market for this sieve. "You've found one prime partition number, -- you've found one too many." All rocks look the same.
2015-05-07, 17:51   #5
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

32·101 Posts

Quote:
 Originally Posted by Batalov Partition function is available in GP/Pari (p(n) = numbpart(n)), but it is slow for large values of n.
Having seen a few partition number generators and written my own simple combinatorial versions, I'd like to rephrase that. Pari's numbpart(n) is not bad at all -- orders of magnitude faster than combinatorial versions. Bober's code using MPFR is ~50x faster but certainly more code. Fredrik Johansson's Arb implementation is amazingly fast.

 2015-05-07, 18:04 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 234038 Posts Indeed, this is how I phrased it after finding that one rock that I wanted for my collection (I like to compare that to peakbagger's club; I want to visit every mountain type in UTM's landscape and at that, if practical, not necessarily top1; in some categories it is mucho tougher than in others). I also searched for the least PRP partition number above 2^34 but with one core only (Arb + prefilter, dump decimal, pfgw). Haven't reached it yet. ;-)
 2017-03-29, 20:01 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 234038 Posts prime P(n^2) numbers A question crossed my mind - how many partition numbers of a square are prime? Not so many, it turns out; just six known so far. P(n2) is (PR)prime for n = 2, 6, 29, 36, 2480, 14881, ... For the largest one, I started the ECPP proof (it is 16,569 decimal digits long). Curiously, 6 and 36 are in the sequence; both P(62) and P(64) are prime; in addition, P(63) and P(6) are prime, but for no other powers A000041(6^k) is known (or can be easily expected) to be prime.
2017-03-30, 00:08   #8
paulunderwood

Sep 2002
Database er0rr

22×1,093 Posts

Quote:
 Originally Posted by Batalov A question crossed my mind - how many partition numbers of a square are prime? Not so many, it turns out; just six known so far. P(n2) is (PR)prime for n = 2, 6, 29, 36, 2480, 14881, ... For the largest one, I started the ECPP proof (it is 16,569 decimal digits long). Curiously, 6 and 36 are in the sequence; both P(62) and P(64) are prime; in addition, P(63) and P(6) are prime, but for no other powers A000041(6^k) is known (or can be easily expected) to be prime.
I am looking forward to your record-breaking 16,569 digit partitions prime's proof

2017-04-06, 14:57   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,329 Posts

Quote:
 Originally Posted by Batalov A question crossed my mind - how many partition numbers of a square are prime?
In general, I would expect the answer to be: infinite.

There is a rather famous Ramanujan-Hardy asymptotic formula (it was even chosen as an illustration for the storyline of the The Man Who Knew Infinity film; for most part of their discussions they talk only about this formula, as if in real life they didn't do many more things).
It is A000041(n) ~ exp(Pi*sqrt(2*n/3)) / (4*sqrt(3)*n).
So, even for n = k^2, the sum of the prime probabilities will be diverging (and there are no obvious restrictions on primality).

 2017-04-06, 16:41 #10 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 2·3·23·61 Posts aka how many squares are in A046063
2017-04-06, 17:19   #11
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100111000000112 Posts

Quote:
 Originally Posted by science_man_88 aka how many squares are in A046063
In theory, yes. Practically, no, -- you will not find 221444161 in A046063.

Not only A046063 is visibly not calculated that far - we do know that it was not taken anywhere near that far

Quote:
 Originally Posted by Jan L. A. van de Snepscheut In theory, there is no difference between theory and practice. But, in practice, there is.

 Similar Threads Thread Thread Starter Forum Replies Last Post JM Montolio A Miscellaneous Math 28 2018-03-08 14:29 rula Homework Help 3 2017-01-18 01:41 fivemack Factoring 57 2007-12-28 10:37 fivemack Math 0 2007-05-18 19:39 OmbooHankvald Linux 19 2005-11-18 10:39

All times are UTC. The time now is 20:41.

Thu Dec 1 20:41:35 UTC 2022 up 105 days, 18:10, 0 users, load averages: 1.45, 1.36, 1.19