Une fonction arithmétique

c-math · February 2019

Bonjour,
j'ai lu dans un magazine ce joli problème d'arithmétique, et je souhaite le partager avec vous. Je donnerai, plus tard, la référence exacte de cet exercice.

Pour tout entier $n\geq 1$, on désigne par $f(n)$ le nombre de chiffres $2$ qui apparaissent dans l'écriture (en base $10$) de la suite $1,2,3,\cdots,n$. Par exemple $f(25)=9$ puisque le chiffre $2$ apparaît une fois dans $2,12,20,21,23,24,25$ et apparaît deux fois dans $22$.

On cherche à trouver un entier $n$ tel que $f(n)=n$, et dire éventuellement s'il existe une infinité de solutions de l'équation $f(n)=n$.

nicolas.patrois · February 2019

n=1
c=0

while True:
  c+=str(n).count("2")
  if n==c:
    print(n)
  n+=1

Affiche 28263827, 35000000, 242463827, 500000000, 528263827, 535000000…

c-math · February 2019

Merci beaucoup nicolas.patrois .
Je serais curieux de savoir s'il existe une démonstration qui ne fait pas appel au calcul formel.

reuns · February 2019

$f(10^k) = ?$

nicolas.patrois · February 2019

À propos, mon script donne ensuite : 10000000000, 10028263827, 10035000000, 10242463827, 10500000000, 10528263827, 10535000000…

babsgueye · February 2019

Salut.
Je jente une formule récursive

$f(1) = 0$
$f(10) = 1$
$f(100) = 9f(10) + 8f(10) + 2 = 16$
$f(1000) = 9f(100) + (8f(10) + 2)f(100) + 3 = 259$
.....
$f(10^k] = 9f(10^{(k-1)}) + (\cdots (8f(10) + 2)f(100) + 3)f(1000) +4)\cdots)f(10^{(k-1)} + k$.

Amicalement.

PS: rectifié après les posts de @depasse et @Al Kashi

depasse · February 2019

Bonsoir,

Babsgueye,

l'un au moins de nous deux se trompe;

Je pense que

$f(10^k)=k10^{k-1}$

Paul

Al-Kashi · February 2019

Salut depasse,

Je pense comme toi: Tout d'abord $f(100)=20=2*10^{2-1}$.
On a ensuite $f(1000)=9f(100)+f(100)+100=300=3*10^{3-1}$ Une récurrence permet de conclure.

Al-Kashi

babsgueye · February 2019

Je change mon $5$ par $8$. C'est l'exemple du message initial que m'a induit en erreur car pour $100$ j'avais raisonné comme pour $25$.

Mais on compte facilement que $f(100) = 19$ et non pas $20$ comme vous le dites. Vous êtes alors en erreur.

lourrran · February 2019

Je compte et je recompte, et je trouve $f(100) = 20$ .
On peut vérifier autrement :
Ente 0 et 99, il y a 100 nombres. On va convenir que pour écrire les nombres, on complète à gauche avec des 0 si nécessaire, et on écrit tous les nombres sur 2 chiffres.
Ca ne change rien dans le décompte du nombre de 2 , ça change uniquement pour le décompte du nombre de 0.
Et, bonne nouvelle, ça introduit une certaine symétrie, et ça nous dit ; $$
f_0(99) = f_1(99) = f_2(99) =\cdots= f_9(99) .
$$ Je n'explicite pas les notations, je pense que c'est évident.
Comme par ailleurs , nos 100 nombres ont chacun 2 chiffres, donc $ f_0(99) + f_1(99) + \cdots + f_9(99) = 200 $
Ces équations nous permettent de retomber sur le calcul 'à la main' : $$ f_0(99) = f_1(99) = f_2(99) =\cdots = f_9(99) = 20 .

$$ Et accessoirement, cette façon d'écrire les nombres en les complétant à gauche par des 0 permet de valider les résultats déjà donnés pour $10^k$ : $ f_i(999) = 300,\ f_i(9999) = 4000$ ...

babsgueye · February 2019

C'est vrai, je n'avais pas compté trois fois !

nodgim · February 2019

Ce problème est intéressant.

Le fait de compter le nombre de 2 plutôt qu'un autre chiffre a t 'il une signification particulière ?

En tout cas, il me semble que le nombre de solutions devrait être fini pour un chiffre donné. En effet, pour les nombres de 11 chiffres, l'ensemble des chiffres est 11 fois plus élevé que le nombre lui même, soit, avec une répartition égale ( sauf pour le zéro) plus de chiffres d'une valeur donnée que de nombres. Et bien entendu la supériorité du nombre de chiffres va s'accentuer avec les nombres plus grands, de sorte qu'à un moment donné, chacun des chiffres sera définitivement en quantité supérieure à un nombre donné.

lourrran · February 2019

Le nombre de solutions est infini.
Si on se limite aux solutions de la forme $10^k$, on a $10^{10}$ , $10^{100}$, ... et en fait tous les nombres de la forme $10^{10^k}$ sont des solutions

Le résultat $f(10^k) = k*10^{k-1}$ donné par DEPASSE nous permet de l'affirmer.

Si on remplace 2 par 3 4 5 6 7 8 ou 9, tous ces nombres restent valables.
Si on remplace 2 par 0 ou 1, alors ces solutions ne sont plus valables, mais on a toujours une infinité de solutions.

Edit : convaincu par le message de JLT... j'ai tout faux.

JLT · February 2019

Si $n$ est un nombre à $k+1$ chiffres tel que $f(n)=n$, alors $10^{k+1}> n=f(n)\geqslant f(10^k)=k10^{k-1}$ donc $k<100$.

Par conséquent, si $n=f(n)$ alors $n$ a au plus $100$ chiffres.

nodgim · February 2019

Dans la pratique, j'avance qu'avec des nombres à 15 chiffres, on est déjà assuré d'avoir f(n) > n.

reuns · February 2019

On compte le chiffre $2$. Alors $f(10^k) =f(10^k-1)= k 10^{k-1}$ (regarder $\{0,\ldots 9\}^k$)

pour $m \in [1,9[,n \in [0, 10^k-1]$, $f(m.10^k+n) = m f(10^k)+f(n) + (n+1) 1_{m =2} + f(10^k) 1_{m \ge 3}= (m+1_{m \ge 3}) k 10^{k-1} + f(n) + (n+1) 1_{m=2}$

on peut appliquer la même formule récursivement au $f(n)$.

comment faire pour délimiter un nombre fini d'intervalles de taille beaucoup plus petite que $10^{10}$ où il est plausible que $f(N) = N$ ?

nodgim · February 2019

En effet, la recherche de l'intervalle des transitions possibles ( et donc égalités possibles) entre f(n) et n est la 1ère chose à faire.

On a pour les nombres à 9 chiffres max ( jusqu'à 10 ^ 9 - 1) : 9 * 10 ^ 8 chiffres 2 (ou tout autre que 0)

Pour les nombres à 10 chiffres max ( jusqu'à 10^10 - 1) : 10 ^10 chiffres 2 .

Pour les nombres à 11 chiffres max ( jusqu'à 10 ^ 11 - 1) : 1,1 * 10 ^ 11 chiffres 2.

Pour rattraper l’excès des chiffres 2 au delà des nombres à 11 chiffres, soit 10 ^ 10 chiffres 2, il faut au minimum aller jusqu'à 10 ^ 11 + 10 ^ 10, mais dans ce cas, on obtient 1,2 * 10^11 chiffres 2, on n'a rien gagné, et on ne gagnera plus rien par la suite.

Moralité: il n'y a pas de solution pour les nombres à moins de 10 chiffres ou à plus de 11 chiffres.

Après, je doute qu'on puisse trouver une méthode analytique pour la recherche des solutions dans cet intervalle.

Cependant, on doit pouvoir encore réduire l'intervalle de recherche.

nicolas.patrois · February 2019

Mon script doit être faux parce qu'il donne des solutions à huit et à neuf chiffres. :-D

nodgim · February 2019

Rassure toi, ton script est correct, 28263827 est bien solution.

J'ai eu le tort de trop globaliser mes calculs pour la limite inférieure, en revanche je maintiens la limite supérieure : nombre à 12 chiffres.

depasse · February 2019

Bonjour à tous,

Reuns a écrit:

pour $m \in [1,9[,n \in [0, 10^k-1]$,
$f(m.10^k+n)
= m f(10^k)+f(n) + (n+1) 1_{m =2} + f(10^k) 1_{m
\ge 3}$

Je dirais plutôt;

pour $k \in \mathbb N^*$, pour $m \in [1,9],n \in [0, 10^k-1]$,
$f(m.10^k+n)
= m f(10^k)+f(n) + (n+1) \times 1_{m =2} + 10^k \times 1_{m
\ge 3}$

A voir!

Cordialement
Paul

depasse · February 2019

Quelques conséqences:

Avec les notations ci-dessus:

1) $ f(2.10^k+n) - (2.10^k+n) = f(n) + 2.10 ^{k-1}(k-10) +1 =0$
implique $k<10$. Autrement dit si une solution commence par $2$ elle a au plus $10$ chiffres.

2)$ f(10^{10}+n) - (10^{10}+n) = f(n)-n$.
Par conséquent, si $n$ est solution et a au plus $10$ chiffres, $10^{10}+n$ est solution.

3)Si $m \geq 3$, $ f(m.10^k+n) - (m.10^k+n) = f(n)-n + 10^{k-1} (m(k-10) +10)$.
Donc $f(5.10^8+n)-(5.10^8+n) = f(n) - n$.
Par conséquent, si $n$ est solution et a au plus $8$ chiffres, $5.10^8+n$ est solution.

De la solution $0$ et des trois solutions (merci Nicolas) $28263827, 35000000, 242463827$ dont le nombre de chiffres est $8, 8, 9$, on déduit les solutions

$500000000, 528263827, 535000000$ en utilisant 3). Ils ont $9$ chiffres.

$10000000000, 10028263827, 10035000000, 10242463827,$
$10500000000, 10528263827, 10535000000$ en utilisant 2).

Las, les trois petits points qui suivent le dernier affichage de Nicolas laissent penser que mes trois remarques sont insuffisantes pour trouver toutes les solutions à partir de ses trois premières.

Me donnera-t-il la solution suivante?

Cordialement

Paul

Edit: correction typo

nicolas.patrois · March 2019

J’ai arrêté mon script parce que les dernières solutions sont venue en gros une journée après son lancement.

etanche · March 2019

$10^{10}$ est une solution de $f(n)=n$.

Si $n> 10^{100}$ il n'y a pas de solution de $f(n)=n$ je crois.

nodgim · March 2019

Nicolas Patrois a écrit:

J’ai arrêté mon script parce que les dernières solutions sont venue en gros une journée après son lancement.

Connais-tu le temps que ta machine a cherché après la dernière valeur trouvée ?
Parce que je crois qu'il n'y a pas d'autres solutions.
À noter, trouvé à la main par une suite dichotomique : $$

f ( 12 222 222 221) = 12 222 222 220.$$

nicolas.patrois · March 2019

Non mais il a tourné environ une journée entière (24h).

nodgim · March 2019

Dommage, tant pis.

c-math · March 2019

Bonjour,

merci pour vos contributions.

Comme promis, je donne la référence de l'exercice. C'est un problème qui a été publié dans la revue Mathematics Magazine (publication de la MAA), l'auteur est Enrique Trevino.

Une fonction arithmétique

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 24