Enigme Entiers sans zéro 2/2 @ Prise2Tete

nodgim · #26

@masab: c'est OK, mais c'est loin de prendre en compte tous les cas.

nodgim · #27

Là je suis d'accord Gwen bravo !
C'est une méthode assez différente de la mienne. Ton procédé est assez alambiqué, mais très efficace à l'arrivée.

gwen27 · #28

Pas facile d'expliquer des trucs clairement parfois surtout pour moi
En fait, "par groupes de 9 (x9 x9 x9 ...)" je n'utilise que le critère de divisibilité par 9 grâce à la factorisation à chaque étape.

Un exemple partiel était plus parlant finalement .

masab · #29

C'est effectivement loin de prendre en compte tous les cas !
Mais ça donne une formule donnant une infinité d'entiers divisibles par la somme de leurs chiffres.

nodgim · #30

@masab: tu as raison, mais si on suppose que si pour tout k il y a une solution,
alors la proportion des solutions que tu as prouvées est assez maigre dans N.

@Gwen: oui, c'était bien clair avec l'exemple. Il aurait fallu que tu indiques clairement les décalages à chaque étape dans ton explication. Je l'ai refait et c'est devenu évident.
Sinon, je viens de trouver un bug dans ma solution en la rédigeant, ce qui fait que je n'ai que 96% des nombres, et non 100 % comme toi.

masab · #31

On va donner une solution pour 100% des valeurs de k.

On note
[TeX]\displaystyle \quad f(k) = \frac{10^k-1}{9}\,.[/TeX]
f(k) est un entier à k chiffres tous égaux à 1.

Dans un message précédent on a prouvé que [latex]f(3^r)[/latex] est divisible par [latex]3^r[/latex].

Soit [latex]k\geq 1[/latex] un entier.

Il existe [latex]r\geq 0[/latex] entier tel que [latex]9^r<k\leq 9^{r+1}[/latex].

Il existe des entiers [latex]q ,u[/latex] tels que [latex]k = 9^r\,q+u[/latex], [latex]q\geq 0[/latex], [latex]1\leq u\leq 9^r[/latex].
C'est une forme de la division euclidienne.
On a alors [latex]1\leq q<9[/latex].

On considère l'entier sans zéro n défini par
[TeX]n = f(k) + (9-q)\,f(9^r)-f(u)[/TeX]
Alors [latex]n[/latex] possède [latex]k[/latex] chiffres et la somme des chiffres de [latex]n[/latex] est égale à [latex]s(n)=9^{r+1}[/latex].
De plus [latex]n[/latex] est divisible par la somme de ses chiffres.

Preuve
On a [latex]10^{9^r} = 1 + 9\times f(9^r)[/latex] donc [latex]10^{9^r}[/latex] est congru à [latex]1[/latex] modulo [latex]9\times f(9^r)[/latex].
On divise [latex]n[/latex] en blocs de [latex]9^r[/latex] chiffres à partir de la droite, on fait la somme de ces blocs.
Cette somme est égale à [latex]9\times f(9^r)[/latex] ; par suite [latex]n[/latex] est congru à [latex]0[/latex] modulo [latex]9\times f(9^r)[/latex].
Autrement dit n est divisible par [latex]9\times f(9^r)[/latex].
Or on a vu dans un message précédent que [latex]f(9^r)[/latex] est divisible par [latex]9^r[/latex].
Donc [latex]n[/latex] est divisible par [latex]9^{r+1} = s(n)[/latex].
cqfd

On a explicité ci-dessous les valeurs de n pour 1<=k<=90 :

Code:

k=1  r=0  q=1  u=0  n=9
k=2  r=0  q=2  u=0  n=18
k=3  r=0  q=3  u=0  n=117
k=4  r=0  q=4  u=0  n=1116
k=5  r=0  q=5  u=0  n=11115
k=6  r=0  q=6  u=0  n=111114
k=7  r=0  q=7  u=0  n=1111113
k=8  r=0  q=8  u=0  n=11111112
k=9  r=0  q=9  u=0  n=111111111
k=10  r=1  q=1  u=1  n=1999999998
k=11  r=1  q=1  u=2  n=11999999988
k=12  r=1  q=1  u=3  n=111999999888
k=13  r=1  q=1  u=4  n=1111999998888
k=14  r=1  q=1  u=5  n=11111999988888
k=15  r=1  q=1  u=6  n=111111999888888
k=16  r=1  q=1  u=7  n=1111111998888888
k=17  r=1  q=1  u=8  n=11111111988888888
k=18  r=1  q=2  u=0  n=111111111888888888
k=19  r=1  q=2  u=1  n=1111111111888888887
k=20  r=1  q=2  u=2  n=11111111111888888877
k=21  r=1  q=2  u=3  n=111111111111888888777
k=22  r=1  q=2  u=4  n=1111111111111888887777
k=23  r=1  q=2  u=5  n=11111111111111888877777
k=24  r=1  q=2  u=6  n=111111111111111888777777
k=25  r=1  q=2  u=7  n=1111111111111111887777777
k=26  r=1  q=2  u=8  n=11111111111111111877777777
k=27  r=1  q=3  u=0  n=111111111111111111777777777
k=28  r=1  q=3  u=1  n=1111111111111111111777777776
k=29  r=1  q=3  u=2  n=11111111111111111111777777766
k=30  r=1  q=3  u=3  n=111111111111111111111777777666
k=31  r=1  q=3  u=4  n=1111111111111111111111777776666
k=32  r=1  q=3  u=5  n=11111111111111111111111777766666
k=33  r=1  q=3  u=6  n=111111111111111111111111777666666
k=34  r=1  q=3  u=7  n=1111111111111111111111111776666666
k=35  r=1  q=3  u=8  n=11111111111111111111111111766666666
k=36  r=1  q=4  u=0  n=111111111111111111111111111666666666
k=37  r=1  q=4  u=1  n=1111111111111111111111111111666666665
k=38  r=1  q=4  u=2  n=11111111111111111111111111111666666655
k=39  r=1  q=4  u=3  n=111111111111111111111111111111666666555
k=40  r=1  q=4  u=4  n=1111111111111111111111111111111666665555
k=41  r=1  q=4  u=5  n=11111111111111111111111111111111666655555
k=42  r=1  q=4  u=6  n=111111111111111111111111111111111666555555
k=43  r=1  q=4  u=7  n=1111111111111111111111111111111111665555555
k=44  r=1  q=4  u=8  n=11111111111111111111111111111111111655555555
k=45  r=1  q=5  u=0  n=111111111111111111111111111111111111555555555
k=46  r=1  q=5  u=1  n=1111111111111111111111111111111111111555555554
k=47  r=1  q=5  u=2  n=11111111111111111111111111111111111111555555544
k=48  r=1  q=5  u=3  n=111111111111111111111111111111111111111555555444
k=49  r=1  q=5  u=4  n=1111111111111111111111111111111111111111555554444
k=50  r=1  q=5  u=5  n=11111111111111111111111111111111111111111555544444
k=51  r=1  q=5  u=6  n=111111111111111111111111111111111111111111555444444
k=52  r=1  q=5  u=7  n=1111111111111111111111111111111111111111111554444444
k=53  r=1  q=5  u=8  n=11111111111111111111111111111111111111111111544444444
k=54  r=1  q=6  u=0  n=111111111111111111111111111111111111111111111444444444
k=55  r=1  q=6  u=1  n=1111111111111111111111111111111111111111111111444444443
k=56  r=1  q=6  u=2  n=11111111111111111111111111111111111111111111111444444433
k=57  r=1  q=6  u=3  n=111111111111111111111111111111111111111111111111444444333
k=58  r=1  q=6  u=4  n=1111111111111111111111111111111111111111111111111444443333
k=59  r=1  q=6  u=5  n=11111111111111111111111111111111111111111111111111444433333
k=60  r=1  q=6  u=6  n=111111111111111111111111111111111111111111111111111444333333
k=61  r=1  q=6  u=7  n=1111111111111111111111111111111111111111111111111111443333333
k=62  r=1  q=6  u=8  n=11111111111111111111111111111111111111111111111111111433333333
k=63  r=1  q=7  u=0  n=111111111111111111111111111111111111111111111111111111333333333
k=64  r=1  q=7  u=1  n=1111111111111111111111111111111111111111111111111111111333333332
k=65  r=1  q=7  u=2  n=11111111111111111111111111111111111111111111111111111111333333322
k=66  r=1  q=7  u=3  n=111111111111111111111111111111111111111111111111111111111333333222
k=67  r=1  q=7  u=4  n=1111111111111111111111111111111111111111111111111111111111333332222
k=68  r=1  q=7  u=5  n=11111111111111111111111111111111111111111111111111111111111333322222
k=69  r=1  q=7  u=6  n=111111111111111111111111111111111111111111111111111111111111333222222
k=70  r=1  q=7  u=7  n=1111111111111111111111111111111111111111111111111111111111111332222222
k=71  r=1  q=7  u=8  n=11111111111111111111111111111111111111111111111111111111111111322222222
k=72  r=1  q=8  u=0  n=111111111111111111111111111111111111111111111111111111111111111222222222
k=73  r=1  q=8  u=1  n=1111111111111111111111111111111111111111111111111111111111111111222222221
k=74  r=1  q=8  u=2  n=11111111111111111111111111111111111111111111111111111111111111111222222211
k=75  r=1  q=8  u=3  n=111111111111111111111111111111111111111111111111111111111111111111222222111
k=76  r=1  q=8  u=4  n=1111111111111111111111111111111111111111111111111111111111111111111222221111
k=77  r=1  q=8  u=5  n=11111111111111111111111111111111111111111111111111111111111111111111222211111
k=78  r=1  q=8  u=6  n=111111111111111111111111111111111111111111111111111111111111111111111222111111
k=79  r=1  q=8  u=7  n=1111111111111111111111111111111111111111111111111111111111111111111111221111111
k=80  r=1  q=8  u=8  n=11111111111111111111111111111111111111111111111111111111111111111111111211111111
k=81  r=1  q=9  u=0  n=111111111111111111111111111111111111111111111111111111111111111111111111111111111
k=82  r=2  q=1  u=1  n=1999999999999999999999999999999999999999999999999999999999999999999999999999999998
k=83  r=2  q=1  u=2  n=11999999999999999999999999999999999999999999999999999999999999999999999999999999988
k=84  r=2  q=1  u=3  n=111999999999999999999999999999999999999999999999999999999999999999999999999999999888
k=85  r=2  q=1  u=4  n=1111999999999999999999999999999999999999999999999999999999999999999999999999999998888
k=86  r=2  q=1  u=5  n=11111999999999999999999999999999999999999999999999999999999999999999999999999999988888
k=87  r=2  q=1  u=6  n=111111999999999999999999999999999999999999999999999999999999999999999999999999999888888
k=88  r=2  q=1  u=7  n=1111111999999999999999999999999999999999999999999999999999999999999999999999999998888888
k=89  r=2  q=1  u=8  n=11111111999999999999999999999999999999999999999999999999999999999999999999999999988888888
k=90  r=2  q=1  u=9  n=111111111999999999999999999999999999999999999999999999999999999999999999999999999888888888

portugal · #32

J'ai une piste.

L'idée est de constituer une suite d'ensemble de nombres "En" tels que les éléments de En vérifient chacun :

- la somme de ses chiffres est égale à 9*2^n
- Le nombre composé de ses n derniers chiffres est le plus petit nombre de n chiffres divisible par 2^n qui ne contient pas de 0 que l'on note Kn

La somme des chiffres restant à placer est donc 9*2^n-Kn soit autant de 1 que l'on peut placer devant le postfix de divisibilité par 2^n

Il y a différentes vérifications à faire. La méthode permet elle d'aboutir ?

nodgim · #33

@Portugal: je ne crois pas que tu puisses aboutir, pour les raisons que j'ai déja expliquées plus haut.

@masab: q<=0 ?

nodgim · #34

@ fix33: je ne t'ai pas répondu car, même si l'idée semble bonne, tu n'apportes pas la moindre preuve de ce que tu avances. Il faut creuser un peu.

nodgim · #35

@masab: u est il le reste de la division de k par 9^r ?

masab · #36

Ce n'est pas tout à fait le reste habituel ; c'est le reste au sens
[TeX]\ a = b\,q+r\quad \mathrm{avec}\quad 1\leq r\leq b[/TeX]
Habituellement on impose [latex]\ \quad 0\leq r < b[/latex]

MrHall · #37

Soit k le nombre de chiffres dans tout nombre recherché. Soit X l'ensemble des nombres entiers naturels qui ne possèdent aucun zéro. Soit P la proportion de nombres appartenant à X et divisible par la somme de leurs propres chiffres, par rapport à la totalité des nombres appartenant à X.

J'ai établi empiriquement que P(k) est une décroissance exponentielle, proche de P(k) = 4,10935 * e^(-1,42233). La proportion P de nombres divisibles par la somme de leurs chiffres diminue par rapport au nombre k de leur chiffres, P n'atteint jamais zéro.

Ensuite, soit Q la quantité de nombres entiers n'ayant aucun chiffre zéro et divisibles par la somme de leurs chiffres. Alors Q(k) = 0,173298 * e^(2,03862). Les nombres qui ne comportent ni chiffre zéro et qui sont divisibles par la somme de leurs chiffres deviennent de plus en plus nombreux (croissance exponentielle) au fur et à mesure que k augmente. Par conséquent, dans l'ensemble des nombres naturels, il existe une infinité de nombres n'ayant ni zéros dans leurs digits, et étant également divisibles par la somme de leurs chiffres. Testé empiriquement entre le nombre 1 et le nombre 999999999.
Dans l'intervalle [1 ; 999999999], il existe exactement 19 086 485 nombres n'ayant aucun zéro dans leurs digits, et qui sont divisibles par la somme de leurs digits.

Je sais qu'une démonstration mathématique aurait été plus convaincante, mais les outils empiriques au moyen de la programmation informatique sont particulièrement efficaces.

nodgim · #38

@masab: donc c'est bien le reste de la division de k par 9^r, puisque tu mets en préalable que k > 9^r. Je voulais juste être certain que c'était bien la division euclidienne, car tu ne le précises pas.

@Mr Hall: bienvenue sur le site. Difficile en effet de voir tous les cas jusqu'à l'infini avec l'informatique. Même avec une densité nulle de nombres divisibles par la somme de leur chiffre, ça ne veut pas dire qu'il n'y en a pas une infinité.

nodgim · #39

@masab: OK, je valide. La même preuve que Gwen, mais avec une formalisation bien plus acamédique. Bravo à toi.

unecoudée · #40

bonjour.
peut-être en travaillant avec des nombres à k chiffres congrus à 0 (mod9)
la somme S de leurs chiffres est aussi congrue à 0 (mod9).
Maintenant , dans l'écriture de N , on écrit N de cette façon:
N = X S S S S S S S avec [latex]X = 2^m \times S[/latex]

par exemple N est un nombre de k=18 chiffres .S = 81 . Alors :

N = 818181818181818181

si N est un nombre de k=19 chiffres , alors

N = 1628181818181818181 ou 3248181818181818181

si k = 21

N = 162818181818181818181

en raisonnant comme ça : k = 400 par exemple : [latex]S_x[/latex] est la somme des chiffres de X
et [latex]S_s[/latex] est la somme des chiffres de S

pour S à 4 chiffres et Ss =18 , et X a 8 chiffres avec Sx = 27
[TeX]S = S_x + n\times{S_s}[/TeX]
alors S = 27 + 98 x 18

alors : [latex]X = 1791 \times 111\times 2^6 = 12723264[/latex] par exemple

Et N = 12723264 1791 1791 ... (98 fois)...1791 1791 est divisible
par S = 1791 et contient k = 400 chiffres

pour chaque k , il y a plusieurs solutions possibles , après il suffit d'éviter les 0
dans les nombres X et S qui forment le nombre N.

nodgim · #41

@une coudée: une seule solution pour chaque k suffit, maintenant il faut être sûr que ça marche pour tout k. Ce que tu ne prouves pas vraiment pour l'instant.

nodgim · #42

Merci à tous les participants d'avoir sué sur cette énigme pas facile. Et pour cause: il s'agit d'un problème posé en Olympiades internationales. Même si c'est du niveau Lycée, c'est tout de même adressé aux meilleurs.

Mention particulière à Gwen et Masab qui ont pu brillamment en venir à bout, à l'aide de sommes de nombres composés uniquement d'une succession de 9.

J'avais perso cru tenir une solution sans les 9, mais elle s'est avérée fausse en partie. Je donne pour info la démarche que j'avais entreprise.

1) Un nombre n de k chiffres est divisible par un nombre m si on construit n en additionnant des m à n'importe quel rang. Par exemple, pour 5 chiffres, la somme de ces 6 nombres:

12000+
01200+
00120+
00012+
12000+
01200=

26532 qui est divisible par 12.

2) La somme des chiffres du résultat n vaut k fois la somme des chiffres de m si on a construit n avec k fois m et si on s'est arrangé pour qu'à aucun rang l'addition ne dépasse 9.
S(n) = k * S(m)

3) Compte tenu de 1) et 2), il suffit d'additonner m/S(m) fois un nombre m divisible par S(m) pour obtenir un nombre n dont la somme des chiffres est m et divisible par m.

Par exemple 111=37*3.
Il suffit d'additionner 37 fois 111 en répartissant correctement sur k chiffres pour obtenir un nombre divisible par 111.

Le problème qui reste à résoudre est de savoir combien de chiffres au MIN. doit avoir n pour accueillir k fois m sans qu'aucun rang de l'addition des k*m ne dépasse 9. Et combien de chiffres au MAX n peut avoir pour qu'il n'y ait aucun zéro dans le nombre n.

Pour le cas de l'exemple 111:
MIN pour 3 chiffres: 999. ratio R pour un rang: 3/27=1/9. Nb MIN= m*R = 111/9=12,3.. on prend bien sûr la valeur modulo 3 supérieure (car 111 comporte 3 chiifres) donc 15.
Le nombre 111 999 999 999 999 a une somme de chiffres 111 et est divisible par 111.

MAX pour 3 chiffres: 111. ratio R=3/3=1. Nb MAX= m* R= 111/1= 111. On peut écrire un nombre de 111 chiffres MAX divisible par 111 et ayant pour somme de chiffres 111.

Donc pour 15 <= k <= 111, on a toujours une solution par le diviseur 111.

Il faut maintenant trouver les bons nombres pour qu'il y ait superposition d'intervalle.

Avec 12
MIN pour 2 chiffres: 48 R=2/12=1/6 ---> MIN=12/6 = 2. MAX: R=2/3 MAX = 12*2/3= 8

Résolu pour 2 <= k <= 8 par le diviseur 12.

Avec 21
MIN: 84, R=1/6 ---> MIN=21/6=4. MAX: R=2/3 MAX= 14.

4 <= k <= 14 par 21.

Avec 111:
15 <= k <= 111

Avec 201:
MIN:
804+
0804=
8844
R=4/24=1/6---->MIN= 201/6=33,5--->36.

MAX
201+
0201=
2211
R=2/3 ---->MAX=134

Avec 201, solutions pour 36 <= k <= 134.

Avec 1002, solutions pour 168 <= k <= 668
Avec 2001, solutions pour 336 <= k <= 1334
Avec 10002,solutions pour 1670 <= k <= 6668

Général
Avec 100...002 solutions pour 166...6667 <= k <= 666...667 environ
Avec 200...001 solutions pour 33...33336 <= k <= 133...3337 environ

Il existe un vide entre 133... et 166.. soit environ 3,5 % d' inconnues.

nodgim · #43

Ce message pour rendre justice à Godisdead qui avait trouvé la solution la plus simple, sans toutefois l'avoir prouvée formellement....

Dans un autre message, on avait prouvé qu'on pouvait écrire un nombre de n chiffres divisible par 2^n, uniquement avec des 1 et des 2. Il suffit alors, pour notre cas ici, de compléter le nombre à k chiffres pour obtenir que leur somme fasse 2^n.

Exemple, avec un nombre à 47 chiffres.

On vise le nombre 2^7 = 128.

La fin du nombre sera ....2122112.

Reste plus qu'à répartir le reste de la somme 128-11 = 119 dans les 47 - 7 = 40 autres chiffres.

Un aménagement est toutefois à prévoir pour les petites valeurs de k.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#26 - 09-02-2016 19:32:33

entiers dans zéro

#0 Pub

#27 - 09-02-2016 20:05:47

Entiers sanss zéro

#28 - 09-02-2016 20:30:43

Entiers sas zéro

#29 - 09-02-2016 21:07:38

Entiers sasn zéro

#30 - 10-02-2016 08:19:17

Entierss sans zéro

#31 - 12-02-2016 22:54:13

entiets sans zéro

Code:

#32 - 12-02-2016 23:42:18

zntiers sans zéro

#33 - 13-02-2016 07:19:57

rntiers sans zéro

#34 - 13-02-2016 10:54:33

ntiers sans zéro

#35 - 13-02-2016 11:09:36

Entierss sans zéro

#36 - 13-02-2016 13:56:45

entiers sans zéto

#37 - 13-02-2016 17:00:36

Entiiers sans zéro

#38 - 13-02-2016 17:29:14

Entieers sans zéro

#39 - 13-02-2016 17:40:19

Entierrs sans zéro

#40 - 14-02-2016 15:22:50

Enttiers sans zéro

#41 - 14-02-2016 18:53:52

entiers sabs zéro

#42 - 15-02-2016 10:17:40

entoers sans zéro

#43 - 20-03-2020 08:10:47

entiers szns zéro

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums