Décomposer un entier en somme

[anthony_unac]

signifie que je suis passé de la 1ère à la 2ème ligne en faisant: 10^19-
9937510582097494459 = 62489417902505541

Quelle est donc votre décomposition finale ? Vous semblez avoir trouvé une décomposition en 21 termes (si j'ai bien suivi) ce qui est plausible mais ou est elle ?

[nodgim]

Dans la liste que j'ai fournie. Je ne donne que les restes, en fait. Retrouver les termes, c'est faire la différence entre les nb de 2 lignes voisines.

[chan79]

9937510582097494459=






donc ça fait bien les 21 termes de nodgim

Je n'ai pas la preuve qu'on ne peut pas faire mieux

[bolza]

Bonjour,

Moi personnellement, plutôt que de passer par les modulo j'utiliserais l'algorithme suivant :

On sait que les chiffres possibles sont 1,2,4 et 8.
donc j'encadre d'abord le nombre entre deux nombres de la forme 1*10^k, 2*10^k, 4*10^k ou 8*10^k
et je prend la valeur la plus proche.

Par exemple, avec 497 537 :

on a 400 000 <= 497 537 <= 800 000
comme 497 537 est plus proche de 400 000 que de 800 000 je choisit 400 000 :
497 537 = 400 000 + 97 537.

ensuite 80 000 <= 97 537 <= 100 000
comme 97 537 est plus proche de 100 000 que de 80 000, je choisit 100 000 :
497 537 = 400 000 + 100 000 - 2463

2463 est plus proche de 2000 que de 4000 donc :
497 537= 400 000 + 100 000 - 2000 - 463.

463 est plus proche de 400 que de 800 donc :
497 537 = 400 000 + 100 000 - 2000 - 400 - 63.

63 est plus proche de 80 que de 40 donc :
497 537 = 400 000 + 100 000 - 2000 - 400 - 80 + 17.

17 est plus proche de 20 que de 10 :
497 537 = 400 000 + 100 000 - 2000 - 400 - 80 + 20 - 3.

3 est équidistant de 2 et de 4 donc ça n'a pas d'importance :
497 537 = 400 000 + 100 000 - 2000 - 400 - 80 + 20 - 2 -1

Et on peut prouver que cet algorithme donne une solution optimal en faisant une récurrence sur le nombre de chiffre.

L'avantage ici c'est qu'on n'utilise pas le modulo qui est en générale, une opération coûteuse.

[Ben314]

L'avantage ici c'est qu'on n'utilise pas le modulo qui est en générale, une opération coûteuse.

Ch'uis pas trop d'accord là : si on fait les calculs "à la main", je pense que je met pas bien longtemps à te trouver le modulo d'un entier par 10 ou par 20 (seuls modulos nécessaires dans l'algo. de Doraki) si tu me donne un entier même de 10 000 chiffres (a condition bien sûr que tu me donne son écriture en base 10...)
Et si on le fait avec l'ordi., soit on se limite a des entier pas trop grand et le modulo est super rapide, soit on veut manipuler des entiers super grand et on a fortement intérêt, vu les calculs à faire, à les stocker sous forme de chaine de caractères correspondant à leur écriture en base 10 qui donne sans aucun calculs le reste modulo 10 et avec très peu de calculs celui modulo 20.

De plus, il me semble que de partir des unités permet de comprendre bien plus facilement pourquoi on a intérêt à prendre une solution plutôt qu'une autre lorsqu'on a deux possibilités "de même cout" (i.e. ça me semble plus naturel de regarder comment les éventuelles retenues d'addition/soustraction se reportent sur la gauche plutôt que sur la droite)

...et je prend la valeur la plus proche.

Pour dire la même chose autrement, autant je pense qu'effectivement ton "je prend le plus proche" marche, autant je pense que ce n'est pas évident à démontrer proprement vu que, dans l'absolu, 3 est "plus proche" de 0 que 4 alors qu'en terme d'opérations autorisés, c'est 4 qui est préférable à 3 (et je me demande même s'il n'y a pas des contre-exemples montrant qu'on ne doit pas toujours prendre "le plus proche" avec la démarche partant de la gauche)

[bolza]

si on fait les calculs "à la main", je pense que je met pas bien longtemps à te trouver le modulo d'un entier par 10 ou par 20 (seuls modulos nécessaires dans l'algo. de Doraki) si tu me donne un entier même de 10 000 chiffres (a condition bien sûr que tu me donne son écriture en base 10...)
Et si on le fait avec l'ordi., soit on se limite a des entier pas trop grand et le modulo est super rapide, soit on veut manipuler des entiers super grand et on a fortement intérêt, vu les calculs à faire, à les stocker sous forme de chaine de caractères correspondant à leur écriture en base 10 qui donne sans aucun calculs le reste modulo 10 et avec très peu de calculs celui modulo 20.

Oui, je suis d'accord que les modulo 10 et 20 se font très facilement à la main.
Mais pour une machine, modulo 10 elle fait un calcul (alors que l'humain regarde seulement le dernier chiffre).
Et comparé aux opérations d'addition/soustraction et de comparaison (qui sont en générale des circuits en dur dans le processeur) l'opération modulo est plus coutêuse. Si tu stock les nombres dans des chaînes de caractères, tu feras des accès mémoire pour aller lire les nombres en base 10 et l'accès mémoire ce n'est pas l'opération la plus rapide pour une machine (car elle implique un mouvement mécanique).
Après certes on peux gagner un peu de temps si la chaîne de caractère tiens dans le cache, mais ça reste à mon avis un peu plus coûteux). Mais bon en même temps, c'est vrai qu'on n'est pas sur un algorithme d'une grande complexité non plus ^^.

De plus, il me semble que de partir des unités permet de comprendre bien plus facilement pourquoi on a intérêt à prendre une solution plutôt qu'une autre lorsqu'on a deux possibilités "de même cout" (i.e. ça me semble plus naturel de regarder comment les éventuelles retenues d'addition/soustraction se reportent sur la gauche plutôt que sur la droite)

...et je prend la valeur la plus proche.

Pour dire la même chose autrement, autant je pense qu'effectivement ton "je prend le plus proche" marche, autant je pense que ce n'est pas évident à démontrer proprement vu que, dans l'absolu, 3 est "plus proche" de 0 que 4 alors qu'en terme d'opérations autorisés, c'est 4 qui est préférable à 3 (et je me demande même s'il n'y a pas des contre-exemples montrant qu'on ne doit pas toujours prendre "le plus proche" avec la démarche partant de la gauche)

Je ne comprend pas l'exemple avec 3,4 et 0 : pour 3 on a 2 <= 3 <= 4 donc ici trois est aussi proche de 4 que de 2, mais 2+1 ou 4-1 donne le même nombre d'étape.

Pour la preuve, si ça se prouve proprement, par récurrence sur le nombre de chiffre et par étude de cas.
L'idée c'est de montrer que pour diminuer le nombre de chiffre, soit ça se fait en une étape quand c'est possible, soit en deux étapes quand on ne peux pas faire autrement, ce qui montre que le résultat est optimal.

(on doit pouvoir utiliser le même genre de raisonnement avec l'algorithme de Doraki, je pense, je ne sais pas, je n'ai pas essayé)

[Ben314]

Si tu stock les nombres dans des chaînes de caractères, tu feras des accès mémoire pour aller lire les nombres en base 10 et l'accès mémoire ce n'est pas l'opération la plus rapide pour une machine (car elle implique un mouvement mécanique). Après certes on peux gagner un peu de temps si la chaîne de caractère tiens dans le cache, mais ça reste à mon avis un peu plus coûteux). Mais bon en même temps, c'est vrai qu'on n'est pas sur un algorithme d'une grande complexité non plus ^^.

Certes, si ça ne rentre pas dans le cache écrit en alphanumérique ça va être "un peu long" (sic...)
Mais si tu compare le temps qu'il faut pour aller chercher dans la mémoire (non cache) par rapport au temps qu'il faudrait pour appliquer ta méthode, à savoir trouver le k tel que 10^k est de l'ordre du nombre en question (qui ne rentre pas dans le cache en alphanumérique...), ben je pense... que y'a vraiment, mais alors vraiment pas photo sur ce qui est le plus rapide (ou alors toi aussi tu le stocke en alphanumérique et c'est exactement la même chose : soit c'est stocké en AZT et il faut parcourir la chaine pour avoir ton k ET pour avoir le modulo 10, soit on connait d'avance la longueur de la chaine et c'est, à un poil de cul prés, la même chose de récupérer k ou le dernier chiffre)

Je ne comprend pas l'exemple avec 3,4 et 0 : pour 3 on a 2 <= 3 <= 4 donc ici trois est aussi proche de 4 que de 2, mais 2+1 ou 4-1 donne le même nombre d'étape.

Ben... faut bien lire tout lire ce qui est écrit...
Ce que je dit, c'est que sur le principe, ce n'est pas parce qu'un nombre est plus petit (au sens de la relation d'ordre usuelle) qu'un autre que ça prouve qu'il est plus petit au sens du nombre de (avec ) qu'il faut pour le ramener à zéro.
Et je dit aussi que, dans le cas particulier où on cherche le le plus "proche" (au sens du nombre d'opérations à faire) d'un donné, je pense (mais je suis pas 100% sûr) que là, la propriété est vraie, c'est a dire que c'est le même que le le plus "proche" au sens de la relation d'ordre usuelle.
MAIS ça reste à démontrer (et ça me semble pas simple d'où le "pas 100% sûr") : as-tu une preuve ?

Alors que l'algo. de Doraki est bien plus rapide (pas besoin de faire les deux soustractions entre le et les deux les plus proche) et il est quasi immédiat qu'on a bien le résultat optimum.

[Doraki]

ok le coût pour effacer le k-ième chiffre ne dépend pas du choix de comment on a effacé les (k-1) chiffres précédent, donc ça a l'air de marcher.
Du coup ta méthode est beaucoup plus simple à prouver que la mienne.

(je ne dirais pas que ma preuve d'optimalité est quasi immédiate, enfin je l'ai pas faite moi-même lol donc si ça se trouve ben a raison)

Ah aussi, moi j'ai pas besoin de passer dans les nombres négatifs vu que je change le nombre par la droite et pas par la gauche.

[Ben314]

Concernant la "preuve" de l'algo. de Doraki.

La première question à se poser est de savoir si systématiquement, lorsqu'on a le choix entre un truc en deux étapes et un truc en une étape pour rejoindre un multiple de 10, est ce que forcément il faut prendre celui en une étape (i.e. est ce que la suite du processus ne pourrait pas faire que celui en deux étapes est mieux) ?
La réponse est non, car, si celui en deux étapes s'avère mieux par la suite, on pouvait aussi obtenir ce "mieux" en commençant par celui à une étape : par exemple partant de 1, si un optimum consiste à faire -1-8 alors en faisant +1-10 c'est la même chose. Idem par exemple partant de 4 où, si un optimum consiste à faire -8-8 alors on a la même chose en faisant +4-20.

Ensuite on regarde le dernier chiffre :
0 -> rien à faire
1 -> 1
2 -> 2 ou bien -8
3 -> 1 (i.e. on fera 1+2 ou 1-8 en fonction des même critères que pour 2)
4 -> -4
5 -> 4+1 ou bien -4-1
Pour 6,7,8,9 idem en changeant les signes
Ensuite, dans les cas où le nombre se termine par 2 ou 5, on regarde le chiffre précédent :
02 -> 2
12 -> -8 (faire 2 amènerais à 10 où on fera ensuite forcément +10 pour avoir 00 alors qu'en faisant -8 on tombe sur 20 qui permet de faire non seulement 20 mais aussi -80 pour tomber sur 00 dans les deux cas)
22 -> 2 (20 -> une étape ; 30 -> 2 étapes)
32 -> -8 (40 -> une étape ; 30 -> 2 étapes)
42 -> 2 (40 -> une étape ; 50 -> 2 étapes)
52 -> -8 (60 -> une étape ; 50 -> 2 étapes)
Idem pour 62,72,82,92
Exactement les même constatations pour 05,15,25,...,95.
Ce qui amènent a la constatation faite par Doraki qu'il suffit de regarder modulo 20 pour savoir exactement quoi faire.
A mon sens, la seule "mini astuce", c'est dans le cas où on a le choix entre passer à 10 ou a 20 qui sont tout les deux à "un cran" de 00.
Sauf qu'on peut systématiquement prendre le 20 vu qu'il permet ensuite de prendre 20 (qui équivaut a avoir pris 10 partant de 10) ou bien à faire -80 qui ouvre éventuellement de nouvelles portes.

Bilan : l'algo. consiste à faire "au plus simple" si le dernier chiffre est 1,4,6,9 et à rendre l'avant dernier chiffre pair dans les cas ambigües où le dernier chiffre est 2,3,5,7,8.

[bolza]

Certes, si ça ne rentre pas dans le cache écrit en alphanumérique ça va être "un peu long" (sic...)
Mais si tu compare le temps qu'il faut pour aller chercher dans la mémoire (non cache) par rapport au temps qu'il faudrait pour appliquer ta méthode, à savoir trouver le k tel que 10^k est de l'ordre du nombre en question (qui ne rentre pas dans le cache en alphanumérique...), ben je pense... que y'a vraiment, mais alors vraiment pas photo sur ce qui est le plus rapide (ou alors toi aussi tu le stocke en alphanumérique et c'est exactement la même chose : soit c'est stocké en AZT et il faut parcourir la chaine pour avoir ton k ET pour avoir le modulo 10, soit on connait d'avance la longueur de la chaine et c'est, à un poil de cul prés, la même chose de récupérer k ou le dernier chiffre)

.

Oui, c'est vrai qu'il y a la recherche du nombre de chiffre, ce qui revient à faire du modulo
Mais au pire, je peux demander à l'utilisateur d'entrer le nombre de chiffre du nombre qu'il cherche à décomposer ^^

Ben... faut bien lire tout lire ce qui est écrit...
Ce que je dit, c'est que sur le principe, ce n'est pas parce qu'un nombre est plus petit (au sens de la relation d'ordre usuelle) qu'un autre que ça prouve qu'il est plus petit au sens du nombre de (avec ) qu'il faut pour le ramener à zéro.
Et je dit aussi que, dans le cas particulier où on cherche le le plus "proche" (au sens du nombre d'opérations à faire) d'un donné, je pense (mais je suis pas 100% sûr) que là, la propriété est vraie, c'est a dire que c'est le même que le le plus "proche" au sens de la relation d'ordre usuelle.
MAIS ça reste à démontrer (et ça me semble pas simple d'où le "pas 100% sûr") : as-tu une preuve ?

Je ne sais pas ce que je démontre c'est :

l'algorithme est optimal sur les nombre à 1 chiffre.
Supposons que l'algorithme est optimal sur les nombres k chiffres pour k < n.
Montrons alors qu'il est optimal sur les nombres à n chiffres.

Soit donc N un nombre à n chiffres.
Principe :
Soit : N= p*10^n +- r (avec p=1,2,4,8 (ou 10)) si r a un nombre de chiffre strictement plus petit que n
alors l'algorithme est optimal pour N car il ne m'a fallu qu'une seule étape pour réduire le nombre de chiffre.
et avoir une décomposition optimal pour r.
Soit N=p*10^n+- r avec r qui a le même nombre de chiffre que N alors il ne faut qu'une deuxième étape
supplémentaire pour avoir un r' sur lequel j'aurai mon hypothèse de récurrence. Et de plus dans ce cas là il
n'est pas possible de réduire le nombre de chiffre en une seule étape. (Tous ça est partie de l'idée qu'on ne peut pas faire mieux que si on avait les 10 chiffres disponibles).
.
Si j'ai montré ça alors par récurrence l'algorithme est optimal.

Donc ensuite viens toute une série d'étude cas pour le montrer :
(Je donne un exemple avec n=3, mais ça marche pour tout n) :

Les nombre de 1000 à 1500 sont les plus proche de 1000 et
a) si 1000 <= N <= 1500 alors on écrit : N = 1000 + r avec r un nombre qui a strictement moins de 4 chiffres
(une seul étape).

b) de 1501 à 1999 on a N = 2000-r avec r un nombre qui a strictement moins de 4 chiffres
(une seul étape).

c) de 2000 à 2999 on a N=2000+r avec r un nombre qui a strictement moins de 4 chiffres
(une seul étape)

d) N= 3000 on a N= 2000+1000 : optimal.
(une seule étape)

e) de 3001 à 3999 on a N=4000-r avec r un nombre qui a strictement moins de 4 chiffres
(une seule étape)

f) de 4000 à 4999 on a N= 4000+r avec r un nombre qui a strictement moins de 4 chiffres
(une seule étape)

g) de 5000 à 5500 on a : N=4000+r avec 1000<= r <= 1500 on retombe dans le cas a) qui se fait en une seule étape, donc ici il faut 2 étapes pour avoir un r' avec qui a strictement moins de 4 chiffres et on ne peut pas faire moins.
(2 étapes)

h) de 5501 à 5999 on a N= 4000 + r avec 1501 <= r <= 1999 et on tombe dans le cas b)
(2 étapes)

i) N=6000 : N= 4000 + 2000 : optimal.
(une seule étape)

etc

Bon j’arrête là parce que je dois y aller, mais en faisant tous les cas, on a une étapes quand c'est possible et que
deux sinon. (ce que je viens de faire avec n=3 marche tout aussi bien dans le cas général).

Bon après est-ce que c'est plus rapide où pas, effectivement, ce n'est pas si évident ^^.

[Ben314]

Principe :
Soit : N= p*10^n +- r (avec p=1,2,4,8 (ou 10)) si r a un nombre de chiffre strictement plus petit que n
alors l'algorithme est optimal pour N car il ne m'a fallu qu'une seule étape pour réduire le nombre de chiffre.
et avoir une décomposition optimal pour r.
Soit N=p*10^n+- r avec r qui a le même nombre de chiffre que N alors il ne faut qu'une deuxième étape
supplémentaire pour avoir un r' sur lequel j'aurai mon hypothèse de récurrence. Et de plus dans ce cas là il
n'est pas possible de réduire le nombre de chiffre en une seule étape. (Tous ça est partie de l'idée qu'on ne peut pas faire mieux que si on avait les 10 chiffres disponibles).

Pour moi, ton truc ne prouve absolument rien concernant ton algorithme : ce n'est pas parce qu'il est "optimal" sur les nombre à k chiffres que ça prouve qu'il vaut mieux descendre le nombre de chiffres le plus rapidement possible.

La "clef de voute" de ton algo., c'est que, lorsque tu as le choix entre entre dire que N=p*10^n+r ou bien N=p'*10^n- r', tu dit qu'il faut choisir selon que r<r' ou pas pour l'ordre usuel sur les entiers naturels. Alors que la seule chose triviale, c'est qu'il faut choisir selon que r<r' ou pas pour le "presque ordre" induit par le nombre de coups pour arriver à zéro.
Qu'est ce qui te permet d'affirmer que c'est la même chose, c'est à dire qu'il est impossible de tomber sur un truc du style r=3 r'=4 où 3<4 pour l'ordre usuel mais 3>4 pour celui du "nombre de coups" ?
(et je redit que je pense que c'est vrai, mais... c'est pas du tout trivial...)

EDIT : en fait tu as r+r'=(p+p')10^n donc ce qu'il faut montrer, c'est que dans ce cas, r et r' sont dans le même ordre pour l'ordre usuel sur N que pour l'ordre "du nombre de coup"

[nodgim]

Je ne sais pas si c'est un coup de bol, mais la méthode Bolza semble efficace. Je n'arrive pas à la mettre en défaut par un cas particulier.

[anthony_unac]

Je ne pensais pas que cette petite histoire de décomposition déchaînerait autant les passions.
Un grand merci à l'ensemble des participants pour leur lumière sur la question Il me reste à présent à digérer tranquillement les méthodes de M.Bolza et M.Doraki afin de voir la plus simple quand on a qu'une feuille et un crayon.

[Ben314]

Algo Doraki "résumé" :

Faire "au plus simple" si le dernier chiffre est 1,4,6,9 et à rendre l'avant dernier chiffre pair dans les cas ambigües où le dernier chiffre est 2,3,5,7,8.

Exemple avec la valeur 497 537 traitée par PSEUDA çi dessus :
497 537 : 7=ambigü (*) -> rendre le chiffre précédent pair 497 537=497 540-2-1
497 540 : 4=non ambigü -> 497 540=497 500+40
497 500 : 5=ambigü -> rendre le chiffre précédent pair 497 500=498 000-400-100
498 000 : 8=ambigü (**) -> rendre le chiffre précédent pair 498 000=500 000-2 000
500 000 : 5=ambigü -> rendre le chiffre précédent pair 500 000=0 000 000+400 000+100 000

(*) On a le choix entre 37=30+8-1 et 37=40-2-1 et on choisi le second car 4 est pair.
(**) On a le choix entre 498=490+8 et 498=500-2 et on choisi le second car 0 est pair.

A toi de voir si c'est plus rapide ou pas que ce que fait bolza dans son message du 12 Mar 2016 13:08
(à noter qu'on obtient le même nombre de "coups", à savoir 8, mais pas exactement les mêmes)

[anthony_unac]

A toi de voir si c'est plus rapide ou pas que ce que fait bolza dans son message du 12 Mar 2016 13:08
(à noter qu'on obtient le même nombre de "coups", à savoir 8, mais pas exactement les mêmes)

Merci pour ce joli résumé en couleur et tout ...
Ce qui est beau finalement c'est de voir qu'on arrive à une décomposition optimale en prenant des chemins différents (il n'y a pas finalement de décomposition unique à l'ordre près comme c'est le cas avec la décomposition d'un entier en produit de facteurs premiers)

Est ce que vous avez manipulé des gros entiers avec cet algo (mettons un entier de 100 chiffres pour fixer les idées) ?
Le nombre de termes de la décomposition (optimale) ne semble pas excéder n+2 (n représentant le nombre de chiffres de l'entier à décomposer) sur l'ensemble des exemples mentionnés ici. Cet écart à n augmenterait il avec la taille de l'entier manipulé ?

[Doraki]

essaye avec 4545454545454545 ?

[anthony_unac]

essaye avec 4545454545454545 ?

Il semblerait que la décomposition optimale comporte 3*8=24 termes pour cet entier de 16 chiffres soit un écart de n+8. Donc c'est assez aléatoire cette histoire d'écart à n finalement.

PS : En multipliant par deux cet entier, on obtient quelquechose de bien plus "rentable"

[Pseuda]

Exemple avec la valeur 497 537 traitée par PSEUDA çi dessus :
497 537 : 7=ambigü (*) -> rendre le chiffre précédent pair 497 537=497 540-2-1
497 540 : 4=non ambigü -> 497 540=497 500+40
497 500 : 5=ambigü -> rendre le chiffre précédent pair 497 500=498 000-400-100
498 000 : 8=ambigü (**) -> rendre le chiffre précédent pair 498 000=500 000-2 000
500 000 : 5=ambigü -> rendre le chiffre précédent pair 500 000=0 000 000+400 000+100 000

Hum Ben314, une remarque : bolza PSEUDA

[chan79]

essaye avec 4545454545454545 ?

Il semblerait que la décomposition optimale comporte 3*8=24 termes pour cet entier de 16 chiffres soit un écart de n+8. Donc c'est assez aléatoire cette histoire d'écart à n finalement.

PS : En multipliant par deux cet entier, on obtient quelquechose de bien plus "rentable"

Ce qui serait pas mal, c'est de dénombrer les écritures de longueur minimale pour un nombre donné ...

[nodgim]

J'avais bien vu cette suite 54545454....et elle coûte 3 termes pour 2 nombres. C'est la pire situation. La moindre est évidemment 1. La moyenne doit être quelque chose qui approche n+1, avec n chiffres.