Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 29-03-2017 19:07:23

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

Artihmétique carrée....

Bonjour à tous.

Etant donné un entier naturel impair n, existe t 'il toujours un autre entier naturel impair m > n  tel que (m-1) * ( n-1) divise m² - n² ?

Bonne réflexion



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 29-03-2017 21:09:59

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 526

Arihtmétique carrée....

Oui : [latex]m = \frac{n^2+1}{2}[/latex] convient.

 #3 - 30-03-2017 08:20:43

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

Arithméique carrée....

C'est ça Ebichu, bravo !
Comment l'as tu trouvé ? Perso, après une série d'essais....

 #4 - 30-03-2017 09:55:40

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 526

arithmétiqye carrée....

Pareil. J'ai fait un rapide programme qui me donne la plus petite valeur de m qui fonctionne pour les 50 premières valeurs de n. On remarque alors que c'est très souvent (n²+1)/2 (de rares fois, c'est moins). Il ne reste qu'à vérifier que (m-1)*( n-1) divise m²-n², et ce n'est pas compliqué.

 #5 - 30-03-2017 12:13:36

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

arithmétique czrrée....

Bien sûr, l'informatique est bien utile dans ce cas.

Justement, j'étais en train de me pencher sur le critère des autres solutions. En gros, peut-on savoir à l'avance s'il y aura plusieurs solutions possibles pour un entier donné ?

Pas si simple...

 #6 - 30-03-2017 12:58:44

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3823
Lieu: hébesphénorotonde triangulaire

Arithmétique acrrée....

Bonjour,

La réponse est OUI.

Il suffit de choisir m = (n-1)*(n+1)/2 +1

smile Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #7 - 30-03-2017 13:00:21

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

Arihtmétique carrée....

@ Klimrod : c'est bien ça, bravo !

 #8 - 30-03-2017 15:18:32

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 241

Aithmétique carrée....

Bonjour,
On peut reformuler le problème en (m'-n')(m'+n'+1) divisible par m'n', m',n' quelconques,  car les m et n initiaux sont impairs.
On conjecture assez facilement qu'en prenant m' = n' + n'^2 = n'(n'+1), le résultat est bon.
En effet, on a alors:
m'n' = n'^2 + n'^3
(m'-n')(m'+n'+1) = n'^2(n'^2+2n'+1) = [n'(n'+1)]^2
Donc pour n impair, n' = (n-1)/2,  m' = n'(n'+1) = (n-1)(n+1)/4 et enfin m = (n-1)(n+1)/2 + 1

 #9 - 30-03-2017 16:17:32

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 526

Arihtmétique carrée....

Pour les autres solutions, je viens de trouver l'explication d'une bonne partie d'entre elles.

Voici celles que j'ai trouvées inférieures à 1000 :

5,[7]*
13,[29]*
25,[79]*
31,[49]
41,[169]*
61,[311]*
71,[169]
85,[517]*
113,[799]*
145,[1169]*
181,[1639]*
209,[337]
221,[2221]*
265,[2927]*
313,[3769]*
365,[4759]*
409,[985]
421,[5909]*
461,[1519]
481,[7231]*
545,[8737]*
613,[10439]*
685,[12349]*
761,[14479]*
841,[16841]*
925,[19447]*

À gauche, la valeur de n, et à droite entre crochets, celle de m (strictement inférieure à (n²+1)/2) .

Les solutions marquées d'une étoile sont de la forme n = (k²+1)/2 et m = (k³-k²+3k+1)/4 pour k un nombre impair >=3 : j'ai trouvé cette formule en cherchant quel polynôme pouvait bien donner ces valeurs. Et après, quand on fait les calculs, on se rend compte que oui, ça marche : (m-1)(n-1)=(n-1)²(n+1)(n²+3)/8 et (m²-n²)=(n-1)³(n+1)(n²+3)/16.

Il reste encore quelques solutions pour les courageux smile

 #10 - 30-03-2017 19:42:16

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

Arithmétiique carrée....

@ Caduck : c'est bien ça, bravo !
L'expression de la formule est silmplifiable.

@ Ebichu: très bonne avancée pour les autres solutions possibles !

Je soupçonne qu'il y a une infinité de tels polynomes-solutions. Se pourrait il qu'ils obéissent eux mêmes à une régle plus générale ?

 #11 - 30-03-2017 22:03:20

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 526

Arithmétique ccarrée....

Je vais arrêter là, voilà où j'en suis. Jusqu'à 2000, j'ai trouvé les solutions sporadiques suivantes (en me restreignant à m<(n²+1)/2) :
n=31 ; m=49
n=71 ; m=169
n=209 ; m=337
n=409 ; m=985
n=461 ; m=1519
n=1429 ; m=2311
n=1871 ; m=7921

Quelques questions ouvertes :
* existe-t-il un couple solution (n;m) avec m>(n²+1)/2 ?
* une valeur n peut-elle correspondre à >=3 valeurs de m ?
* peut-on faire émerger une autre famille de solutions de ces valeurs sporadiques ?

 #12 - 30-03-2017 22:37:21

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 526

Aritmétique carrée....

Ouh là là... c'est de plus en plus effrayant. J'ai réussi à isoler deux familles infinies parmi ces solutions sporadiques.

1ere famille.

n=31 ; m=49
n=209 ; m=337
n=1429 ; m=2311
n=9791 ; m=15841
...

Pour n, on passe au terme suivant en multipliant par 7, puis en soustrayant 3+le terme précédent. Par exemple, 9791=1429*7-209-3.
Pour m, on passe au terme suivant en multipliant par 7, puis en soustrayant -1+le terme précédent. Par exemple, 15841=2311*7-337+1.
De plus, le quotient m/n converge vers le nombre d'or.

2e famille.

n=71 ; m=169
n=409 ; m=985
n=2379 ; m=5741
n=13861 ; m=33461
...

Pour n, on passe au terme suivant en multipliant par 6, puis en soustrayant 4+le terme précédent. Par exemple, 13861=2379*6-409-4.
Pour m, on passe au terme suivant en multipliant par 6, puis en soustrayant le terme précédent. Par exemple, 33461=5741*6-985.
De plus, le quotient m/n converge vers 1+racine(2).

 #13 - 31-03-2017 08:31:56

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

Arithméique carrée....

OK. J'examine une voie assez différente, je t'en parlerai quand ce sera plus mûr. En tout cas, chapeau pour ces nouveaux constats ! Je crois que toute solution particulière primitive doit pouvoir en créer une infinité d'autres.

 #14 - 31-03-2017 09:30:36

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 526

Arithméétique carrée....

Par curiosité, comment as-tu trouvé cet énoncé ?

 #15 - 31-03-2017 17:07:01

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 526

Arithmétique carrée.....

Effectivement, je suis d'accord avec ton intuition, on peut probablement trouver une infinité de familles de solutions sporadiques. La k-ième famille correspond aux solutions entière de l'équation :
(m-1)*(n-1)*k=m²-n².

Quand je lance mon programme sur une petite valeur de k, je trouve systématiquement des solutions. Par exemple, je prends k=13, et j'obtiens
n=25 ; m=313 (solution du type (n²+1)/2)
n=365 ; m=4759 (solution liée au polynôme)
n=698021 ; m=9127639 (nouvelle solution sporadique, début de la famille)

Les familles semblent devenir de plus en plus compliquées. Par exemple, le début de la 3e famille est :
n=5 ; m=13
n=25    ; m=79
n=461 ; m=1519
n=2839 ; m=9373
n=54719 ; m=180721
n=337681 ; m=1115281
n=6510965 ; m=21504253

Les valeurs de n obéissent à la relation de récurrence u(n+2)=119*u(n)-u(n-2)-135 et celles de m à la relation v(n+2)=119*v(n)-v(n-2)-27.
J'ai l'impression que le rapport m/n converge vers (3+racine(13))/2, un petit coup de Wolframalpha devrait permettre de confirmer.

Je ne sais pas si ça vaut le coup de continuer à analyser les familles individuellement plus loin. Maintenant, il faudrait chercher une théorie générale ; mais ça devient ardu. Je peux rajouter une question supplémentaire, dont on peut conjecturer que la réponse est négative :
* existe-t-il une solution qui n'appartienne pas à une certaine k-ième famille ?

 #16 - 31-03-2017 18:53:48

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,717E+3

Arrithmétique carrée....

Il me semble que ça revienne globalement à cette liste : https://oeis.org/A001844

Même si on peut rajouter quelques éléments comme 29 pour 13 .

Il n'y a que pour 1 que ce n'est pas possible.

 #17 - 31-03-2017 19:57:01

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

arithmétique cartée....

@ Ebichu : je n'ai pas pu travailler là dessus, ni hier, ni aujourd'hui, mais je ne n'abandonne pas ma propre piste, qui se résume en une seule équation relativement simple à étudier. Et qui justifie facilement la liste "deuxième niveau". 

@ Gwen: rapprochement intéressant, en effet.

 #18 - 31-03-2017 19:58:50

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

Arithétique carrée....

Vu les développements inattendus de ce sujet, j'ajoute du temps.

 #19 - 01-04-2017 13:16:18

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 526

Airthmétique carrée....

Petit progrès : je conjecture que pour la k-ième famille de solutions, le quotient m/n tend vers [latex]\frac{k+\sqrt{k^2+4}}{2}[/latex]. Je l'ai vérifié pour k de 1 jusqu'à 5.

 #20 - 01-04-2017 18:11:16

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,717E+3

Arithmétique carréée....

Oui...

et chose remarquable, une seconde série de solution plus "économique" se profile pour  :

5 13 25 41 61 qui sont justement des solution eux-même avec 7 29 79 169 ...

Puis une nouvelle solution encore plus "économique" pour  85 solution pour 13, lui-même solution pour 7 ... (29)

Il semble qu'on puisse trouver une première série , puis une amélioration pour les termes de cette série solution pris comme point de départ , et encore une pour les termes de cette série dont le cas de figure est lui-même un terme de cette série ...etc (un niveau 3 à trouver ? puis 4 ? ...)

 #21 - 01-04-2017 19:09:21

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

arithmérique carrée....

@ Ebichu :
Je dois pouvoir justifier cette relation entre k et le rapport m/n. Je vais rédiger mon idée et la transmettre, ça devrait t'éclairer.

 #22 - 01-04-2017 19:38:47

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

arithmétoque carrée....

J'ouvre le sujet, Gwen signale des choses intéressantes, déja vues je crois par Ebichu. Je ferai voir mon travail demain.

 #23 - 02-04-2017 10:25:59

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

Arithmétique carrée...

La démarche qui m'avait mené aux solutions :

On pose m² - n² = k (m-1) ( n-1)
qui est une équation du second degré dont m est l"inconnue : m² - k ( n-1) m - n² + k (n-1) = 0

Delta1 = k² (n-1)² - 4 (n-1) k + 4 n² doit être un carré parfait A², qu'on résout à son tour par un Delta (inconnue k).

Delta' 2 = (n-1)² (4 + A² - 4 n² )

k = ( 2 (n-1) + V ( D' 2 )) / (n-1)² = ( 2 + V ( A² - 4 ( n²-1 ) ) / ( n-1)   

4 ( n² - 1 )  doit être une différence entre 2 carrés pour avoir un k rationnel.

Une différence entre 2 carrés voisins est impaire. 4 ( n² - 1 )  est une somme de différences entre carrés voisins successifs.

Exemple  n = 7 et donc  4 (n²-1) = 4 * 48 
Pour 2 * 96 : la suite des différences successives  est 95 97 et les carrés encadrants sont 47² et 49²
Pour 4 * 48 : la suite des différences successives  est 45 47 49 51 et les carrés encadrants sont 22² et 26².
Pour 8 * 24 : la suite des différences successives  est 17 19 21 23 25 27 29 31 et les carrés encadrants sont 8² et 16²
etc...

Mais ce ne sont pas que des solutions puisque 2 + V ( A² - 4 ( n²-1 )  doit être aussi divisible par n-1 pour avoir un k entier.

On peut déja simplifier en posant n ' = (n-1) /2

La formule pour k devient k = ( 1 + V ( A' ² - 4 n' (n' + 1 ) ) / n' avec A' = A / 2.

On doit donc trouver a * b = n '  ( n' +1 ) tel que a < b et  b - a + 1 (le petit carré encadrant) est divisible par n'; Dans ce cas, m aura pour valeur 2 b + 1.

Exemple
n = 71
n' = 35 (7 * 5)  et n' + 1 = 36 ( 2 * 2 * 3 * 3 )
Il faut chercher a et b en échangeant les facteurs premiers tel que b = a - 1 modulo 35.
Par tâtonnement, on trouve que a = 15 et b = 84 convient. Et m = 169. 

Par cette méthode, on voit apparaitre immédiatement une solution évidente pour tout n :
a = 1 et b = n' (n' +1 ). Modulo n', ça donne bien (1,0). Dans ce cas, m = 2 n' ( n' + 1 ) + 1.

On a aussi une autre série de solutions immédiates quand n' = a' ( a' + 1).
a = a' + 1 et b = a'  * ( n' + 1) car dans ce cas on a bien b - a + 1 = 0 modulo n'.

On trouve aussi, par une série de déductions simples, les nombres n pour lesquels une seule solution est possible :
- Lorsque n' possède un seul facteur premier (élevé ou non à une puissance donnée) dans sa décomposition.
- Lorsque n' + 1 est premier dans sa décomposition et n' n'est pas de la forme a' ( a' + 1).
- Lorsque n' ne possède que 2 et un seul autre facteur premier ( élevé ou non à une puissance donnée ) sauf si n' est 6.
- Il n'y a pas de couple (a, b) tel qu'un facteur premier de n' , présent à une puissance > 1, est distribué à la fois dans a et b.

 #24 - 02-04-2017 22:16:38

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 526

Arithmétiquee carrée....

J'ai essayé de comprendre ton message. Si je ne m'abuse, il manque un 4 quelque part vers le milieu :

"La formule pour k devient k = ( 1 + V ( A' ² - 4 n' (n' + 1 ) ) / n' avec A' = A / 2. "

J'ai décroché juste après, mais ce n'est pas ta faute : l'arithmétique est mon tendon d'Achille (à moins que ce ne soit l'anatomie ?).

Je pense que la résolution de ce type d'équation diophantienne du second degré est assez connue, mais je ne maîtrise pas la théorie.

 #25 - 03-04-2017 11:27:44

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3258

Arithmétique carée....

Je crois que tu as raison, et pourtant ça marche bien ce que j'ai fait. ça doit se compenser ailleurs, mais c'est tellement embrouillé que je ne vois pas où pour l'instant. Je vais regarder tranquillement et corriger.

Sinon, l'utilisation du célèbre  " Delta " comme critère de résolution d'une équation du second degré est ici poussée au max.

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

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
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete