Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Project Staging Area :
Number of digits of primorials
| Author |
Message |
|---|
 Bur Volunteer tester
Send message
Joined: 25 Feb 20
Posts: 515
ID: 1241833
Credit: 415,491,654
RAC: 22,332
                
|
|
How can the number of digits of a primorial be estimated? It seems to be possible, as it's shown by T5K, but I couldn't find anything online.
What I found though is an estimate for factorials which is apparently based on Stirling's approximation:
log(n!) ~ floor( (n+0.5)*log(n) + 0.4343n + 1.4 )
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000 | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 14039
ID: 53948
Credit: 479,807,370
RAC: 436,069
                               
|
How can the number of digits of a primorial be estimated? It seems to be possible, as it's shown by T5K, but I couldn't find anything online.
What I found though is an estimate for factorials which is apparently based on Stirling's approximation:
log(n!) ~ floor( (n+0.5)*log(n) + 0.4343n + 1.4 )
Brute force. Expand the number to its decimal representation, and count the digits.
I don't know how T5K does it, but that's how we do it. I'm not certain if there's a better way.
____________
My lucky number is 75898524288+1 | |
|
Yves GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 843
ID: 164101
Credit: 306,540,505
RAC: 5,390
|
How can the number of digits of a primorial be estimated?
We have log(p#) ~ p then #digits(p#) ~ p / log(10).
n = 1000003
primorial = 1; forprime(p = 2, n, primorial *= p); #digits(primorial)
=> 433643
n / log(10)
=> 434295.785 | |
|
|
|
Brute force. Expand the number to its decimal representation, and count the digits.
With PARI/GP, assuming the "default" primelimit is large enough (in the gprc file before startup of PARI), otherwise it is slow, you can calculate the full primorial like this:prod(k=1,primepi(3132781),prime(k))
Then find number of digits with 1+logint(%,10).
If you go beyond primelimit, use:a=1;forprime(p=2,3132781,a*=p);a
If you only care about the number of digits, you can do it in floating point even faster, with:prod(k=1,primepi(3132781),prime(k)+0.0)
If you prefer PFGW, you can do:.\pfgw64.exe -od -f0 -q'len(3132781#)'
/JeppeSN | |
|
BurVolunteer tester
Send message
Joined: 25 Feb 20
Posts: 515
ID: 1241833
Credit: 415,491,654
RAC: 22,332
|
|
Ok, thanks, so it has to be calculated, very interesting. I thought that since the general distribution of primes is known, it could be approximated from the #digits of the respective factorial.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000 | |
|
|
|
Ok, thanks, so it has to be calculated, very interesting. I thought that since the general distribution of primes is known, it could be approximated from the #digits of the respective factorial.
Did you see Yves's post? He estimated from the general distribution of primes. /JeppeSN | |
|
Yves GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 843
ID: 164101
Credit: 306,540,505
RAC: 5,390
|
Ok, thanks, so it has to be calculated, very interesting. I thought that since the general distribution of primes is known, it could be approximated from the #digits of the respective factorial.
Did you see Yves's post? He estimated from the general distribution of primes. /JeppeSN
The first Chebyshev function is the logarithm of the primorial of x. Then p# ~ ep.
| |
|
BurVolunteer tester
Send message
Joined: 25 Feb 20
Posts: 515
ID: 1241833
Credit: 415,491,654
RAC: 22,332
|
|
Apparently I misunderstood that post, I thought it also comprised calculating p#.
To be honest I still don't see it:
forprime(p = 2, n, primorial *= p); #digits(primorial)
Isn't this just a loop that calculates the primorial?
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000 | |
|
Yves GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 843
ID: 164101
Credit: 306,540,505
RAC: 5,390
|
Apparently I misunderstood that post, I thought it also comprised calculating p#.
To be honest I still don't see it:
forprime(p = 2, n, primorial *= p); #digits(primorial) Isn't this just a loop that calculates the primorial?
Yes, it is. Or you compute p# and print the number of digits or you use the estimate p# ~ ep.
You can't compute the exact value of p# without a loop.
| |
|
|
|
|
Explaining Yves's post:
How can the number of digits of a primorial be estimated?
We have log(p#) ~ p then #digits(p#) ~ p / log(10).
Above, Yves gave a way to approximate/estimate the number of digits of p#, namely to use the formula p/log(10). Here, clearly, log denotes the natural logarithm.
n = 1000003
primorial = 1; forprime(p = 2, n, primorial *= p); #digits(primorial)
=> 433643
Above, Yves used p=1000003 as an example. He first calculated the exact number of digits in 1000003# with "brute force", and got 433643 digits.
n / log(10)
=> 434295.785
Above, Yves used his approximation to estimate the number of digits in 1000003#. This method gives 434295.785. This should be compared to the earlier exact value 433643.
We see, that both values are about 434 thousand. So Yves demonstrated that his method does work, as an approximation.
/JeppeSN | |
|
BurVolunteer tester
Send message
Joined: 25 Feb 20
Posts: 515
ID: 1241833
Credit: 415,491,654
RAC: 22,332
|
|
I finally got it, very interesting again.
Slightly off-topic: in PARI/GP log() is the natural logarithm. Is there any built-in function for the decadic logarithm? Always dividing to transform it is a bit cumbersome.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000 | |
|
|
|
Slightly off-topic: in PARI/GP log() is the natural logarithm. Is there any built-in function for the decadic logarithm? Always dividing to transform it is a bit cumbersome.
No. With:lg(x)=log(x)/log(10)
which is the same as:lg=x->log(x)/log(10)
you can define this function yourself.
Note that there is a built-in logint function for integer logarithms. For example:logint(1234^65536+1, 10)
will give you the floor (an integer) of the base 10 logarithm of the number 1234^65536+1 (documented as the largest integer e such that 10^e <= 1234^65536+1).
/JeppeSN | |
|
BurVolunteer tester
Send message
Joined: 25 Feb 20
Posts: 515
ID: 1241833
Credit: 415,491,654
RAC: 22,332
|
|
So logint() accepts the base as a parameter. Why does it return the floor though? Otherwise it'd be exactly what I was looking for.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000 | |
|
|
|
So logint() accepts the base as a parameter. Why does it return the floor though? Otherwise it'd be exactly what I was looking for.
I think they wanted to make it an exact function. If they had returned a floating-point number (called t_REAL by PARI), there would be rounding involved. If you had a result that was very close to an integer, then in theory, because of the inexactness of t_REAL, you could risk that your output was on the "wrong side" of that integer . You can define a function
(x,b) -> log(x)/log(b)
if you still want floating point.
/JeppeSN | |
|
Message boards :
Project Staging Area :
Number of digits of primorials |
