Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 03-11-2009 10:34:34

ju_bicycle
Membre
Inscription : 31-08-2009
Messages : 79

Le défi d'Euler

Salut a tous,
Il y a déja peut etre eu une petite note au sujet de ce site...

http://projecteuler.net/

Une suite de question mathématique (il y en a plus de 250), a résoudre a l'aide de programme a écrire soi-même
(ex: Somme des nombre premiers inferieur a 2 000 000).

Super instructif d'un point de vue Math/Optimisation de code (le but étant d'avoir des codes qui tournent en moins d'une minute), et totalement addictif

Qui se lance?
(j'ai découvert ca hier aprem, et j'ai perdu une demi journée dessus)

Hors ligne

#2 03-11-2009 13:00:17

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Le défi d'Euler

RE,


Défi n°1
Somme des nombres divisibles par a et inférieurs b:

# usr/bin/env python
# -*- coding: utf-8 -*-

a,b,total = 7,1000000,0
total=sum([x for x in range(1,b,a)]
# Variante : total=sum([x for x in xrange(b) if not x%a])
# Enlever le not conduit à sommer tous les non-multiples de a

print u'Somme des nombres divisibles par',a,'et inférieurs à',b,':',total

Résultat :

Somme des nombres divisibles par 7 et inférieurs à 1000000 : 71428928571

ou encore directement :

# usr/bin/env python
# -*- coding: utf-8 -*-

a,b = 7,1000000
print u'Somme des nombres divisibles par',a,'et inférieurs à',b,':',sum([x for x in range(a,b,a)]

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 03-11-2009 13:58:54

ju_bicycle
Membre
Inscription : 31-08-2009
Messages : 79

Re : Le défi d'Euler

Bah oui, je me suis peut etre mal exprimé:
Quand je dit que j'ai passé une demi journée dessus: C'est pas sur la question 1. Il y en a 250 alors j'ai le temps d'en perdre...J'ai fais les 11 premiere hier. Ce devient plus dur mais ca reste tout a fais faisable...C'est juste pour info pour ceux que ca interesserai

Hors ligne

#4 03-11-2009 14:09:42

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Le défi d'Euler

Re,

J'avais compris, merci !
Ce n'était qu'un un début... (...continuons le combat !)

Mais, comme c'est de l'anglais (non pas que je bute sur chaque terme), ça me donne des boutons !

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 03-11-2009 14:28:31

ju_bicycle
Membre
Inscription : 31-08-2009
Messages : 79

Re : Le défi d'Euler

Si t'as besoins de traduction hésite pas...
Par contre quand tu finis les questions donne surtout les temps de compile. C'est le plus interessant.
Tu pourra réutiliser ton algo pour les nombres premiers...J'ai fais ça a l'arrache (force brut) Du coup j'ai besoins de presqu'une minute pour la somme des nombres premiers inférieur a 2 millions...

Hors ligne

#6 03-11-2009 17:49:07

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Le défi d'Euler

Re,


Défi n° 10
Somme des nombres premiers  inférieurs à 2000000 :

Avec psyco :
* Somme : 142913828922
* Temps de travail : 0.359000205994 s

Ca me paraît louche !

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
import psyco
psyco.full()

def eratosthene(n,premiers):
    nombres = []
    for i in xrange(2,n+1):
        nombres.append(True)
    for i in xrange(2,n+1):
        if nombres[i-2]:
            premiers.append(i)
            for j in xrange(2*i,n+1,i):
                nombres[j-2] = False
    return premiers

tp_d=time()
premiers,s=[],0
premiers=eratosthene(2000000,[])
for n in premiers:
    s+=n
   
print "Somme :",s    
temps = time()-tp_d
print
print "Temps de travail :", temps,"s"

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#7 03-11-2009 19:51:14

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Le défi d'Euler

RE,

Défi n°3
Plus grand facteur premier :

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
from fractions import gcd

tp_d=time()
n=600851475143
n1=n
a=1

# Si la factorisation me marche pas
# Et si vous avez la certitude que votre nombre n'est pas premier
# Changez la valeur de c : essayez avec 3,5,7...

liste_prem=[]
while a!=n:
    x,y,a,c=1,1,1,1
    while a==1:
        x=(x*x+c)%n           # x = f(x)
        y=(y*y+c)%n
        y=(y*y+c)%n           # y = (f o f)(y)
        a=gcd(n,abs(x-y))
    liste_prem.append(a)
    if n==a:
        break
    n=n/a

temps = time()-tp_d
print "Le plus grand facteur premier de",n1,"est :", max(liste_prem)
print
print "Temps de travail :", temps,"s"

Résultat :

Le plus grand facteur premier de 600851475143 est : 6857

Temps de travail : 0.0 s

@+

[EDIT]

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Là, je ne vois pas ce qu'il faut faire
* even-valued = même valeur ?
* even valued terms : termes de même valeur ??? là, je ne pige plus...
* which do not exceed four million  : qui ne doit dépasser 4000000 ? les sommes de termes ? le plus grand nombre de la suite ?

Ah ! L'impérialisme arrogant de la langue anglaise !!!


Arx Tarpeia Capitoli proxima...

Hors ligne

#8 04-11-2009 11:27:32

ju_bicycle
Membre
Inscription : 31-08-2009
Messages : 79

Re : Le défi d'Euler

even= paire
Donc la somme de tous les termes paire de la suite de fibonnaccci inferieur a 4 millions

Hors ligne

#9 04-11-2009 11:36:44

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Le défi d'Euler

Salut,


Défi n°4
Ok, merci !
Plus grand palindrome composé du produit de 2 nombres à 3 chifres :

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
import psyco
psyco.full()

tp_d=time()
pal,fac1,fac2='1',100,100
for i in xrange(100,1000):
    for j in xrange(100,1000):
        mot=str(i*j)
        tom=''
        for lettre in mot:
            tom=lettre+tom
        if mot==tom:
            if i*j>int(pal):
                pal,fac1,fac2=mot,i,j

temps = time()-tp_d          
print u"Palindrome cherché :", pal,"=",fac1,"*",fac2
print
print "Temps de travail :", temps,"s"

Résultat :

Palindrome cherché : 906609 = 913 * 993

Temps de travail : 2.45300006866 s

Que t'inspirent ces temps ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#10 04-11-2009 11:44:56

ju_bicycle
Membre
Inscription : 31-08-2009
Messages : 79

Re : Le défi d'Euler

Que t'inspire ces temps

meilleur que les miens ^^
Faut dire que j'ai pas cherché a optimiser. Ma fonction isprime(n) est trés moche. Un truc du genre (je te la balance de tete, donc c'est a prendre comme du pseudo code)


i=3
while i<sqrt(n):
    if i%n==0:
        return False
   i=i+2
return True

J'ai pas eu le temps de m'y remettre depuis avant hier, mais j'pense que je passerai un peu de temps a étudier tes algos avant de continuer : Le but étant aussi d'améliorer ses trucs

De mémoire le temps d'execution pour la somme des entier inferieur a 2 000 000 était de l'ordre de 45 secondes chez moi. Soit  45/0.36=125 fois plus lent que toi!!! Pas top top!

Par contre met bien le numéro de la question en en-tete, afin d"éviter de ne pas lire une soluce non traité par erreur

Dernière modification par ju_bicycle (04-11-2009 11:49:05)

Hors ligne

#11 04-11-2009 12:33:44

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Le défi d'Euler

RE,

Défi n°6
Différence entre le carré de la somme des 100 premiers entiers et le somme de leurs carrés

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
import psyco
psyco.full()

tp_d=time()
n=100
somme_carres= n*(2*n*n+3*n+1)/6
carre_somme =n*n*(n+1)*(n+1)/4
diff=carre_somme-somme_carres

temps = time()-tp_d
print u"Différence entre la somme des carrés des 100 premiers nombres entiers et le carré de leur somme :"
print "        ",carre_somme,'-',somme_carres,'=',diff
print
print "Temps de travail :", temps,"s"

Résultat :

Différence entre la somme des carrés des 100 premiers nombres entiers et le carré de leur somme :
         25502500 - 338350 = 25164150

Temps de travail : 0.0 s

-----------------------------------------------------------------------------------------------------------------------
Défi n° 7
Le 10001e nombre premier.

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
import psyco
psyco.full()

def eratosthene(n,premiers):
    nombres,cpt = [],0
    for i in xrange(2,n+1):
        nombres.append(True)
    for i in xrange(2,n+1):
        if nombres[i-2]:
            premiers.append(i)
            cpt+=1
            for j in xrange(2*i,n+1,i):
                nombres[j-2] = False
            if cpt==10001:
                break
    return premiers

tp_d=time()
premiers,n=[],120000
premiers=eratosthene(120000,[])

temps = time()-tp_d
print "Le 10001e nombre premier est :",premiers[10000]    

print
print "Temps de travail :", temps,"s"

Résultat :

Le 10001e nombre premier est : 104743

Temps de travail : 0.0159997940063 s

Cela dit, il faut relativiser les écarts de temps :
1. J'ai mis en place l'accélérateur psyco : gain 5 à 20% selon les scripts
2. J'ai 2 Go RAM
3. J'ai un AMD Phenom X3 2,66 Ghz

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#12 04-11-2009 15:03:03

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Le défi d'Euler

Salut,

Encore deux !
Défi n° 2
Somme de tous les nombres pairs de la suite de Fibonacci inférieurs à 4000000

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
import psyco
psyco.full()

tp_d=time()
Fibo1,Fibo2,Fibo,Somme=1,2,2,2
i=1

# Variante avec affichage des nombres pairs : print '2',
while Fibo<4000000:
    i+=1
    Fibo=Fibo1+Fibo2
    if Fibo %2==0:
        Somme+=Fibo
        # print Fibo,          Variante avec affichage des nombres pairs
    Fibo2,Fibo1=Fibo,Fibo2
   
temps=time()-tp_d  
print u"La somme de tous les nombres pairs de la suite de Fibonacci inférieurs à 4000000 est :"
print "        S =",Somme
print
print "Temps de travail :", temps,"s"

Résultats
* Sans affichage intermédiaire :

La somme de tous les nombres pairs de la suite de Fibonacci inférieurs à 4000000 est :
        S = 4613732

Temps de travail : 0.0 s

* Avec affichage intermédiaire :

2 8 34 144 610 2584 10946 46368 196418 832040 3524578
La somme de tous les nombres pairs de la suite de Fibonacci inférieurs à 4000000 est :
        S = 4613732

Temps de travail : 0.0149998664856 s

----------------------------------------------------------------------------------------------------------

Défi n° 5
Le plus petit multiple de chacun des nombres de 1 à 20...
C'est évidemment leur PPCM !!!
Donc :

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
import psyco
psyco.full()

tp_d=time()

premiers,expos=[2,3,5,7,11,13,17,19],[]
prod=1
for i in premiers:
    j=1
    while i**j<21:
        j+=1
    prod*=i**j
    expos.append(j-1)

temps=time()-tp_d
reponse=''
print u"Le plus petit nombre multiple de tous les nombres de 1 à 20 est :"
for i in xrange(8):
    reponse+=str(premiers[i])+'^'+str(expos[i])+" * "*(i<7)
print "     ",prod,'=',reponse
print
print "Temps de travail :", temps,"s"

Résultat :

Le plus petit nombre multiple de tous les nombres de 1 à 20 est :
      2258015666306400 = 2^4 * 3^2 * 5^1 * 7^1 * 11^1 * 13^1 * 17^1 * 19^1

Temps de travail : 0.0 s

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#13 05-11-2009 10:38:06

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Le défi d'Euler

Bonjour, Bonjour,

Deux de plus.
Défi n°8
Trouver le plus grand produit de 5 nombres à 1 chiffre consécutifs dans le nombre de 1000 chiffres donnéd.

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
import psyco
psyco.full()

tp_d=time()
nombre='73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450'

prod1,prod = 1,1
for i in xrange(995):
    prod = eval('*'.join(nombre[i:i+5]))
    prod = max(prod,prod1)
    prod1 = prod
   
temps=time()-tp_d
print
print u'Le plus grand produit de 5 "chiffres" consécutifs du nommbre de 1000 chiffres donné est:'
print "        Produit =",prod
print
print "Temps de travail :", temps,"s"

Résultat :

Le plus grand produit de 5 "chiffres" consécutifs du nombre de 1000 chiffres donné est:
        Produit = 40824

Temps de travail : 0.0309998989105 s

----------------------------------------------------------------------------------------------------

Défi n°9
Trouver le seul triplet pythagoricien de somme 1000, donc tel que a + b + c = 1000 et a² + b² = c².

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
import psyco
psyco.full()

tp_d=time()
x,y,z,fin=3,4,5,0
for x in xrange(3,500):
    if fin:
        break
    for y in xrange(x+1,500):
        z = 1000-x-y
        if x*x+y*y==z*z:
            fin,a,b,c=1,x,y,z
            break

temps=time()-tp_d
print
print u'Le triplet pythagoricien de somme 1000 est:'
print '   ',a,b,c,':',str(a)+'**2'+' + '+str(b)+'**2'+' =',a**2,'+',b**2,'=',a**2+b**2,'= '+str(c)+'**2'
print
print "Temps de travail :", temps,"s"

Résultat :

Le triplet pythagoricien de somme 1000 est:
    200 375 425 : 200**2 + 375**2 = 40000 + 140625 = 180625 = 425**2

Temps de travail : 0.0469999313354 s

Rappel : la seule exigence de ce défi est que les résultats doivent être trouvés en moins d'une minute...

Pas d'autres amateurs ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#14 05-11-2009 11:30:58

ju_bicycle
Membre
Inscription : 31-08-2009
Messages : 79

Re : Le défi d'Euler

oui et encore la regle de la minute est plutot un objectif personnel. La seule exigence est de donner la bonne réponse. Aprés il est précisé qu'il est faisable de pondre un algo qui permet de trouver les résultats en moins d'une minute...
J'ai pas eu le temps de m'y repencher depuis lundi. J'vais surement m'y consacrer une petite demi heure cette aprem pour finir la 11. Ensuite je regarderai tes algos (y'a des trucs qui m'interessent). Puis je passerai a la 12 plus tard
Voilou!
PS tu répond pas a tes mails :D?

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
quatre-vingt quatorze moins
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums