## Other

drummers-lowrise

Message boards : Project Staging Area : Number of digits of primorials

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Message 146136 - Posted: 5 Dec 2020 | 7:05:13 UTC

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

Message 146138 - Posted: 5 Dec 2020 | 7:25:13 UTC - in response to Message 146136.

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 Gallot Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 843
ID: 164101
Credit: 306,540,505
RAC: 5,390 Message 146141 - Posted: 5 Dec 2020 | 8:42:44 UTC - in response to Message 146136.

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

Message 146142 - Posted: 5 Dec 2020 | 9:21:52 UTC - in response to Message 146138.

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

Message 146189 - Posted: 6 Dec 2020 | 6:33:15 UTC

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

Message 146191 - Posted: 6 Dec 2020 | 7:36:15 UTC - in response to Message 146189.

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 Gallot Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 843
ID: 164101
Credit: 306,540,505
RAC: 5,390 Message 146205 - Posted: 6 Dec 2020 | 13:51:57 UTC - in response to Message 146191.

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.

Message 146337 - Posted: 8 Dec 2020 | 9:40:31 UTC - in response to Message 146205.

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 Gallot Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 843
ID: 164101
Credit: 306,540,505
RAC: 5,390 Message 146340 - Posted: 8 Dec 2020 | 10:26:21 UTC - in response to Message 146337.

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.

Message 146351 - Posted: 8 Dec 2020 | 13:04:45 UTC - in response to Message 146141.

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

Message 146382 - Posted: 8 Dec 2020 | 18:34:40 UTC - in response to Message 146351.

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

Message 146408 - Posted: 8 Dec 2020 | 22:54:25 UTC - in response to Message 146382.

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:

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

Message 146493 - Posted: 10 Dec 2020 | 18:31:01 UTC - in response to Message 146408.

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

Message 146529 - Posted: 11 Dec 2020 | 8:44:43 UTC - in response to Message 146493.

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