1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #vérification de la conjecture de Sierpinski jusqu'à n=10000
import math
import time
import sys
import types
import psyco
#variables globales utilisées par la méthode du crible d'Atkin
limite=10000
crible=[0]*limite
racine= int(math.sqrt(limite))+1
premiers=[2,3]
# fin des v.g.
# la méthode du crible d'Atkin
def cond1 (n):
return n<limite and ((n%12==1)or(n%12==5))
def cond2(n):
return n<limite and (n%12==7)
def cond3(x,y,n):
x>y and (n<limite)and (n%12==11)
def debut():
for x in range(1,racine):
for y in range (1,racine):
n=4*x*x+y*y
if cond1(n):
crible[n]=not crible[n]
n=3*x*x+y*y
if cond2(n):
crible[n]=not crible[n]
n=3*x*x-y*y
if cond3(x,y,n):
crible[n]= not crible[n]
def fin():
for n in range(5,limite):
L=[k*n*n for k in range(1,limite/(n*n))]
for k in L:
crible[k]=0
def Stocke_Premiers():
global crible, premiers
debut() #début du crible d'Atkin
fin() #fin du crible d'Atkin
for i in range(5,limite):
if crible[i]:
premiers.append(i)
crible=[] # récupération espace
#teste l'hypothèse de Sierpsinski (force brute pour a,b <=k)
def sierpinski2(n,k):
for a in range (max(2,n/5)+1,k+1):
for b in range (max(2,int(a*n/(5*a-n)))+1,k+1):
if not (n*a*b)%(5*a*b-n*b-n*a):
return True
return False
# teste l'hypothèse de Sierpinski au moyen de l'algo glouton
def sierpinski1(n):
return len(egypt([5,n]))<=3
#pgcd de deux entiers
def pgcd(m,n):
while m%n!=0:
r=m
m=n
n=r%n
return n
#simplification d'une fraction
def simplif(f):
return [f[0]/pgcd(f[0],f[1]),f[1]/pgcd(f[0],f[1])]
# décomposition de f en somme de fractions egyptiennes
#par un algorithme 'glouton'
# le résultat ne fait apparaître que les dénominateurs des fractions egyptiennes
def egypt(f):
f=simplif(f)
result=[]
i=2
while f[0]!=1:
if not f[1]%f[0]:
i= f[1]/f[0]
else:
i=f[1]/f[0]+1
f=simplif([f[0]*i-f[1],f[1]*i])
result.append(i)
result.append(f[1])
return result
def bindfunctions(module):
L=[value for key,value in module.__dict__.items() if type(value) is types.FunctionType]
for f in L:
psyco.bind(f)
def main():
starttime = time.time()
bindfunctions(sys.modules[__name__])
Stocke_Premiers()
print premiers[-1]
#on récupère les nombres premiers pour laquelle la conjecture n'est pas vérifiée par l'algo de Fibonacci
M=[n for n in premiers if not sierpinski1(n)]
print len(M) # combien y en-a-t-il ?
N=[n for n in M if not sierpinski2(n,8000)]
print len(N) # si affiche 0 c'est que tout est vérifié
print "Exécution en %f secondes." % (time.time() - starttime)
if __name__ == '__main__':
main() |
) : ne commence pas par prolog.
) et de regarder vers des choses simples comme par exemple alphabeta, minmax, etc...
Répondre avec citation
Envoyé par Alp
Partager