![](/img/vague-bas-gauche.png) |
#1 - 26-01-2014 10:10:11
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
PProgramme mystère
Bonjour à tous.
Programme simple à écrire (langage à adapter):
Soient N à entrer, et les variables a,b,x=1 et c,d=0
1) si x<N aller en 2); si x>N aller en 3); si x=N aller en 5).
2)a=a+1, b=b+a, aller en 4)
3)c=c+1, d=d+c, aller en 4)
4)x=b-d, aller en 1)
5) afficher a+c+1, a-c.
Que représentent les valeurs affichées ?
#2 - 26-01-2014 11:10:18
- SabanSuresh
- Elite de Prise2Tete
- Enigmes résolues : 45
- Messages : 1951
- Lieu: Paris
Programme mytsère
J'ai tapé le programme et pour chaque nombre N, le produit de a+c+1 par a-c vaut 2N. Par contre, je n'ai pas compris pourquoi ces deux nombres et non les autres.
Exemple : N=23, a+c+1 = 23 et a-c = 2 → c'est le seul cas (sans compter 1*46) Mais N=24, a+c+1 = 16 et a-c = 3 → Mais il y a aussi 2*24, 4*12 ou 6*8
#3 - 26-01-2014 11:43:22
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Programem mystère
OK Saban. La justification est à trouver. Combien de temps met ton programme pour N=49999 ?
#4 - 26-01-2014 13:11:07
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
Programmme mystère
Mon programme me permet de montrer que (a+b+1)*(a-c)=2*N
Pour N=49999, mon programme met 1 milliseconde ![smile](img/smilies/smile.png)
Démonstration de la solution: La solution est affichée si x=N or x=b-d donc N=b-d. b est la somme des a premiers entiers à partir de 1 donc b=a*(a+1)/2 d aussi est la somme des c premiers entiers à partir de 1 donc d=c*(c+1)/2 [TeX]N=b-d=\frac{a*(a+1)}{2}-\frac{c*(c+1)}{2}\Rightarrow 2*N=a^2+a-c^2-c[/TeX][TeX]\Rightarrow 2*N=(a^2-c^2)+(a-c)[/TeX][TeX]\Rightarrow 2*N=(a+c)*(a-c)+(a-c)[/TeX] [latex]\Rightarrow 2*N=(a-c)*(a+c+1)[/latex] CQFD
#5 - 26-01-2014 15:10:31
- snapy
- Habitué de Prise2Tete
- Enigmes résolues : 49
- Messages : 33
Progrmame mystère
Si on note A et B les valeurs affichées, alors : A est le plus grand entier et B le plus petit entier tels que (A*B)/2 = N.
#6 - 26-01-2014 15:14:44
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
peogramme mystère
Bonjour,
Après quelques essais, on remarque que le produit des nombres affichés est 2N.
Remarquons que avec les valeurs de départ nous avons :
a(a+1)/2 = b et c(c+1)/2 = d et x = b - d. Il est facile de vérifier que ces égalités sont des invariants de boucles, donc si le programme termine nous avons à la fin du programme :
N = x = b - d = a(a+1)/2 - c(c+1)/2, autrement écrit : 2N = a(a+1) - c(c+1) = a² - c² + a - c = (a+c)(a-c)+(a-c) = (a+c+1) (a-c). Donc le produit des deux nombres affichés est bien égal à 2N.
Terminaison du programme : Le programme termine pour N = 0. Par définition des nombres triangulaires, nous avons pour tout N > 0, N(N-1)/2 + N = N(N+1)/2.
Autrement écrit, N = N(N+1)/2 - N(N-1)/2, après un peu de réflexion, on peut facilement se convaincre que si a atteint la valeur N, alors on passera dans l'étape 3) jusqu'à ce que c atteigne la valeur (N-1) et le programme terminera. (c <= a est aussi un invariant de boucle).
Maintenant, il est curieux de constaté que : i)le programme retourne (2N,1) lorsque N est une puissance de 2. ii)le programme retourne (N,2) lorsque N est premier.
En fait le ii) peut s'expliquer par le fait que si N est premier alors 2*N est la seul décomposition de 2N en facteur premier.
Sinon, à quoi correspondent plus précisément les deux nombres retournés, je ne sais pas ![hmm](img/smilies/hmm.png)
P.S.: pour N = 49999, j'ai un dixième de seconde. (et 49999 est premier )
Il y a sûrement plus simple.
#7 - 26-01-2014 15:37:00
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Programme mysère
Kossi-tg: c'est parfait bravo ! Snapy: ton programme tourne bien, reste à comprendre le résultat. Cogito: parfait également, bravo! La singularité que tu signales sur les nombres premiers et les puissances de 2 s'explique assez facilement.
A signaler: Kossi_tg donne le résultat en 1ms pour 49999, Cogito ça semble plus lent, avec 100ms.
Kossi_tg, peux tu tenter un premier plus grand pour se rendre compte du temps ? par exemple avec 2^31 -1 ou 2^61-1 ?
#8 - 26-01-2014 16:15:50
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
Proogramme mystère
Les temps de calcul: 2^31-1 (3115 ms), 2^31 (6370 ms), 3^31 (117 ms) et autres.
Il parait évident que le temps de calcul ne dépend pas ou pas seulement de la grandeur de N mais d'autres propriétés (par exemple sa décomposition en facteur de nombres premiers). Il faut noter par ailleurs que ce temps dépend énormément des performances du pc, cela peut aller du simple au centuple voire plus d'un pc à un autre suivant leur performance ![smile](img/smilies/smile.png)
#9 - 26-01-2014 18:00:25
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
rPogramme mystère
Merci kossi. Il y a une cohérence remarquable dans les temps de calcul (2^31 deux fois plus long que 2^31-1). donc environ 3 secondes pour un binaire de 30 chiffres, la même chose pour un produit de 2 premiers de 30 chiffres. Pour un nombre premier de 100 chiffres binaires, il faudra à ton ordi quelques semaines pour obtenir le résultat...
#10 - 26-01-2014 21:18:20
- NickoGecko
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1819
Programmee mystère
Bonjour,
Voici ce que je trouve pour les première valeurs de N avec un code tout nase en VBA excel ....
![](http://www.prise2tete.fr/upload/NickoGecko-programmep2tabcdx.jpg)
(copie d'écran zoomable)
Pourrais-tu confirmer que ce sont les valeurs attendues pour que je continue à me creuser la tête sur leur signification ?
Merci, bonne soirée !
Il aurait pu pleuvoir, con comme il est ! (Coluche)
#11 - 27-01-2014 19:18:53
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Programme mysttère
C'est OK Nicko. Reste à en déduire une formule générale et ensuite à trouver l'explication.
#12 - 29-01-2014 18:39:45
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Programe mystère
Les réponses de chacun étant affichées, je laisse à ceux qui n'ont pas encore trouvé la formule générale le soin de la lire dans les bons commentaires qui ont été faits et auxquels il n'y pas grand chose à ajouter.
Merci à tous les participants pour les efforts déployés, notamment pour l'écriture en réel du programme, et les résultats affichés des performances.
Les variables b et d renvoient aux nombre triangulaires, c'est à dire les nombres de la forme n(n+1)/2. Tout le monde a vu que les 2 valeurs affichées donnent comme résultat 2 fois le nombre entré au départ, il s'agit donc ici d'un algorithme qui découvre la factorisation du nombre testé N. Il renvoie 2 facteurs pas forcément premiers.
Il a été signalé qu'un nombre de la forme 2^n renvoie 1*2^n+1 alors que pour un nombre premier P on renvoie 2*P. L'explication est la suivante: Entre 2 nombres triangulaires voisins, Tn et T(n-1), il est facile de montrer que la différence Tn-T(n-1)=n. Donc tout entier est différence au moins 1 fois de 2 nombres triangulaires. Tout nombre premier P est aussi différence de 2 nombres triangulaires, et mis à part 2, cette différence est impaire. Or tout impair est somme de 2 nombres consécutifs. Or l'algorithme tel qu'il est fait renvoie en premier l'égalité pour laquelle la valeur a (le a ième nombre triangulaire) minimale. Pour un nombre premier P: T(P+1)/2-T(P-3)/2.
Pour un nombre de la forme 2^n, il n'y a pas de valeur paire pour 2 nombres consécutifs, il faudrait prendre un nombre impair de nombres consécutifs, mais c'est impossible avec que des facteurs pairs dans le nombre. Si N=2^n, la seule valeur renvoyée sera: TN-T(N-1)=N.
Comme j'ai écrit tantôt que tout nombre entier était différence de 2 nombres triangulaires, il en est de même pour tout nombre triangulaire.
Sauriez vous trouver à la main cette fois toutes les différences possibles entre 2 nombres triangulaires de T35, par exemple ?
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |