Computation of the function h(n), maximal product of
primes whose sum is ≤ n
The method of computation of h(n) is described in the paper written by
Marc Deléglise and Jean-Louis Nicolas,
[1]
Maximal product of primes whose sum is bounded.
See also the paper written by
Marc Deléglise, Jean-Louis Nicolas and Paul Zimmermann,
[2]
Landau's function for one million billions.
Let pi be the i-th prime and
σi=p1+p2+...+pi.
To calculate h(n), the first step is to determine k=k(n)
defined by σk≤ n <
σk+1. Further, one sets
n'=n-σk and
mm=n' if n' is even
while mm=n'-1 if n' is odd.
If Nk is the product of the first k primes,
we have h(n)=NkG(pk ,n')
where G(p,m) is a fraction somewhat complicated to
evaluate.
There are 5 types for the computation of
G(pk ,n'):
Type 0 : if n'= pk+1 -2 or n'=
pk+1 -1 then G(pk ,n')=
pk+1 /2.
Type 1 : if 0 ≤ n' < pk+1 - pk
then G(pk ,n')=1.
Type 2 : if pk+1 -mm is a prime, say q,
then G(pk ,n')=pk+1 /q.
Type 3 : is the general case, solved by the δ-method (see [1] or
[2] for explanations).
Type 4 : is the case where the δ-method fails and the
combinatorial method is used. This case occurs only when
n' is small.
The variable ecart is the largest integer such that
h(n-ecart) =h(n).
All the prime factors of G(pk ,n') (but one) are close
to pk , i.e. are equal to pk+i with
i small. The values of the i's are given in a list. For
instance the display
[1,4], [ p',p''], [-2], [p''',q] means that
G(pk , n')=p' p'' / p''' q
with p'=pk+1 ,
p''=pk+4
and p'=pk-2 .
To see the table of the values of
h(2a) and h(10a) download the file
powersof2and10
To use the Maple program to compute h(n), download the MAPLE code file
calculhden
Open a MAPLE sheet and type
read calculhden:
♣ If you want to calculate h(n)
for a not too large n, say n≤1012, then type
hdennext(n);
The procedure hdennext generates the primes by using the
function nextprime.
♦ If you want to calculate h(n)
for several not too large n's, you had better to generate
the primes and the sum of consecutive primes with a sieve.
For that, for, say, nmax=107,
type crible(nmax);
Then, for several values of n, type
hdensieve(n);
♥ If you want to calculate h(2a)
for amin≤a≤amax with 1≤amin ≤ amax ≤ 117,
then type
hdedeuxpuisa(amin,amax);
This procedure has been used to write the above
mentionned file powersof2and10.
For 1≤a ≤ 117, and n=2a, the values of
pk and n' have been precomputed and
written in the file calculhden, see the reference [1].
♠ If you want to calculate h(10a)
for amin≤a≤amax with 1≤amin ≤ amax ≤ 35,
then type
hdedixpuisa(amin,amax);
This procedure has been used to write the above
mentionned file powersof2and10.
For 1≤a ≤ 35, and n=10a, the values of
pk and n' have been precomputed and
written in the file calculhden, see the reference [1].
¶ If you want to calculate G(p,m),
then type
Gpkmh(p,m,500,2);.
You may try to change the two last paramaters; the last
one is a printing parameter : increasing it will print
more partial results.