# 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,
 Maximal product of primes whose sum is bounded.
See also the paper written by Marc Deléglise, Jean-Louis Nicolas and Paul Zimmermann,
 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  or  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 .

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

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