Rédaction en cours.
Accueil / Divers / Nombres cumulés des chiffres

Nombres cumulés des chiffres des entiers de 1 à n

Description

Comptez le nombre de chiffres c=1 utilisés pour écrire tous les nombres 1, 2, 3, 4, 5, ..., 253, 254. Recommencez avec c=0 ou c=2...

Le faire à la main en écrivant réellement tous ces entiers est fastidieux.
Écrire un simple programme qui scrute tous les nombres de 1 à n=254, les uns après les autres est faisable.
Cependant un tel programme sera pas particulièrement lent pour de grandes valeurs de n. Le temps de calcul sera peut-être de l'ordre de n*log(n).

Le temps de calcul du programme de cette page sera approximativement proportionnel au nombre de chiffres de n, (en O(log n)).
Le chiffre $ c $ étant donné, le nombre de chiffres $ c $ est bien évidemment une fonction croissante de $ n $. Il est facile de voir à l'aide d'un contre exemple que cette fonction $ f_c $ n'est pas strictement croissante, par exemple si $ c=1 $ f_1(22) = f_1(23) $.

Calculs

Dans la base de numération $ b \ge 2 $, les nombres entiers $n$ sont écrits avec les chiffres de $0$ à $ b-1 $. Habituellement on utilise les chiffres ou lettres 0, 1, 2, ..., 8, 9, A, B, C, D, E, F, ... ce qui permet d'utiliser les bases b jusquà b=36.
Entrez les valeurs du nombre $n$ et de la base $b$.
(Attention : les calculs sont effectués en simple précision et en javascript, pour cette raison les résultats ne sont exacts que pour des valeurs de $ n $ relativement petites).

Valeurs


Écriture décimale du nombre n = , base de numération b = pour écrire tous les nombres.

  


Résultats

Algorithmes
Soit $n$ positif, non nul de décomposition $\displaystyle n = a_0+a_1 b+ a_2 b^2+\cdots + a_i b^i+\cdots + a_k b^k $ dans la base $ b $ avec $ \forall i, 0\leq a_i < b $ et $ a_k>0 $.
$\displaystyle n = \overline{a_k a_{k-1}\cdots a_i\cdots a_2 a_1 a_0} $ est la notation habituelle de l'écriture de $ n $ dans la base $ b $, les chiffres correspondent aux valeurs $\displaystyle a_k, a_{k-1},\cdots , a_i, \cdots , a_2, a_1, a_0 $.
On notera $\displaystyle p_i = \overline{a_k a_{k-1}\cdots a_{i+1}} = a_k b^k+a_{k-1}b^{k-1}+\cdots+a_{i+1}b^{i+1}$
et $\displaystyle r_i = \overline{a_{i-1}\cdots a_2 a_1 a_0 } = a_{i-1}b^{i-1}+\cdots a_2b^2+ a_1 b + a_0 $,
bien entendu $p_k$ est nul ainsi que $r_0$.

L'algorithme de recherche du nombre de chiffres $c$ utilisés pour écrire tous les entiers de $1$ à $n$ n'est pas le même selon que $c$ est nul ou pas.

Chiffre non nul

Soit le chiffre $c$, ($ c >0 $ et $ c < b $).
Pour toutes les positions $ i $ de $ 0 $ à $ k $ des chiffres de l'écriture $\displaystyle \overline{a_k a_{k-1}\cdots a_i\cdots a_2 a_1 a_0} $ de $ n $, on compare $ c $ au chiffre $ a_i $ :
– Si $ c $ est différent de $ a_i $ on note $ u_i $ la valeur $ u_i = (p_i + 1) \times b^{i} $.
– Si $ c $ et $ a_i $ sont égaux, alors on prend $ u_i = p_i \times b^{i} + r_i + 1 $.
Le nombre de chiffres $ c $ utilisés pour écrire dans la base $ b $ tous les nombres de $ 1 $ à $ n $ est la somme $\displaystyle \sum_{i=0}^{i=k} u_i $.

Chiffre zéro

Une remarque : Le chiffre le plus à gauche de l'écriture d'un entier non nul n'est jamais le zéro, c'est ce qui explique que le nombre de zéros se calcule différemment des nombres des autres chiffres non nuls.
Pour toutes les positions $ i $ de $ 0 $ à $ k - 1 $ des chiffres de l'écriture $\displaystyle \overline{a_k a_{k-1}\cdots a_i\cdots a_2 a_1 a_0} $ de $ n $ :
– Si $ a_i $ est différent de $ 0 $, alors $ u_i = p_i\times b^i $.
– Si $ a_i = 0 $, alors $\displaystyle u_i = (p_i -1)\times b^i + r_i + 1 $.
Le nombre de chiffres $ 0 $ utilisés pour écrire dans la base $ b $ tous les nombres de $ 1 $ à $ n $ est la somme $\displaystyle \sum_{i=0}^{i=k-1} u_i $.

Tous les chiffres

On peut calculer et additionner les sommes des zéros, des uns, deux etc.
On peut aussi calculer directement le nombre total de tous les chiffres utilisés, par l'algorithme ci-dessous.
$\displaystyle (k+1)(n+1-b^{k}) + \sum_{i=0}^{i=k-1}(b-1)\times b^i\times(i+1) $.

Le tableau des résultats des calculs précédents donne le nombre total des chiffres selon les deux méthodes.
















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014