20150426, 21:06  #1 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,041 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>=10^{10} is p(10000076282) and has 111391 decimal digits. 
20150426, 21:11  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×3,041 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 "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 45, not 57, not 611 !)\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); } 
20150507, 16:26  #3  
Jun 2003
2^{2}·11·107 Posts 
Quote:
I will need to code it up to see actual performance. Is this something that looks useful? 

20150507, 17:29  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23A3_{16} 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. 
20150507, 17:51  #5  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 Posts 
Quote:


20150507, 18:04  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,041 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. ;) 
20170329, 20:01  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×3,041 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(n^{2}) 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(6^{2}) and P(6^{4}) are prime; in addition, P(6^{3}) and P(6) are prime, but for no other powers A000041(6^k) is known (or can be easily expected) to be prime. 
20170330, 00:08  #8  
Sep 2002
Database er0rr
7·491 Posts 
Quote:


20170406, 14:57  #9  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9123_{10} Posts 
Quote:
There is a rather famous RamanujanHardy 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). 

20170406, 16:41  #10 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
aka how many squares are in A046063

20170406, 17:19  #11  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×3,041 Posts 
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:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A useful function.  JM Montolio A  Miscellaneous Math  28  20180308 14:29 
phi function  rula  Homework Help  3  20170118 01:41 
Have a look at the partition numbers  fivemack  Factoring  57  20071228 10:37 
Partition number congruences  fivemack  Math  0  20070518 19:39 
Linux/SUSE noob trouble  Resize partition  OmbooHankvald  Linux  19  20051118 10:39 