Écrire une réponse @ Prise2Tete

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	[+]

	Forum » Enigmes Mathématiques » Décomposition en somme d'entiers Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=scarta]C'est assez facile avec le théorème du nombre pentagonal d'Euler, il me semble... Ce dernier donne une récurrence pour trouver P(n), le nombre de [b]partitions[/b] (ça s'appelle comme ça) de n. [latex]P(n) = \sum_{k \in \mathbb{N}^}{(-1)^{(k+1)} P(n - \frac{k(3k-1)}{2})}[/latex] P(N) = 0 pour N < 0, P(0) = 1 et c'est parti ! P(1) = P(0) + P(-1) + ... (termes nuls) P(1) = 1 P(2) = P(1)+P(0)+P(-3) + ... (termes nuls) P(2) = 2 P(3) = P(2)+P(1)+P(-2) + ... (termes nuls) P(3) = 3 P(4) = P(3)+P(2)+P(-1) + ... (termes nuls) P(4) = 5 P(5) = P(4)+P(3)-P(0)-P(-2) + ... (termes nuls) P(5) = 7 P(6) = P(5)+P(4)-P(1)-P(-1)+P(-6) + ... (termes nuls) P(6) = 11 P(7) = P(6)+P(5)-P(2)-P(0)+P(-5) + ... (termes nuls) P(7) = 15 P(8) = P(7)+P(6)-P(3)-P(1)+P(-4) + ... (termes nuls) P(8) = 22 P(9) = P(8)+P(7)-P(4)-P(2)+P(-3) + ... (termes nuls) P(9) = 30 P(10) = P(9)+P(8)-P(5)-P(3)+P(-2) + ... (termes nuls) P(10) = 42 La réponse est 42 (en même temps c'était prévisible, d'après le théorème d'Adams :lol:) Pour 1000, un petit programme de 10 lignes (avec une librairie pour gérer les gros entiers) nous donne en une fraction de seconde le résultat exact suivant: 24061467864032622473692149727991 En pseudo-code, ça donne: Initialiser un tableau d'entiers "très longs" indicé de 0 à 1000, initialiser le 1er à 0 Pour I allant de 1 à 1000 avec un incrément de 1 Initialiser le i-ème résultat à 0 Pour j allant de 1, sans limite avec un incrément de 1 Si K = i - j (3 * j - 1) / 2 est négatif, fin de la boucle sur j Ajouter au i-ème résultat le K-ème résultat si j est impair ou son opposé si j est pair Si K = i - j * (3 * j + 1) / 2 est négatif, fin de la boucle sur j Ajouter au i-ème résultat le K-ème résultat si j est impair ou son opposé si j est pair Fin de boucle sur j Fin de boucle sur i[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez à la devinette suivante : Le père de toto a trois fils : Pif, Paf et ? Retour Résumé de la discussion Nicouj 25-10-2010 14:26:19 Le problème est de compter le nombre de décompositions d'un entier en somme d'entiers strictement positifs modulo associativité/commutativité. Par exemple pour le nombre 5 il existe 7 décompositions : 5 4+1 3+2 3+1+1 2+2+1 2+1+1+1 1+1+1+1+1 Combien en existe t-il de décompositions pour les nombres suivants : - 10 (à la main) - 100 (à la machine) - 1000 (à la machine mais en faisant gaffe) ~~Réponse pour 1000~~ : (je viens de m'apercevoir que la boite de réponse tronque la solution car il y a trop de chiffres >< Du coup je laisse la case réponse pour 10 : Pied de page des forums P2T basé sur PunBB Screenshots par Robothumb © Copyright 2002–2005 Rickard Andersson
Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact