Fun with partition function

[Batalov]

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¹⁰ is p(10000076282) and has 111391 decimal digits.

[Batalov]

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)

#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 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);
}

[axn]

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?

[Batalov]

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.

[danaj]

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.

[Batalov]

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. ;-)

[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(n²) 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²) and P(6⁴) are prime; in addition, P(6³) and P(6) are prime, but for no other powers A000041(6^k) is known (or can be easily expected) to be prime.

[paulunderwood]

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(n²) 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²) and P(6⁴) are prime; in addition, P(6³) 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

[Batalov]

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

[science_man_88]

aka how many squares are in A046063

[Batalov]

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

Originally Posted by Jan L. A. van de Snepscheut

In theory, there is no difference between theory and practice. But, in practice, there is.