from collections import defaultdict from copy import copy from math import sqrt from math import ceil from math import floor from math import log import datetime #This is the code used to build the initial dictionary that drives the DifferencesMain code. #Specifically, you choose a set X of "bad" differences, an initial interval size N0, and an #"extension" length m. This algorithm takes every bad difference-free subset A of [1,N0] and #determines the maximum number of terms in an extension B in [N0+1,N0+m] such that the union #of A and B remains bad difference-free. #Example of execution: If your set of bad differences is the squares, and you want to encode, #for each square difference-free subset A of [1,25], the maximum amount that you #can extend A to a subset of [1,75] while remaining square difference-free, then after #running this module you could do: # X= squares(100) # NumAlgoFull(25,50,X) #Then to pickle that information for later use, you could do: # import pickle # pickle.dump(NUM, open( "NUM2550.p", "wb")) #The info is now saved in a file called NUM2550.p, and to recall it and use it later #you would do: #import pickle #NUM=pickle.load( open( "NUM2550.p", "rb" )) #As a reference, for the squares, NUM35100.p took about two weeks to build on a personal laptop. #It's size when unpickled is about 2GB. Good=defaultdict(set) D=defaultdict(int) def squares(N): X= set([a**2 for a in range(1,floor(sqrt(N))+1)]) return X def PM1(N): numbers = set(range(N, 1, -1)) X = [] while numbers: p = numbers.pop() X.append(p-1) numbers.difference_update(set(range(p*2, N+1, p))) return X def NewAlgo(N,X): start_time = datetime.datetime.now() T=0 for x in range(1,N+1): if x in X: T=T+2**(x-1) #Good[0,0]=set([0]) #D[0]=0 Good[0,0]=set([0]) D[0]=0 for n in range(1,N+1): for j in range(0,D[n-1]+1): for x in Good[n-1,j]: Good[n,j].add(x<<1) if not x&T: Good[n,j+1].add((x<<1)+1) del(Good[n-1,j]) memclear(n) if Good[n,D[n-1]+1]: D[n]=D[n-1]+1 else: D[n]=D[n-1] print(n) end_time = datetime.datetime.now() print(end_time-start_time) NUM=defaultdict(int) def NumInit(N): for j in range(0,D[N]+1): for x in Good[N,j]: NUM[x,0]=0 def Potential(x,w,n,n1,j1,N): z=2**(N)-1 y=w&z if j1+NUM[y,n-n1]>NUM[x,n-1]: return True else: return False def NumAlgo(N, n, X): start_time = datetime.datetime.now() T=0 for x in range(1,N+n+1): if x in X: T=T+2**(x-1) for j in range(0,D[N]+1): for x in Good[N,j]: NUM[x,n]=copy(NUM[x,n-1]) GE=defaultdict(set) GE[0,0]=set([x]) DE=defaultdict(int) DE[0]=0 for n1 in range(1,n+1): for j1 in range(0,DE[n1-1]+1): for y in GE[n1-1,j1]: w=copy(y)<<1 if Potential(x,w,n,n1,j1,N): GE[n1,j1].add(w) if not y&T: GE[n1,j1+1].add(w+1) del(GE[n1-1,j1]) memclearE(n1,x,GE) if GE[n1,DE[n1-1]+1]: DE[n1]=DE[n1-1]+1 else: DE[n1]=DE[n1-1] if DE[n]==NUM[x,n-1]+1: NUM[x,n]=copy(DE[n]) print(j) end_time = datetime.datetime.now() print(end_time-start_time) def NumAlgoFull(N,m,X): start_timeFull = datetime.datetime.now() NewAlgo(N,X) NumInit(N) for n in range(1,m+1): NumAlgo(N,n,X) print("n=",n) end_timeFull = datetime.datetime.now() print(end_timeFull-start_timeFull) def NumExtend(N,m,m1,X): for n in range(m+1,m1+1): NumAlgo(N,n,X) print("n=",n) def memclear(N): for n in range(1,N): for j in range(1,D[n]+1): if Good[n,j]: del(Good[n,j]) def memclearE(N,x,GE): for n in range(1,N): for j in range(1,NUM[x,n]+1): if GE[n,j]: del(GE[n,j])