Image Escher

Quelques Calculs

Accueil

Valeurs de la fonction Theta de Chebychev

Soit θ et ψ les fonctions de Chebychev définies par θ(x)= Σp ≤ x log p et ψ(x) = Σpn ≤ 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. 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.

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

Calcul de la fonction de Landau

Landau's function for one million billions, with Jean-Louis Nicolas and Paul Zimmermann. preprint, February 2008. Let Sn denote the symmetric group with n letters, and g(n) the maximal order of an element of Sn. If the standard factorization of M into primes is M=q1a1 q2a2… qkak, we define l(M) to be q1a1 + q2a2 + … + qkak; one century ago, E. Landau proved that g(n)=maxl(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(N3/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 1015. 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'à 10n

Soit f une fonction définie sur l'ensemble des entiers strictement positifs. On note Sf(x) la somme des f(p) pour p premier inférieur ou égal à x. Si f est la fonction constante égale à 1, Sf(x) est le nombre π(x) des nombres premiers jusqu'à x. Si f = id est la fonction identité, (i.e. f(p) = p), Sf(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 Sf(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 Sid(10n) pour n = 2, 3, … , 18. La plus grande valeur connue jusqu'à présent (juin 2007) était Sid(1013). La suite (Sid(10n)) 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(10n, 4, 1) et pi(10n, 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, …, 1020. On pourra consulter l'article Counting primes in residue classes pour plus de détails.

Le 10n ème nombre premier

La suite dont le nème élément est le nombre premier de rang 10n 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 neme nombre premier pour n inférieur à x/log x. La table 10n è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 10n è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.