4816.sagews

def distance(p,q):
    p = vector(p)
    q = vector(q)
    d = norm(p-q)
    return d
    
def checkGaussianPrimes(x,y):
    if x!= 0 and y != 0:
        d = x**2 +y**2
        if d in Primes():
            return True
    else:
        p = int(sqrt(x**2 + y**2))
        if mod((p-3),4) == 0 and p in Primes():
            return True
            
def gaussianPrimes(num):
    points = []
    for x in range(0,num):
        for y in range(0,num):
            if x>=y:
                if checkGaussianPrimes(x,y) == True:
                    points.append((x,y))      

    return points       
        
def gaussianPlot(alist):
    g = Graphics()
    for apoint in alist:
        p = point(apoint)
        g = g+p
    return g
    
    
def steplist(start, stepSize):
    Slist = []
    X_init = start[0]
    Y_init = start[1]
    
    for x in range(X_init-stepSize,stepSize + X_init+1 ):
        for y in range(Y_init-stepSize,stepSize + Y_init +1 ):
            if x >= y and x>=0 and y>=0:
                if (mod(x,2)==0 and mod(y,2)==0) or (mod(x,2)!=0 and mod(y,2)!=0):
                    pass
                    
                else:
                    d = distance((X_init,Y_init),(x,y))
                    if d <=float(stepSize) and checkGaussianPrimes(x,y) == True:
                        Slist.append((x,y))
    
    return Slist
       
    
def buildPath(start, stepSize):
    Glist = start
    for point in Glist:
        slist = steplist(point,stepSize)
        for p in slist:
            if p not in Glist:
                Glist.append(p)
                
    Glist_sorted = sorted(Glist, key=lambda tup: tup[0])
    return Glist_sorted   
    

    
def drawPath(alist,stepSize):
    g = Graphics()
    current = alist[0]
    for apoint in alist:
        for i in xrange(len(alist)):
            if distance(apoint,alist[i]) <= stepSize:
                l = line([apoint,alist[i]])
                g = g+l
                
    return g
    
def main():
    t = cputime()
    g = Graphics()
    num = 90
    start=[(1,1)]
    stepSize = sqrt(8)
    Gaussian = gaussianPrimes(num)
    path = buildPath(start, stepSize)
    print "Path : " + str(path)
    print "Maximum distance is " + str(float(distance((0,0),path[-1])))
    print "Farthest point reached with step of size " +str(stepSize)+ " is " + str(path[-1])
    print "Time Elapsed " + str(cputime(t))
    T = cputime()           
    pointPlot = gaussianPlot(Gaussian)  
    pathFound = drawPath(path,stepSize)    
    g = g+pointPlot + pathFound
    g.show()   
    print "Time Elapsed for plotting " + str(cputime(T))           
    
main()

Path : [(1, 1), (2, 1), (3, 0), (3, 2), (4, 1), (5, 2), (5, 4), (6, 1), (6, 5), (7, 0), (7, 2), (8, 3), (8, 5), (8, 7), (9, 4), (10, 1), (10, 3), (10, 7), (10, 9), (11, 4), (11, 6), (11, 0), (12, 7), (13, 2), (13, 8), (13, 10), (13, 12), (14, 1), (14, 9), (14, 11), (15, 2), (15, 4), (15, 14), (16, 1), (16, 5), (16, 9), (17, 2), (17, 8), (17, 10), (17, 12), (18, 5), (18, 7), (18, 17), (19, 0), (19, 6), (19, 10), (19, 14), (19, 16), (20, 1), (20, 3), (20, 7), (20, 11), (20, 13), (20, 19), (21, 4), (21, 10), (22, 5), (22, 13), (22, 15), (22, 17), (23, 8), (23, 12), (23, 18), (23, 20), (23, 0), (23, 22), (24, 5), (24, 19), (24, 1), (25, 4), (25, 6), (25, 12), (25, 14), (25, 16), (25, 22), (25, 24), (26, 5), (26, 11), (26, 1), (26, 9), (26, 21), (26, 25), (27, 2), (27, 10), (27, 20), (27, 22), (28, 5), (28, 13), (28, 15), (28, 25), (29, 4), (29, 6), (29, 10), (29, 16), (30, 11), (30, 13), (30, 23), (30, 29), (31, 4), (31, 6), (31, 10), (31, 0), (31, 16), (31, 20), (31, 26), (31, 30), (32, 3), (32, 5), (32, 13), (32, 15), (32, 23), (32, 27), (33, 2), (33, 8), (33, 20), (33, 28), (33, 32), (34, 5), (34, 9), (34, 11), (34, 15), (34, 21), (34, 29), (35, 2), (35, 8), (35, 16), (35, 18), (35, 22), (35, 24), (35, 26), (35, 34), (36, 5), (36, 1), (36, 19), (36, 29), (36, 35), (37, 2), (37, 8), (37, 18), (37, 28), (37, 30), (37, 32), (38, 3), (38, 7), (38, 17), (38, 13), (38, 15), (38, 23), (38, 25), (39, 10), (39, 16), (39, 34), (40, 1), (40, 3), (40, 11), (40, 17), (40, 23), (40, 33), (41, 4), (41, 14), (41, 20), (41, 26), (41, 34), (42, 5), (42, 13), (42, 17), (42, 23), (42, 25), (43, 12), (43, 10), (43, 8), (43, 22), (43, 28), (43, 30), (43, 0), (43, 40), (43, 42), (44, 15), (44, 19), (44, 9), (44, 21), (44, 29), (44, 31), (44, 39), (44, 41), (45, 14), (45, 16), (45, 8), (45, 2), (45, 32), (45, 34), (45, 38), (46, 15), (46, 19), (46, 21), (46, 11), (46, 25), (46, 29), (46, 39), (46, 41), (47, 8), (47, 10), (47, 20), (47, 22), (47, 2), (47, 0), (47, 30), (48, 13), (48, 17), (48, 23), (48, 37), (48, 35), (48, 43), (48, 47), (49, 16), (49, 6), (49, 20), (49, 4), (49, 30), (49, 40), (49, 36), (49, 34), (49, 44), (49, 46), (50, 11), (50, 17), (50, 19), (50, 7), (50, 31), (50, 39), (50, 27), (50, 43), (51, 14), (51, 16), (51, 20), (51, 4), (51, 40), (52, 5), (52, 7), (52, 3), (52, 33), (52, 35), (52, 37), (52, 27), (52, 25), (52, 45), (53, 12), (53, 20), (53, 10), (53, 32), (53, 30), (53, 38), (53, 28), (53, 40), (54, 11), (54, 1), (54, 31), (54, 41), (54, 25), (55, 12), (55, 14), (55, 8), (55, 6), (55, 4), (55, 32), (55, 26), (55, 42), (56, 9), (56, 11), (56, 15), (56, 1), (56, 25), (56, 39), (56, 41), (57, 8), (57, 2), (57, 32), (57, 22), (58, 7), (58, 13), (58, 3), (58, 5), (58, 25), (58, 27), (58, 37), (59, 6), (59, 10), (59, 14), (59, 0), (59, 34), (59, 24), (59, 26), (59, 20), (60, 13), (60, 23), (60, 29), (60, 31), (60, 37), (60, 17), (61, 10), (61, 14), (61, 34), (61, 30), (61, 24), (61, 26), (62, 13), (62, 33), (62, 23), (62, 17), (63, 32), (63, 38), (63, 40), (64, 11), (64, 9), (64, 25), (64, 19), (64, 29), (65, 8), (65, 6), (65, 4), (65, 2), (65, 34), (65, 36), (65, 38), (65, 24), (65, 18), (65, 16), (65, 14), (65, 28), (66, 1), (66, 35), (66, 41), (66, 29), (67, 2), (67, 0), (67, 40), (67, 22), (67, 20), (67, 18), (67, 28), (68, 35), (68, 23), (68, 43), (69, 40), (69, 26), (70, 37), (70, 39), (70, 41), (71, 36), (71, 34), (71, 26), (72, 37), (73, 32), (73, 30), (73, 28), (74, 35), (74, 39), (74, 29), (74, 25), (75, 34), (75, 38), (75, 26), (76, 35), (76, 39), (76, 41), (76, 31), (77, 40), (77, 30), (78, 35), (78, 43), (79, 36), (79, 40), (80, 33), (80, 41), (81, 34), (81, 40), (82, 35), (82, 43), (82, 37), (84, 41)] Maximum distance is 93.4719209175 Farthest point reached with step of size 2*sqrt(2) is (84, 41) Time Elapsed 9.77

Time Elapsed for plotting 451.4