Calcul de pgcd
dans Arithmétique
Bonjour,
Je cherche à calculer la quantité suivante :
pgcd( (2n+13) * 3n-2 + (3n-23) * 4n-2 , 2*4n-2 - 3n-2 )
Il me faut une formule en n ou un algorithme rapide. (En fait, j'ai besoin de la somme de ces valeurs pour n allant de 2 à 107)
C'est pour résoudre le problème 570 de projet Euler.
Merci !
Je cherche à calculer la quantité suivante :
pgcd( (2n+13) * 3n-2 + (3n-23) * 4n-2 , 2*4n-2 - 3n-2 )
Il me faut une formule en n ou un algorithme rapide. (En fait, j'ai besoin de la somme de ces valeurs pour n allant de 2 à 107)
C'est pour résoudre le problème 570 de projet Euler.
Merci !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si on te résout le problème, ce n'est plus toi qui résous le problème !! :-X
Cordialement,
Rescassol
Rescassol oui j'ai un peu honte ...
mais mes connaissances en arithmétique s'arrêtent à Bézout, c'est faisable quand même ?
Quand on voit apparaître cette forme générale, on est déjà un peu plus armé pour chercher.
Une formule certainement utile à connaître , c'est que PGCD(a,b) = PGCD(a-b,b) et plus généralement, PGCD(a,b)=PGCD(a-kb,b).
Et cette formule, c'est M. EUCLIDE qui l'a rendue célèbre. Ca aussi, ça peut être un nom utile à connaître quand on parle de PGCD.
C’est un problème mathématique par semaine donné le week-end (sauf l’été), de difficulté variable (de simple à très difficile), résoluble la plupart du temps à l’aide d’un esclave numérique.
-- Schnoebelen, Philippe
En regardant les valeurs pour n allant de 1 à 1000, ont voit que le pgcd vaut 1 sauf en 11 + 20k, 104 + 272k, 43 + 342k, 246 + 253k, ... je ne sais pas quoi en déduire
Je peux avoir un indice ?
Certains problèmes me semblent difficiles à résoudre avec une seule feuille et un crayon.
J'ai calé sur un problème il y a quelques années (problème que je doute qu'on puisse résoudre seulement par papier et un crayon) et je me suis éloigné de ce site (dont j'ai perdu mes identifiants).
.
Une bonne partie, oui. D’autres, bon courage.
J’en ai résolu 243 mais je commence à caler et je n’ai pas un temps infini non plus.
-- Schnoebelen, Philippe