Enigme Somme de carrés consécutifs 2/2 @ Prise2Tete

Ebichu · #26

Merci et bravo aux participants. L'énigme était conçue pour être résolue par ordinateur, et pour vous donner du fil à retordre : si la première solution se laisse facilement attraper, l'autre nécessite un programme manipulant des entiers assez grands.

Comme observé par gwen27, je ne sors pas ça de nulle part : votre moteur de recherche habituel vous permettra d'accéder à un article intitulé "On Sums of Consecutive Squares" (Bremner et al), qui contient des mathématiques permettant de résoudre ce type de problèmes (enfin, je suppose, j'ai vite décroché...), et entre autres, qui montrent que 1221044 est la dernière valeur qui fonctionne (voir Table III p. 60).

enigmatus · #27

portugal #23 a écrit:
Je ne connais pas les précisions par défaut de python et à partir de quand le résultat trouvé sera faux. Un avis ?

En python, il n'y a pas de limite sur la longueur des entiers.
Voici le script python que j'ai utilisé pour mon résultat en #5 :

Code:

import sys
N=int(sys.argv[1])

def sqri(n) :
  r1,r2=0,n
  m1,m2=r1*r1,r2*r2
  if   m1==n : return r1
  elif m2==n : return r2
  while True :
    r=(r1+r2)//2
    if r==r1 : return None
    m=r*r
    if  m==n : return r
    elif m<n : r1=r
    else :     r2=r

m=20; n=0; s=0
while n<=N:
   s+=(m+n)**2
   r=sqri(s)
   if r!=None: print("%d^2+...+%d^2 = %d^2 = %d"%(m,m+n,r,s))
   n+=1

La fonction sqri retourne la racine carrée d'un entier si la racine est entière, et None sinon.

nodgim · #28

Ce que je trouve étonnant, c'est que Franky et Golgot ont trouvé la seconde valeur (308) et pas la premère (43). Peuvent ils donner une explication ?
Normalement, avec le tableur, c'est immanquable.

Deuxième remarque:
Les fabricants des logiciels de calcul (tableur, calculette..) ne se sont pas donné beaucoup de mal pour prévenir les utilisateurs des dépassements de capacité. Au lieu de renvoyer "erreur" pour des divisions, ils renvoient un résultat faux.
Si on ne connait pas bien sa machine, on se plante facilement. Pour connaitre la capacité de calcul d'une machine (nombre de chiffres exploitables), on peut se contenter de diviser par 2 un nombre impair et d'observer le résultat.

Pour ce qui de l'énigme proprement dite, je suis resté discret car sec à trouver une solution analytique. Je me suis tout de même fait plaisir à découvrir que 1²+2²+..n² est un carré pour une certaine valeur autre que 1. Sans pouvoir dire s'il y en a d'autres...

enigmatus · #29

Franky1103 #7 a écrit:
=> f(n) = (n-19).(n²/3 + 41.n/6 + 130)
Mais n²/3 + 41.n/6 + 130 n’est pas factorisable (son déterminant est négatif)
Du coup je suis un peu bloqué et ce n’est surement pas la bonne méthode.

C'est parce qu'un polynome n'a pas besoin d'être décomposable pour prendre des valeurs qui sont des carrés.
Exemple : [latex]x^2+9[/latex] pour [latex]x=0[/latex] ou [latex]x=4[/latex]

golgot59 · #30

@ nodgim : 308 est la première valeur, car 43 était déjà donné dans l'énoncé

Du coup, la deuxième était bien 1 221 044, introuvable avec les moyens dont je dispose...

nodgim · #31

Ah OK, pardon.

NickoGecko · #32

Hello

J'ai oublié de revenir avec ma macro excel ...
L'exécution est assez rapide même en VBA - pour une boucle jusque 1E7

Code:

Sub Macro1()
'
' Macro1 Macro
'
Dim i, a As Double

ligne = 1
For i = 21 To 10000000#

    a = Sqr((2 * i * i * i + 3 * i * i + i - 14820) / 6)

If a = Int(a) Then
    Cells(ligne, 1) = i
    ligne = ligne + 1
End If
Next i

End Sub

trouve aussi comme halloduda 3108049, 5988346 ...
A+

Ebichu · #33

@nodgim : le cas particulier dont tu parles (quand on commence par 1 au lieu de 20) est connu sous le nom de "cannonball problem" (désolé pour l'anglais, d'autant que le problème est dû à Édouard Lucas).

Voir par exemple : http://mathworld.wolfram.com/CannonballProblem.html

dhrm77 · #34

Je trouve:
21 29
43 158
308 3128
1221044 778998480
en 0.4 secondes.

Pour aller plus loin, faire des tonnes de racines carrées avec des nombre de plus de 64 bits peut prendre du temps... On peut utiliser les modulos pour eliminer un tas de sommes qui ne peuvent pas etre des carrés.

Modulo 10, (ou si on regarde le dernier chiffre en base 10) toutes les sommes (de carrés de 20 a n) sont potentiellement des carrés.
Modulo 3: seulement les 2/3 des sommes sont potentiellement des carrés
Modulo 4: la moitié (50%)
Modulo 12: 1/3 (33%)
Modulo 16: 25%
Modulo 44: 21.43%
Modulo 88: 16.07%
Modulo 176: 10.7%
Modulo 1056: 6.25%
Modulo 22176: 2.5%
Modulo 72864: 1.67%
Modulo 255024: 1.14%
Modulo 510048: 1.00%
Modulo 10020096: 0.857%

Comme une division est normalement plus rapide qu'une racine carrée, utiliser un modulo et un filtre permet de reduire le temps de calcul de ce qu'aurai pris une racine carrée à ce que prend une division et une lecture dans une table et donc d'aller beaucoup plus vite pour trouver les nombres suivants.
Mais je n'ai pas python installé.

shadock · #35

https://www.python.org/

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

#26 - 16-06-2016 23:17:31

Somme de carés consécutifs

#0 Pub

#27 - 17-06-2016 08:03:56

somme de carrés xonsécutifs

portugal #23 a écrit:

Code:

#28 - 17-06-2016 09:26:37

somme de carréd consécutifs

#29 - 17-06-2016 09:58:37

somme de czrrés consécutifs

Franky1103 #7 a écrit:

#30 - 17-06-2016 16:51:58

Somme de carrés consécutifss

#31 - 17-06-2016 17:01:08

Somme de carrrés consécutifs

#32 - 17-06-2016 17:44:13

somme de carréq consécutifs

Code:

#33 - 17-06-2016 18:41:37

somme de carrés cinsécutifs

#34 - 23-06-2016 22:39:18

SSomme de carrés consécutifs

#35 - 23-06-2016 22:53:30

somme de carrés consécutufs

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums