La (presque) question du mercredi

[Gilles59]

Je dis 'presque' parce que je n'ai moi-même pas la réponse…

Existe-il un moyen optimisé (en vitesse) applicable sur une calcultrice pour trouver la suite des nombres naturels 't' tels que le résultat suivant soit un nombre entier :



ce qui vient naturellement ) l'esprit c'est de tester les valeur de 't' avec une boucle mais ca devient vite très inefficace… Par exemple HP50

Code : Tout sélectionner

«
  -> t
  «
    DO 
     IF 'NOT(FP((1+√(2*t^2-2*t+1))/2)' THEN t 1. DISP END
     1 't' STO+ t 2. DISP
    UNTIL 0 END
  »
»

[gege]

Bonjour,
En regardant super vite, j'ai l'impression qu'il n'y a pas de solutions ???
Je vérifie.
G.E.

EDIT : pff planté

[Gilles59]

En fait l'idée est que le résultat soit un carré parfait. Les premiers 't' possibles sont :

{ 1 4 21 120 697 4060 }

[Marge]

f(4)=3 pas carré...

[zpalm]

f(4)=3 pas carré...

Oui, mais 3 est un entier, c'est ce qu'on veut.

2*t^2 -2*t+1 doit être un carré entier
donc si: 2*t^2 -2*t+1=n^2, alors: t= (1/2)*(sqrt(2*n^2-1)+1)
de plus (1+n)/2 est entier donc n est impair.

Le programme ci-dessous pour HP Prime donne les 9 premières valeurs de t:

Code : Tout sélectionner

EXPORT QDM()
BEGIN
 LOCAL n,t;
 FOR n FROM 1 TO 1000000 STEP 2 DO
  t:= (1/2)*(sqrt(2*n^2-1)+1);
  IF FP(t)==0 THEN
   PRINT("t="+t+" , f="+(1+n)/2);
  END;
 END;
 PRINT("Terminé");
END;

[bernouilli92]

Voici ma version pour hp 48 :

Code : Tout sélectionner

« { }
  1 35000 FOR N 
  N DUP 1 DISP 
  SQ 1 - 2 / √ CEIL
  IF DUP DUP 1 - * 2 * 1 + N SQ ==
  THEN
    DUP 2 DISP +
  ELSE 
    DROP
  END
  2 STEP 
»

Il faut trouver t entier tel qu'on ait : t(t-1) = (N^2-1)/2 avec N entier.
Comme N^2 doit être impair, N est aussi impair. On peut donc tester que les N impairs.

Sur émulateur, cela tourne beaucoup plus vite que sur une vraie hp48.
Avec le programme précédent, je trouve (en 5 secondes) { 0 4 21 120 697 4060 23661 }

0 est aussi un résultat possible.

[Gilles59]

En fait l'idée est que le résultat soit un entier. Les premiers 't' possibles sont :

{ 1 4 21 120 697 4060 }

Oups j’utilise mon smartphone et cafouille un peu. Je voulais éditer mon message. Et Bien ça calcule déjà deux fois plus vite. J’ai l’intuition qu’il doit y avoir un moyen plus rapide mais ne le trouve pas.

Édit : zpalm j’en n’ai pas testé ta solution mais ça m’a L’air t’es efficace en gain de temps.

[dprtl]

Vous êtes trop rapides les gars ! Je dois me dépêcher de publier ma version MPOïsée pour Casio PB-1000 qui affiche très rapidement la suite entière de Gilles59, jusqu'au maximum de chiffres significatifs pour 't' sur cette calculette, soit 5406093004 :

Code : Tout sélectionner

10 A0=1:PRINT A0:A1=4:PRINT A1
20 A2=6*A1-A0-2:A0=A1:A1=A2
30 IF A2<1E10 THEN PRINT A2:GOTO 20

[C.Ret]

Ah! Zut, je rentre du boulot et voilà j'arrive trop tard pour proposer ma solution.

Bon, c'est clair, boucler sur les carrés impairs est un progrès par rapport à la recherche séquentielle sur la variable t.

Mais c'est toujours de la force brute. Or je constate que les solutions sont de plus en plus éloignées les unes des autres, n'y aurait-il pas un moyen de ne pas 'parcourir' tous les n, mais une fraction seulement, quitte à tâtonner un peu autour des solutions possibles ??

C'est (presque) une question, je n'ai pas de solution (pour l'instant), uniquement un fin rayon jaune qui annonce l'aube d'une conjecture…


EDIT: zut je suis grillé, pas assez rapide

[Gilles59]

Vous êtes trop rapides les gars ! Je dois me dépêcher de publier ma version MPOïsée pour Casio PB-1000 qui affiche très rapidement la suite entière de Gilles59, jusqu'au maximum de chiffres significatifs pour 't' sur cette calculette, soit 5406093004 :

Code : Tout sélectionner

10 A0=1:PRINT A0:A1=4:PRINT A1
20 A2=6*A1-A0-2:A0=A1:A1=A2
30 IF A2<1E10 THEN PRINT A2:GOTO 20

je ne comprends rien à ta solution mais elle semble parfaite... Et très RPN friendly à priori !

ca marche nickel ! Mais pourquoi ?

EDIT : L'émulateur NewRPL me sort "{ 21 120 697 4060 23661 137904 803761 4684660 27304197 159140520 927538921 5406093004 31509019101
183648021600 1070379110497 6238626641380 36361380737781 211929657785304 }" instanément. L'émulateur HP50 rom HP est aussi rapide en mode exact.

Le programme n'est pas optimisé en plus :
«
{} 1 4 0 ->  A0 A1 A2
« DO 6 A1 * A0 - 2 - 'A2' STO A1 'A0' STO A2 'A1' STO A2 + UNTIL 'A2>1E15' END »
»

[C.Ret]

Pourquoi ça marche ?

Vu la forme de la solution, cela doit pouvoir se démontrer par récurrence. En partant des hypothèses que n0 et n1 sont deux impairs dont les carrés sont exacts pour t0 et t1, démontrer que n2 sera un carré exact pour t2 = 6.t1+t0+2


Sachant que l'on a:
n0 = (1+SQRT(2.t0.(t0-1)+1))/2 soit (2.n0-1)² = 2.t0.(t0-1)+1
n1 = (1+SQRT(2.t1.(t1+1)+1))/2 soit (2.n1-1)² = 2.t1.(t1-1)+1

Montrer que
(1+SQRT(2.t2.(t2+1)+1))/2 avec t2=6.t1-t0-2 est aussi une racine entière c'est-à-dire que 2.t2.(t2-1)+1 est aussi le carré d'un entier impair.

[…]

La vraie question, est comment avoir aussi vite trouvé la conjecture 6.t1-t0-2 ???
Est-ce un cas d'école des suites ?

Bon, je suis trop fatigué ce soir: j'ai juste un petit code RPN pour HP-28S qui crée la liste des solutions t :

Code : Tout sélectionner

« { 1 4 } DUP LIST→ DROP	// Initialise la suite à partir du début la liste
  DO				// Boucle principale:
    DUP 6 * ROT 2 + -		//   sauvegarde t1 et calcule t2 ← 6.t1-t0-2 en détruisant t0 
    ROT OVER + ROT ROT		//   Ajoute t2 en fin de liste
 UNTIL DUP  1E11 > END		// Boucle jusqu'à précision maximale
 DROP2 »			// Retire t1 et t0 de la pile, laisse la liste des solutions

Je trouve
{ 1 4 21 120 697 4060 23661 137904 803761 4684660 27304197 159140520 927538921 5406093004 31509019101 183648021600 }
sans pouvoir vérifier la validité des dernières solutions sans utiliser un autre calculateur.

[Gilles59]

DPRL a réussi à MPOiser ce problème… :O
Je sors ma 602P LOL

Ca donne pour les 501 à 603P (testé sur 603P). 18 pas

Code : Tout sélectionner

1 Min00 4 Min01
LBL1
 6 x MR01 - MR00 - 2 = Min02
 X<->M01 Min00 HLT
GOTO1

Pas d'astuce. L'utilisation de X<->M qui échange un registre d'affichage et une mémoire est intéressante ici

[Gilles59]

Je trouve
{ 1 4 21 120 697 4060 23661 137904 803761 4684660 27304197 159140520 927538921 5406093004 31509019101 183648021600 }
sans pouvoir vérifier la validité des dernières solutions sans utiliser un autre calculateur.

Ma 50g me confirme en mode exact que tes solutions sont valides ;D

[Gilles59]

Allez c'est l'occasion de sortir la TI57 ;D

La programmation est ici absolument identique à la Casio 602P, pas par pas.
Et bien je dois dire que l'affichage en diodes rouges à son charme ;D
Ce qui est amusant, c'est que même sur un programme aussi simple, on la voit calculer ...

Code : Tout sélectionner

1
STO0
4
STO1
Lbl1
6
x
RCL1
-
RCL0
-
2
=
STO2
Exc1
STO0
RS
GTO1

[zpalm]

La vraie question, est comment avoir aussi vite trouvé la conjecture 6.t1-t0-2 ???
Est-ce un cas d'école des suites ?

Je suis aussi curieux de savoir comment dprtl a trouvé cette superbe formule.

Sinon pour toutes les suites la solution de facilité pour trouver les formules est de mettre les premiers termes dans le moteur de recherche de l'OEIS (On-Line Encyclopedia of Integer Sequences), mais pour les challenges sur le forum c'est un peu de la gruge.