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

# The goal of this code is, given a particular set X of positive integers and a threshold N,
# to find the size of the largest subset(s) A of {1,2,...,N} (hereby denote by [1,N]) such that
# no pair of elements of A differ by an element of X, as well at least some of the specific
# qualifying sets of that maximal size.



# To run all of this, you first need to load a dictionary called NUM, presumably from a pickled file.
# Specifically, you choose a set X of "bad" differences, an initial interval size N0, and an
# "extension" length m. The dictionary encodes, for every bad difference-free subset A of [1,N0],
# 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. For example, the file NUM35100.p
# stores, for each square difference free subset of [1,35], encoded into single integers via binary expansion,
# the maximal number of integers in [36,135] that can appended to the set while maintaining a lack of square differences.
# 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. The code to build this dictionary,
# as well as instructions for running, pickling, and unpickling, are in a separate file called DifferencesPrep.


# Also, if the goal is to push N as far as possible, the process should be somewhat progressive, 
# in the sense that if you want to effectively run the algorithm
# for a specific value of N then you should already know the "answer", meaning the SIZE of the largest bad difference-free
# set, for all values less than  N, or at least pretty close. Those answers should be stored in a dictionary
# that is then used as input into the main algorithm, which is called RothStyle

# For example, suppose you knew the answers for 1 <= N <= 150,
# and specifically that the answer for N=150 was 31. Then, if you wanted to try to do N=160, you should store all
# the known answers up to 150 in a dictionary, called Dict let's say, so in particular Dict[150]=31. You should also
# go ahead and define Dict[N]=31 for 151 <= N <= 160, and input Dict into the appropriate place in the main algorithm.

# Example of execution: Suppose the set of bad differences is the squares, we've already done everything up to N=236, the
# answer for 236 is 47, all the results are stored in a dictionary called DF, and we want to try N=242,
# so we also define DF[N]=47 for 237 <= N <= 242.
# Suppose also that we have our pickled dictionary NUM35100.p as described above. The following
# sequence would do the job:

#    X=squares(300)
    
#    RothStyleInit(35,X)

#    import pickle

#    NUM= pickle.load( open( "NUM35100.p", "rb" ))       this can take a while if the file is large

#    RothStyle(242,35,100,X,47,DF)      this is precisely the farthest we've gotten so far for squares, and it took about a month

# As the algorithm runs, if it finds any new "record holders", it prints the integers that encode the sets via their binary expansion.
# In particular, if you copy one of these integers (call it x), let S=bin(x), and then run GetSet(S), you can actually see these
# maximal sets with no differences that lie in X.

# Everything that goes into the RothStyle algorithm is done and explained below.



# 'Good' will store ALL bad difference free subsets of [1,N0] containing 1, encoded into single integers via their binary expansion,
# where N0 is the threshold from the stored NUM dictionary

Good=defaultdict(set)

# In the initial stage, D keeps track of the size of the largest square difference free subsets of [1,N0] 
D=defaultdict(int)


# squares(N) builds the set of squares up to N

def squares(N):
    X= set([a**2 for a in range(1,floor(sqrt(N))+1)])
    return X


# PM1(N) builds the set of p-1 up to N

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


# RothStyleInit takes as input the interval threshold N and the set of "bad" differences X, and encodes ALL bad difference free
# subsets of [1,N0] containing 1 and stores them in Good[N0]. The way it does this is by encoding the set of bad differences into an integer T,
# then calling the function BasicDFS, which is explained below. The threshold N0 here should correspond to the threshold in the stored
# NUM dictionary, and we could probably just store the Good[N0] as well, but it only takes a second anyway.



def RothStyleInit(N0,X):

    start_time = datetime.datetime.now()

    T=0

    for x in range(1,N0+1):

        if x in X: T=T+2**(x-1)


    BasicDFS(1,N0,T)

    print(D[N0])

    end_time = datetime.datetime.now()
    print(end_time-start_time)




# BasicDFS takes as input an integer x (encoding a "bad" difference free set of integers via its binary representation),
# the initial interval threshold N0, and an integer T (encoding the set of bad differences via its binary representation).
# After checking if the set encoded by x is a new "record holder", or if the encoded set has reached the end of the interval,
# the function builds a new integer by appending a 0
# to the binary expansion of x, which represents the choice to NOT include the next available integer in the set, and also,
# provided the inclusion of the next integer does not induce a square difference, the function also builds a new integer by
# appending a 1 to the binary expansion of x, which represents the choice TO include the next available integer in the set
# The newly constructed integer(s) are then fed back to the function, with the same N0 and T. In the end, this function encodes
# all bad difference free subsets of [1,N0] which "start" with the set encoded by x, and it stores them in Good[N0].
# Therefore, when RothStyleInit calls BasicDFS(1,N0,T), it encodes ALL bad difference free subsets of [1,N0] containing 1

def BasicDFS(x,N0,T):

    s=bin(x)

    n=len(s)-2

    j=s.count('1')

    if j>D[N0]:
        
        D[N0]=copy(j)

    if n==N0:

        Good[N0].add(x)
        
        return

    else:

        w=x<<1

        BasicDFS(w,N0,T)

        if not x&T: BasicDFS(w+1,N0,T)

        

# RothStyle is the main algorithm. Once we have the depickled NUM dictionary and the initial Good[N0] collection of encoded sets,
# we loop through all the elements of Good[N0], extending the bad difference free sets in all possible ways, while pruning the tree
# along the way if the set gets too small, or we know from the NUM dictionary that the set can't be extended densely enough,
# to set a new "record". This is done by calling DFS, which has a built in "potential" test to determine when a particular set
# should be discarded. If new record holders are found, they are printed (in their encoded, single integer forms).

# Note all the inputs here: N is the desired threshold, N0 is the initial interval size and m is the extension size used
# in the imported dictionary discussed at the top of this file, X is the set of avoided differences, L is a lower bound
# on the answer determined from running the algorithm for smaller values of N, and Dict is the dictionary of answers
# determined from running the algorithm for smaller values of N.


def RothStyle(N,N0,m,X,L,Dict): 
    
    


    start_time = datetime.datetime.now()

    T=0
    for x in range(1,N+1):
        if x in X: T=T+2**(x-1)

    counter=0    
    for x in Good[N0]:
        counter=counter+1
        if counter%1000==0: print(counter)
        DFS(x,T,N,N0,m,L,Dict)

    print(D[N])

    end_time = datetime.datetime.now()
    print(end_time-start_time)



# DFS works the same as BasicDFS, except there's a built in check, called 'FinalPotential', that discards a set if it is provably
# incapable of being extended to a new record holder.

# Winners keeps track of sets found that are as big or bigger than the previous record.

Winners=set()



def DFS(x,T,N,N0,m,L,Dict):

    n=len(bin(x))-1
    j=bin(x).count('1')

    if j>D[N]:
        print(j)
        print(x)
        D[N]=copy(j)
        
    if j>=L:
        Winners.add(x)
        print(x)

    if n==N+1:

        

        return

        

        
    else:

        w=copy(x)<<1

        if FinalPotential(w,n,j,N,N0,m,L,Dict):
            DFS(w,T,N,N0,m,L,Dict)

        if not x&T:
            DFS(w+1,T,N,N0,m,L,Dict)
            

# The three 'NewPotential' tests incorporate previously computed records for maximal bad difference free sets, as well as all the info
# in the NUM dictionary, to determine if a set has a chance to be extended to a new record holder. 'Final Potential' just checks that a set
# passes all three tests.



def NewPotential1(w,n,j,N,N0,m,L,Dict):


    z=2**(N0)-1
    y=w&z

    m1=min(m, N-n)

    m2=max(0,Dict[N-n-m])

    if j+NUM[y,m1]+m2>=L: return True
    else: return False

def NewPotential2(w,n,j,N,N0,m,L,Dict):


    C=ceil(N/2)
    if n>= C: return True
    else:
        z=2**(N0)-1
        y=w&z

        m1=min(m, C-n)

        m2=max(0,Dict[C-n-m])

        if j+NUM[y,m1]+m2>=ceil(L/2): return True
        else: return False


def NewPotential3(n,j,N,L,Dict):

    K=max(1,ceil(L/2)-Dict[ceil(N/2)-n],L-Dict[N-n])

    if j >= K: return True
    else: return False


def FinalPotential(w,n,j,N,N0,m,L,Dict):

    if NewPotential1(w,n,j,N,N0,m,L,Dict) and NewPotential2(w,n,j,N,N0,m,L,Dict) and NewPotential3(n,j,N,L,Dict):
        return True

    else: return False





            




# GetSet takes in a string and spits out the set of all bits of the string containing a 1 (shifted by 2 due to Pythons binary string conventions).
# So, if we have a set encoded into an integer x, we simply let S=bin(x), and then GetSet(S) is the set we want.

    

def GetSet(S):
    
    Y=set()
    for n in range(1,len(S)+1):
        if S[-len(S)-1+n]=='1': Y.add(n)

    Y=[y-2 for y in Y]

    return sorted(Y)




#Everything saved from here down is completely rigorously verified data. DF is for squares, DPF is for p-1

DF = defaultdict(int)

DF[1]=1
DF[2]=1
DF[3]=2
DF[4]=2
DF[5]=2
DF[6]=3
DF[7]=3
DF[8]=4
DF[9]=4
DF[10]=4
DF[11]=5
DF[12]=5
DF[13]=6
DF[14]=6
DF[15]=6
DF[16]=7
DF[17]=7
DF[18]=8
DF[19]=8
DF[20]=8
DF[21]=9
DF[22]=9
DF[23]=10
DF[24]=10
DF[25]=10
DF[26]=10
DF[27]=10
DF[28]=10
DF[29]=10
DF[30]=10
DF[31]=10
DF[32]=10
DF[33]=10
DF[34]=10
DF[35]=11
DF[36]=11
DF[37]=11
DF[38]=12
DF[39]=12
DF[40]=12
DF[41]=12
DF[42]=12
DF[43]=13
DF[44]=13
DF[45]=13
DF[46]=13
DF[47]=13
DF[48]=14
DF[49]=14
DF[50]=14
DF[51]=14
DF[52]=14
DF[53]=15
DF[54]=15
DF[55]=15
DF[56]=15
DF[57]=15
DF[58]=16
DF[59]=16
DF[60]=16
DF[61]=16
DF[62]=16
DF[63]=16
DF[64]=16
DF[65]=16
DF[66]=17
DF[67]=17
DF[68]=18
DF[69]=18
DF[70]=18
DF[71]=19
DF[72]=19
DF[73]=20
DF[74]=20
DF[75]=20
DF[76]=20
DF[77]=20
DF[78]=20
DF[79]=20
DF[80]=20
DF[81]=21
DF[82]=21
DF[83]=21
DF[84]=21
DF[85]=21
DF[86]=22
DF[87]=22
DF[88]=22
DF[89]=22
DF[90]=22
DF[91]=22
DF[92]=23
DF[93]=23
DF[94]=23
DF[95]=23
DF[96]=23
DF[97]=24
DF[98]=24
DF[99]=24
DF[100]=24
DF[101]=24
DF[102]=25
DF[103]=25
DF[104]=25
DF[105]=25
DF[106]=25
DF[107]=26
DF[108]=26
DF[109]=26
DF[110]=26
DF[111]=26
DF[112]=27
DF[113]=27
DF[114]=27
DF[115]=27
DF[116]=27
DF[117]=27
DF[118]=28
DF[119]=28
DF[120]=29
DF[121]=29
DF[122]=29
DF[123]=29
DF[124]=29
DF[125]=30
DF[126]=30
DF[127]=30
DF[128]=30
DF[129]=30
DF[130]=30
DF[131]=31
DF[132]=31
DF[133]=32
DF[134]=32
DF[135]=32
DF[136]=32
DF[137]=32
DF[138]=33
DF[139]=33
DF[140]=33
DF[141]=33
DF[142]=33
DF[143]=33
DF[144]=34
DF[145]=34
DF[146]=35
DF[147]=35
DF[148]=35
DF[149]=35
DF[150]=35
DF[151]=36
DF[152]=36
DF[153]=36
DF[154]=36
DF[155]=36
DF[156]=36
DF[157]=37
DF[158]=37
DF[159]=38
DF[160]=38
DF[161]=38
DF[162]=38
DF[163]=38
DF[164]=39
DF[165]=39
DF[166]=39
DF[167]=39
DF[168]=39
DF[169]=39
DF[170]=39
DF[171]=39
DF[172]=39
DF[173]=39
DF[174]=39
DF[175]=39

DF[176]=39
DF[177]=39
DF[178]=39
DF[179]=39
DF[180]=39
DF[181]=39
DF[182]=39
DF[183]=39
DF[184]=39
DF[185]=39
DF[186]=39
DF[187]=39
DF[188]=39

for n in range(189,199):
    DF[n]=40

for n in range(199,203): #double check 202
    DF[n]=41

for n in range(203,206):
    DF[n]=42

for n in range(206,208):
    DF[n]=43

for n in range(208,219):
    DF[n]=44

for n in range(219,223):
    DF[n]=45

for n in range(223,236):
    DF[n]=46

for n in range(236,242):
    DF[n]=47

DF[242]=48

DPF=defaultdict(int)

DPF[1]=1
DPF[2]=1
DPF[3]=1
DPF[4]=2
DPF[5]=2
DPF[6]=2
DPF[7]=2
DPF[8]=2
DPF[9]=3
DPF[10]=3
DPF[11]=3
DPF[12]=4
DPF[13]=4
DPF[14]=4
DPF[15]=4
DPF[16]=4
DPF[17]=4
DPF[18]=4
DPF[19]=4
DPF[20]=4
DPF[21]=4
DPF[22]=4
DPF[23]=4
DPF[24]=4
DPF[25]=4
DPF[26]=4
DPF[27]=4
DPF[28]=4
DPF[29]=4
DPF[30]=4
DPF[31]=4
DPF[32]=4
DPF[33]=5
DPF[34]=5
DPF[35]=5
DPF[36]=6
DPF[37]=6
DPF[38]=6
DPF[39]=6
DPF[40]=6
DPF[41]=6
DPF[42]=6
DPF[43]=6
DPF[44]=6
DPF[45]=6
DPF[46]=6
DPF[47]=6
DPF[48]=6
DPF[49]=7
DPF[50]=7
DPF[51]=7
DPF[52]=8
DPF[53]=8
DPF[54]=8
DPF[55]=8
DPF[56]=8
DPF[57]=8
DPF[58]=8
DPF[59]=8
DPF[60]=8
DPF[61]=8
DPF[62]=8
DPF[63]=8
DPF[64]=8
DPF[65]=9
DPF[66]=9
DPF[67]=9
DPF[68]=10
DPF[69]=10
DPF[70]=10
DPF[71]=10
DPF[72]=10
DPF[73]=10
DPF[74]=10
DPF[75]=10
DPF[76]=10
DPF[77]=10
DPF[78]=10
DPF[79]=10
DPF[80]=10
DPF[81]=10
DPF[82]=10
DPF[83]=10
DPF[84]=10
DPF[85]=10
DPF[86]=10
DPF[87]=10
DPF[88]=10
DPF[89]=10
DPF[90]=10
DPF[91]=10
DPF[92]=10
DPF[93]=10
DPF[94]=10
DPF[95]=10
DPF[96]=10
DPF[97]=10
DPF[98]=10
DPF[99]=10
DPF[100]=10
DPF[101]=10
DPF[102]=10
DPF[103]=10
DPF[104]=10
DPF[105]=11
DPF[106]=11
DPF[107]=11
DPF[108]=12
DPF[109]=12
DPF[110]=12
DPF[111]=12
DPF[112]=12
DPF[113]=12
DPF[114]=12
DPF[115]=12
DPF[116]=12
DPF[117]=12
DPF[118]=12
DPF[119]=12
DPF[120]=12
DPF[121]=12
DPF[122]=12
DPF[123]=12
DPF[124]=12
DPF[125]=12
DPF[126]=12
DPF[127]=12
DPF[128]=12
DPF[129]=12
DPF[130]=12
DPF[131]=12
DPF[132]=12
DPF[133]=13
DPF[134]=13
DPF[135]=13
DPF[136]=14
DPF[137]=14
DPF[138]=14
DPF[139]=14
DPF[140]=14
DPF[141]=14
DPF[142]=14
DPF[143]=14
DPF[144]=14
DPF[145]=14
DPF[146]=14
DPF[147]=14
DPF[148]=14
DPF[149]=14
DPF[150]=14
DPF[151]=14
DPF[152]=14
DPF[153]=15
DPF[154]=15
DPF[155]=15
for n in range(156,209):
    DPF[n]=16

for n in range(209,212):
    DPF[n]=17

for n in range(212,217):
    DPF[n]=18

for n in range(217,220):
    DPF[n]=19

for n in range(220,243):
    DPF[n]=20

for n in range(243,246):
    DPF[n]=21

for n in range(246,299):
    DPF[n]=22

for n in range(299,302):
    DPF[n]=23

for n in range(302,401):
    DPF[n]=24