Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#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...
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:
# -*- 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 :
ou encore directement :
# -*- 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 !
# -*- 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 :
# -*- 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 :
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 :
# -*- 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 :
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)
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
# -*- 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 :
25502500 - 338350 = 25164150
Temps de travail : 0.0 s
-----------------------------------------------------------------------------------------------------------------------
Défi n° 7
Le 10001e nombre premier.
# -*- 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 :
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
# -*- 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 :
S = 4613732
Temps de travail : 0.0 s
* Avec 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.0149998664856 s
----------------------------------------------------------------------------------------------------------
Défi n° 5
Le plus petit multiple de chacun des nombres de 1 à 20...
C'est évidemment leur PPCM !!!
Donc :
# -*- 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 :
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.
# -*- 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 :
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².
# -*- 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 :
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
Pages : 1