Inscription / Connexion Nouveau Sujet
Cubes et algorithme
Bonsoir , je vous propose l'exercice suivant :
on dispose de n = 157889 cubes unités , on désire à partir de ces petits cubes réaliser le plus petit nombre possible de grands cubes
par exemple avec n = 123 , je pourrais former
un cube de dimensions : 4*4*4 .
2 cubes de dimensions : 3*3*3 .
et 5 petits cubes .
soit en tout 7 cubes .
Le but et d'écrire un algorithme permettant de dénombrer le plus petit nombre possible de " grands " cubes à partir de n =157889 petits cubes unités
Bonsoir flight, il faudrait se renseigner un peu mieux sur le problème de Waring pour pouvoir faire un algorithme efficace.
J'avoue ne pas en connaître assez à ce sujet donc je te proposerai au mieux de la force brute sans intérêt.
Par exemple, on connait il me semble le nombre max qui est de 9 grands cubes dans le cas général et 7 grands cubes si ton entier à décomposer est suffisamment grand (avec une conjecture probable à 4 grands cubes).
Il existe sûrement dans la littérature de tels algorithmes qui tiennent compte des propriétés du nombre à décomposer mais je ne les connais pas.
perso,
je propose :
on prend la racine cubique entiere du nombre de cubes dispo
ici 54 :
54 ^3 = 157464, ==> on fait un seul cube de 54*54 *54
reste 425
racine cubique = 7
7^3 = 343 ==> on fait un cube de 7*7*7
reste 82
racine cubique = 4 ==> 1 cube de 4*4*4
reste 18
2^3=8 on peut faire 2 cubes de 2*2*2
reste 2 ==> 2 cubes elementaires.
soit 7 cubes.
pas le temps d'écrire l'algorithme...
Euh pas tout à fait, tu ne peux pas assurer que la meilleure stratégie sera de prendre le plus grand cube possible à chaque fois.
Exemple simple
Et ton algorithme va donner donc tu vas renvoyer 4 alors que la bonne réponse est 3.
Même en force brute, il faut faire un algo où tu choisis un premier nombre au cube inférieur à ton objectif et tu optimises le reste, puis tu essayes avec un autre nombre au cube et tu optimises le reste... Toute la question étant qu'est-ce qui vaut la peine d'être testé ? D'où le fait de s'informer sur le sujet.
Vassillia, tu as raison.
Ma proposition ne peut etre qu'une première étape.
Il faudra aussi regarder si le nombre disponible de mini-cubes est un multiple d'un cube.
Bonne soirée.
Oui enfin même si ce n'est pas un multiple, il va y avoir des problèmes
Et ton algo vas trouver
On est quand même loin du compte.
Bonne soirée à toi aussi.
Bonsoir
Au contraire de l'algo proposé par Leile il faut que les cubes soient autant que faire se peut de même valeur ou de valeurs proches donc surtout pas le plus grand cube possible pour commencer.
Pour rigoler
un cube de 1 est petit donc un cube de 9 est "grand"
On peut donc obtenir 17545 cubes de 9 (avec 2 de 1 )
Mais je vais chercher....
Vassillia
C'était ridicule.......
je vais répondre: 8 cubes de 27 (de coté)
1 cube de 7
3 cubes de 3
1 cube de 1
Soit 13 cubes
Si je comprends bien il faut décomposer N avec le maximum de gros cubes en évitant le plus gros c'est à dire
Je propose donc de décomposer en débutant par ( )/2
On en aura donc 8 puis prendre le reste avec les plus grosses racines cubique.
Je donne un exemple soit N=456 728 286
on obtient 8 cubes de coté 385
A noter que 6 niveaux suffisent....
1 cube de coté 58
1 cube de coté 5
1 cube de coté 3
2 cubes de coté 2
6 cubes de 1
soit un total de 19 cubes les plus grands possibles.
6 cubes de 1
>flight
Comme c'est toi qui a posté je garde ton début ,mais le mien
fonctionne aussi ...
J'ai testé mon bidule au maxi....
Soit N= 281 474 876 710 656
1 de 65535 (what else !)
1 de2344
1 de 181
1 de 37
1 de10
1de 6
1 de 4
2 de 2
1 de 1
Je n'ai pas compris ce que tu trouves ridicule dpi ?
Si j'ai bien lu le problème, le but est d'ecrire un entier comme somme de cubes positifs en minimisant le nombre de terme de la somme. Je ne sais pas où tu as lu qu'il fallait maximiser.
Donc c'est bien le problème de Waring et ta réponse 13 est forcément fausse comme ta réponse 10 d'ailleurs. Il est démontré que n'importe quel entier peut se décomposer en au plus 9 cubes et même 7 cubes si l'entier est suffisamment grand. Je ne dis pas qu'on ne peut pas faire un algo sans mais il me paraît quand même logique d'utiliser de genre d'info et les bornes qui vont avec pour faire un algo optimisé. C'est tout ce que j'ai dit.
En utilisant l'algorithme suivant :
Cliquez pour afficherJ'obtiens une solution en 5 termes:
Cliquez pour afficher>Vassillia
Ridicule s'appliquait à mon message de 8h32.
Je pense que le problème est soit de faire la liste la plus courte des
plus gros cubes inclus soit de faire la liste avec les plus gros exceptés le plus gros...ou autre....
J'attends donc des précisions de flight
>Littlefox
J'observe que tu as pris le minimum de termes avec les plus gros cubes possibles.
Ainsi si on avait a réduire 157 165 par exemple on obtiendrait
54³+1³ soit 2 termes...
Oui, la somme (ordonnée) avec le minimum de termes.
Je n'arrive pas à être sûr du sens de tes autres interprétations.
J'ai corrigé mon algorithme (il y avait des erreurs d'arrondi dans le calcul des racines cubiques) et j'ai maintenant une solution en 4 termes
Le code:
Cliquez pour afficherLes solutions :
Cliquez pour afficher
Un autre solution à la "solution" de dpi (On cherchait 157889 et pas 157859 
)
47³+37³+15³+2³ = 157859
Je ne maitrise pas assez python pour apprécier mais j'ai l'impression que c'est hyper bien écrit Littlefox. Je serai bien incapable de faire aussi bien même dans d'autres langages.
Sinon moi non plus, je n'arrive pas à interpréter la question autrement avec : le plus petit nombre possible de " grands " cubes mais je ne veux pas parler au nom de flight.
sans contraintes on peut donner plusieurs réponses possible au probleme posé , mais la contrainte tait d'obtenir un nombre de "cubes" le plus petit possible l'optimisation obtenue par Littlefox est pas mal
Je suis assez distrait... (c'est l'âge) mais je garde mon bidule mon
erreur de 157859 le confirme .Prochainement je tenterai mon
maximum pour un nombre de 15 chiffres.
@Vassillia
Merci
solve(n, k) retourne la liste de termes telle que cette liste soit la plus courte, la somme des puissances k ème des termes soit égale à n, les termes soient les plus petit possibles et les termes soient en ordre décroissant.
Je construit les solutions de cette façon:
Les solutions pour n sont i³ + les solutions pour (n-i³) avec des termes inférieurs ou égaux à i.
Je génère toutes les solutions avec 1 terme puis 2, puis 3, ...
Avec l'observation que le nombre de termes dans la solution est faible, l'algorithme reste relativement efficace même si on est pas loin de la force brute.
J'ai essayé de rester générique en utilisant les puissances k ème plutôt que le cube.
Pour mémoire:
J'ai testé mon bidule sur N=275 125 865 123 400
J'obtiens 65069³+1841³+156³+18³+8³
Ce qui est remarquable c'est le peu de termes pour les grands chiffres...vous me direz que par chance on peut tomber sur un cube parfait .
Il me faut 1 minute pour dérouler .
Bonjour dpi,
A mon avis, tu t'es trompé ou tu viens de faire une découverte importante mais l'erreur est plus vraisemblable.
En 2000, la conjecture est que le plus grand nombre qui n'est pas somme de 4 cubes positifs vaut
7 373 170 279 850
L'article à ce sujet 
Ton nombre étant plus grand, il devrait pouvoir s'exprimer comme somme de 4 cubes positifs si la conjecture est vraie, 5 cubes positifs n'est pas la meilleure possibilité.
Vous comprenez peut-être pourquoi je disais de s'informer un peu sur le sujet avant 
Edit : enfin il devrait pouvoir s'exprimer comme somme de 4 cubes positifs ou moins, je n'en sais rien, je n'ai pas testé
@dpi
Vérifie un peu tes réponses avant de les poster 
65069³+1841³+156³+18³+8³ = 275506747192590 et non 275125865123400
Avant de chercher à calculer des nombres pareils, pourquoi ne pas essayer de trouver une autre solution en 4 termes au nombre initial: 157889?
Tout à fait d'accord avec LittleFox, il faut savoir être raisonnable. De toute façon, il y a un problème dans ton algo, même pour 275 506 747 192 590 c'est pas normal d'avoir une décomposition en 5 cubes donc ce n'est pas juste une erreur de copier-coller.
L'article que j'ai mis en lien le conjecture et c'est un article sérieux d'un journal sérieux avec peer review. Qu'est-ce que tu lui reproches ?
L'impact factor est honorable pour des maths. Si c'est la langue qui te pose problème, dis moi si tu veux que je te traduise quelque chose car tous les articles de recherche sont publiées en anglais, il faut s'y faire.
Mon algorithme n'est pas assez efficace pour les nombres à 15 chiffres.
En lisant l'article de Vassillia on découvre qu'on peut découper la recherche en utilisant les modulo:
En effet les cubes sont congrus à -1, 0 ou 1 modulo 9 ou 7 or 275125865123400 est congru à -3 modulo 9 et -3 modulo 7.
Il y a donc 3 cas possibles pour la somme de cubes:
(mod 9) 0 + -1 + -1 + -1 = -3
(mod 7) 1 + 1 + 1 + 1 = -3
(mod 63) 36 + 8 + 8 + 8 = 60
(mod 9) 0 + -1 + -1 + -1 = -3
(mod 7) 0 + -1 + -1 + -1 = -3
(mod 63) 0 + 62 + 62 + 62 = 60
(mod 9) 0 + -1 + -1 + -1 = -3
(mod 7) -1 + 0 + -1 + -1 = -3
(mod 63) 27 + 35 + 62 + 62 = 60
Même avec la base 63 j'ai besoin d'environ 10Go de mémoire pour effectuer les calculs. L'article a utilisé un super ordinateur
J'obtiens:
198 solutions pour 36 + 8 + 8 + 8:
Cliquez pour afficher57 solutions pour 0 + 62 + 62 + 62:
Cliquez pour afficheret 232 solutions pour 27 + 35 + 62 + 62:
Cliquez pour afficherVoici le code pour information car spécifique aux cas n = 60 (modulo 63):
Cliquez pour afficher>Littlefox
Bravo pour tes travaux.
Je voulais tester mon travail sur Excel avec 15 chiffres.
je vais améliorer pour trouver en 4 termes.
>Vassillia
Tu sais que j'ai 40 ans de plus que toi et ça pèse....
On peut observer que mon premier terme mal recopié est
65039³ au lieu de 65069³ et donne bien le résultat cherché.
Depuis je sais que l'on peut trouver 4 termes ,mon bidule ne va pas
assez loin.
Quant à ton article ,je manifestais mon incapacité à tout saisir....
Désolé dpi, je ne voulais pas te vexer, je pensais juste que l'article pouvait être utile à toi ou d'autres. Par rapport à ton age, je serai surement bien contente si j'arrive à faire aussi bien que toi à cet age là donc tu as tout mon respect à ce sujet.
Très joli LittleFox, voilà un algo optimisé comme j'aime ! La force brute a malheureusement ses limites. Nous voilà rassuré, la conjecture reste valable pour le moment. Ça aurait été malheureux qu'elle tombe au premier coup quand même.
Les auteurs n'ont pas testé aussi loin, "seulement tous les entiers" entre 7 373 170 279 851 et 74 000 000 000 000. Ils ont toutefois des arguments probabilistes qui se défendent pour la suite.
Leurs tests ont utilisé environ 10 000 heures de CPU, c'était il y a 20 ans, on irait sans doute plus vite aujourd'hui mais ils étaient motivés visiblement.
Annuler
connectez vous