Hello, I am trying to solve the question 175 of the Turing Challenge. We create a network of hexagonal tiles containing the following integers 1, 2, 3, 4, ... I represent this network in a square matrix by placing the number 1 in the center of the matrix.
We must calculate the difference between each tile numbered n and each of its six neighbors, we will call DP (n) the number of these differences # which are a prime number.
My problem is this: I have to calculate a lot of times the function below. We save in DP3 the n which are surrounded by exactly 3 prime numbers. numbers.
Here is all my script. My idea is this: every time I have completed a turn I can calculate the DP3 of the previous turn. The program stops when len (DP3) = 2016. As the spirals become bigger and bigger you have to make more and more calls to the DP3 () search function.
My question is: is it possible to speed up this function?
PS: I'm sorry for my bad english. I also note that I am a beginner in programming.
# TURING 175 - Tuiles hexagonales (essai VII) DERNIER 26/11/18 OK ma!s trop lent
# Une tuile hexagonale portant le numéro 1 est entourée d'un anneau de six tuiles numérotées de 2 à 7, la première tuile de l'anneau étant # posée à midi et en tournant dans le sens inverse des aiguilles d'une montre.
# De nouveaux anneaux sont ajoutés de la même façon, les anneaux suivants étant numérotés 8 à 19, de 20 à 37, de 38 à 61, et ainsi de
# suite. Le diagramme ci-contre montre les trois premiers anneaux.
# En calculant la différence entre la tuile numérotée n et chacune de ses six voisines, nous appellerons DP(n) le nombre de ces différences # qui sont un nombre premier.
# Par exemple, autour de la tuile numéro 8, les différences sont 12, 29, 11, 6, 1 et 13. Donc DP(8)=3.
# De la même manière, autour de la tuile numéro 17, les différences sont 1, 17, 16, 1, 11 et 10, d'où DP(17)=2.
# On peut montrer que la valeur maximale de DP(n) est 3.
# Quand toutes les tuiles pour lesquelles DP(n)=3 sont énumérées dans l'ordre croissant pour former une suite, la 10ème tuile
# porte le numéro 271.
# Trouver le numéro de la 2016ème tuile de cette suite.
temps = walltime()
var('n,x,y')
def rechercheDP3(n,x,y):
n = M[x, y] # test 6 boxes around n
y]
d = [ M[x-1, y], M[x, y+1], M[x+1, y+1], M[x+1, y], M[x, y-1], M[x-1, y-1] ] # les 6 cases qui entourent n
dp = len( [t for t in d if is_prime(abs(n-t))] )
if dp == 3:
DP3.append(n)
return
lim = 17 # Attention, il faut que lim soit impair
M = matrix(ZZ, lim, lim) # création matrice nulle M ATTENTION: X est vertical vers le bas & Y est horizontal vers la droite
x, y = lim//2, lim//2 # centre de M on compte à partir de 0
print "Centre:", x, y
M[x, y] = 1 # le nombre 1 est placé au centre puis le 1er tour (2,3,4,5,6,7)
M[x-1, y] = 2
M[x-1, y-1] = 3
M[x, y-1] = 4
M[x+1, y] = 5
M[x+1, y+1] = 6
M[x, y+1] = 7
n = 7
x_debut_prec, y_debut_prec = x-1, y
DP3 = [1]
maxtour = lim//2
tour = 1 # on a déjà placé le 1er tour 2...7
grandeur_deplact = 1 # plus la spirale est extérieure plus le déplacement est grand
print "maxtour = ", maxtour
print "*",walltime(temps)
#print M # valable si n est petit
#print
# on remplit la table en spirale
while tour < maxtour and len(DP3)<2016: # 2016 est la valeur demandée dans l'énoncé
tour += 1
grandeur_deplact +=1
# on se place au-dessus de la case de départ (2,8,20,...) -> 6 trajets de 1 au 1er tour, de 2 au 2d tour, de 3 au 3e tour, ....
x = x_debut_prec - 1
n += 1 #n = dernier_terme_tour + 1
M[x, y] = n
x_debut_suivant, y_debut_suivant = x, y # coord case départ tour suivant
for i in xrange(grandeur_deplact): # trajet 1 horizontal gauche
y = y-1
n += 1
M[x, y] = n
for i in xrange(grandeur_deplact): # trajet 2 vertical bas
x = x+1
n += 1
M[x, y] = n
for i in xrange(grandeur_deplact): # trajet 3 oblique bas droit
x = x+1
y = y+1
n += 1
M[x, y] = n
for i in xrange(grandeur_deplact): # trajet 4 horizontal droite
y = y+1
n += 1
M[x, y] = n
for i in xrange(grandeur_deplact): # trajet 5 vertical haut
x = x-1
n += 1
M[x, y] = n
for i in xrange(grandeur_deplact-1): # trajet 6 oblique haut gauche -1 car on retombe sur le 1er -> le tour est fini
x = x-1
y = y-1
n += 1
M[x, y] = n
dernier_tour_n = n # on mémorise le tour qu'on vient de faire
xfin_tour = x
yfin_tour = y
# recherche les dp3 -> on recommence le tour précédent et on cherche ses DP3
grandeur_deplact -= 1
# on se place au-début du tour précédent (2,8,20,38,62,92,...)
x,y = x_debut_prec, y_debut_prec
np = M[x,y] # np comme cela on ne touche pas à n
rechercheDP3(np,x,y)
for i in xrange(grandeur_deplact): # trajet 1 horizontal gauche
y = y-1
np += 1
rechercheDP3(np,x,y)
for i in xrange(grandeur_deplact): # trajet 2 vertical bas
x = x+1
np += 1
rechercheDP3(np,x,y)
for i in xrange(grandeur_deplact): # trajet 3 oblique bas droit
x = x+1
y = y+1
np += 1
rechercheDP3(np,x,y)
for i in xrange(grandeur_deplact): # trajet 4 horizontal droite
y = y+1
np += 1
rechercheDP3(np,x,y)
for i in xrange(grandeur_deplact): # trajet 5 vertical haut
x = x-1
np += 1
rechercheDP3(np,x,y)
for i in xrange(grandeur_deplact-1): # trajet 6 oblique haut gauche
x = x-1
y = y-1
np += 1
rechercheDP3(np,x,y)
# retour aux bonnes valeurs
grandeur_deplact += 1 # on revient à la valeur exacte pour le tour suivant
x = x_debut_suivant
y = y_debut_suivant
x_debut_prec, y_debut_prec = x_debut_suivant, y_debut_suivant
if len(DP3) >= 2016:
print DP3(2015)
else:
print "len(DP3) = ", len(DP3)
print "Durée = ", walltime(temps)
