mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2015-04-26, 21:06   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,041 Posts
Lightbulb 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.
Batalov is offline   Reply With Quote
Old 2015-04-26, 21:11   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23A316 Posts
Default

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 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);
}
Batalov is offline   Reply With Quote
Old 2015-05-07, 16:26   #3
axn
 
axn's Avatar
 
Jun 2003

126416 Posts
Default

Quote:
Originally Posted by Batalov View Post
- 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?
axn is offline   Reply With Quote
Old 2015-05-07, 17:29   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,041 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2015-05-07, 17:51   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
danaj is offline   Reply With Quote
Old 2015-05-07, 18:04   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,041 Posts
Default

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 is offline   Reply With Quote
Old 2017-03-29, 20:01   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216438 Posts
Default 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.
Batalov is offline   Reply With Quote
Old 2017-03-30, 00:08   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

7·491 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
paulunderwood is offline   Reply With Quote
Old 2017-04-06, 14:57   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,041 Posts
Default

Quote:
Originally Posted by Batalov View Post
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).
Batalov is offline   Reply With Quote
Old 2017-04-06, 16:41   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

aka how many squares are in A046063
science_man_88 is offline   Reply With Quote
Old 2017-04-06, 17:19   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,041 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A useful function. JM Montolio A Miscellaneous Math 28 2018-03-08 14:29
phi function rula Homework Help 3 2017-01-18 01:41
Have a look at the partition numbers fivemack Factoring 57 2007-12-28 10:37
Partition number congruences fivemack Math 0 2007-05-18 19:39
Linux/SUSE noob trouble - Resize partition OmbooHankvald Linux 19 2005-11-18 10:39

All times are UTC. The time now is 22:40.

Tue Oct 20 22:40:06 UTC 2020 up 40 days, 19:51, 0 users, load averages: 1.43, 1.86, 1.91

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.