Valeurs de la fonction Theta de Chebychev

Soit θ et ψ les fonctions de Chebychev définies par θ(x)= Σ_{p ≤ x} log p et ψ(x) = Σ_{pⁿ ≤ x} log p. La métode évidente de calcul de theta(x), énumerer les nombres premiers ≤ x en additionnant leurs logarithmes est de coût proportionnel à x log(log x). La différence psi(x) - theta(x) = Σ_{p^n ≤ x, 2 ≤ n}, est une somme ne portant que sur les nombres premiers inférieurs à x^(1/2) par la méthode naïve elle se calcule en temps O(x^(1/2 + eps)) pour tout eps > 0. En utilisant alors l'algorithme de calcul de psi(x) en temps inférieur à O(x^(2/3 + eps) pour tout eps > 0, présenté dans M. Deléglise and J. Rivat, Computing Psi(x) il est possible de calculer theta(x) en temps O(x^(2/3 + eps). Voici quelques valeurs de la fonction Theta de Chebychev calculées à l'aide de cet algorithme.

• Theta11.txt
• Theta12.txt
• Theta13.txt
• Theta14.txt
• Theta15.txt
• Theta16_18.txt

Pour plus de détails consulter: Psi-Theta.

Grandes valeurs de la fonction h(n)

Soit h(n) la valeur maximale du produit de n nombres premiers distincts dont la somme ne dépasse pas n. La suite (h(n)) _n est l'entrée A159685 de l'O.e.i.s. Dans Maximal product of primes whose sum is bounded , nous donnons un algorithme qui calcule h(n) pour de grandes valeurs de n, en deux étapes.

• Première étape : calcul de p_k et σ_k

  Notons p₁, p₂, … , p_i, … la suite des nombres premiers. On calcule le plus grand entier k tel que σ_k = p₁ + … + p_k ≤ n. Pour cela, on peut, très simplement, additionner les nombres premiers successifs jusqu'à ce que la somme dépasse n. Cette méthode convient pour des valeurs de n jusqu'à environ 10²⁰.

  Nous donnons une méthode plus sophisiquée utilisant un algorithme de calcul de la somme des nombres premiers jusqu'à x dont le temps de calcul est O(x^2/3/(log² x)). La tables puiss10-35 donne les valeurs de p_k et les temps de calcul, pour quelques valeurs de n, jusqu'à 10³⁵.

• Seconde étape : calcul de h(n)

  Notons N_k = p₁ p₂ … p_k, où k est l'entier calculé lors de la première étape. Quand n tend vers l'infini, les logarithmes de N_k et de h(n) sont équivalents à sqrt(n log n). N_k et h(n) sont donc des trè grands nombres. Par exemple, pour n=10¹⁰, h(n) = 502261/424129 N_k, et les écritures décimales de N_k et de h(n) sont toutes les deux composées de 217 826 chiffres. Pour n=10²⁰, l'écriture décimale de h(n) nécessite plus de 67 milliards de chiffres.

  Dans cette étape on calcule le rapport h(n)/N_k. Nous sommes incapables d'estimer le coût de cette étape. En pratique il est faible, négligeable devant le coût de la première étape. Jamais plus d'une seconde pour toutes les valeurs de n que nous avons considérées. Le fichier hnexemples.txt donne les valeurs de h(n)/n pour n=10^a, 1 ≤ a ≤ 35.

Quelques tables relatives à la distribution des nombres premiers

Tables utilisées dans Le plus grand facteur premier de la fonction de Landau. (avec J.-L. Nicolas).

• Tabulation de ThetaMin
• Tabulation de ThetaD
• Tabulation de Eta1
• Tabulation de Eta2
• Tabulation de Eta3
• Tabulation de Delta3

Calcul de la fonction de Landau

Landau's function for one million billions, with Jean-Louis Nicolas and Paul Zimmermann. preprint, February 2008. Let S_n denote the symmetric group with n letters, and g(n) the maximal order of an element of S_n. If the standard factorization of M into primes is M=q₁^a₁ q₂^a₂… q_k^a_k, we define l(M) to be q₁^a₁ + q₂^a₂ + … + q_k^a_k; one century ago, E. Landau proved that g(n)=max_{l(M) ≤ n} M and that, when n goes to infinity, log g(n) ~ sqrt(n log(n)). There exists a basic algorithm to compute g(n) for 1 ≤ n ≤ N; its running time is O(N^3/2 / sqrt(log N)) and the needed memory is O(N); it allows computing g(n) up to, say, one million. We describe an algorithm to calculate g(n) for n up to 10¹⁵. The main idea is to use the so-called l-superchampion numbers. Similar numbers, the superior highly composite numbers, were introduced by S. Ramanujan to study large values of the divisor function tau(n) which counts the divisors of n. A Maple program implementing the algorithm described in this paper is available from Jean-Louis Nicolas web page.

Somme des nombres premiers jusqu'à 10ⁿ

Soit f une fonction définie sur l'ensemble des entiers strictement positifs. On note S_f(x) la somme des f(p) pour p premier inférieur ou égal à x. Si f est la fonction constante égale à 1, S_f(x) est le nombre π(x) des nombres premiers jusqu'à x. Si f = id est la fonction identité, (i.e. f(p) = p), S_f(x) est la somme des nombres premiers jusqu'à x. La méthode de Lagarias-Miller et Odlyzko, améliorée par Deleglise et Rivat, pour calculer π(x) en temps O(x^(2/3)/log^2 x) peut s'adapter au calcul de S_f(x), lorsque f est une fonction complètement multiplicative, c'est à dire telle que f(ab) = f(a)f(b) pour tous entiers a,b ≥ 1. Eric Bach a montré (congres ANT mai 2007 à Turku, à paraitre) que la méthode peut s'adapter à une classe encore plus générale de fonctions. Voici la table des S_id(10ⁿ) pour n = 2, 3, … , 18. La plus grande valeur connue jusqu'à présent (juin 2007) était S_id(10¹³). La suite (S_id(10ⁿ)) est la suite A046731 dans l'encyplopédie de Sloane.

Compter les nombres premiers de la forme 4k+1 et 4k+3

On note pi(x,k,j) le nombre des nombres premiers ≤ x et de la forme ak + j. Les suites des pi(10ⁿ, 4, 1) et pi(10ⁿ, 4, 3) sont les suites A091098 et A091099 dans l'encyclopédie de Sloane.

Voici une table des valeurs de pi(x, 4, 1) et pi(x, 4, 3), pour x = 10, 100, …, 10²⁰. On pourra consulter l'article Counting primes in residue classes pour plus de détails.

Le 10ⁿ ème nombre premier

La suite dont le n^ème élément est le nombre premier de rang 10ⁿ est la suite A006988 dans l'encyclopédie de Sloane. Tout programme qui calcule pi(x), le nombre des nombres premiers jusqu'à x, permet, pour le même coût, de calculer le n^eme nombre premier pour n inférieur à x/log x. La table 10ⁿ ème prime donne les 19 premiers termes de cette suite. Aujourd'hui (juin 2008), 19 est la plus grande valeur de n pour laquelle on connait le 10ⁿ ème nombre premier.

Tables des 761 premiers champions de la fonction de Kalmar

La fonction K de Kalmar associe à l'entier n le nombre K(n) des factorisations de n en un produit d'entiers plus grands que 1, en tenant compte de l'ordre des facteurs. Par exemple, pour n = 6, les 3 factorisations 6 , 2 * 3 , 3 * 2 donnent K(6) = 3. Soit f une fonction réelle définie sur l'ensemble des entiers naturels non nuls. Un champion de f est un entier n, tel que, pour tout m < n on ait f(m) < f(n). Avec J.-L. Nicolas, et M.O. Hernane, nous avons précisé l'ordre maximal et les propriétés des nombres champions de la fonction de Kalmar, dans Grandes valeurs de la fonction arithmétique de Kalmár. Voici la table des 761 premiers champions de la fonction de Kalmar.