""" Compute values of a(n): number of ones required to build n using +,^ The strategy here is to first determine all n such that a(n) = 2, then 3, then 4, and so on. In each round, we take both operations of all pairs of numbers whose previously known complexities add to the desired target. Since we proceed in order of values, we know that discovered expressions are minimal as desired. Note that it is safe to ignore large arguments n without jeopardizing the values for small n because both operators produce values larger than either argument (except for trivial exponentiations 1^k and k^1, which produce nothing new). """ import math import operator reva = [[], [1]] lopd = [[], [0]] ropd = [[], [0]] oper = [[], [1]] known = {1: 1} opadd = 2 opsub = 3 opmul = 4 opdiv = 5 oppow = 6 oprt = 7 nops = 8 expTwoignore = 30 def ignpow(b,p): if b == 1: return 1 if expTwoignore == 0: return b**p if p > expTwoignore: return 0 if b > 2 and p > expTwoignore/math.log(b,2): return 0 return b**p ops = {opadd: operator.add, #opsub: operator.sub, #opmul: operator.mul, #opdiv: operator.floordiv, oppow: ignpow, #oprt: introot } trybothorders = {opadd: False, opsub: False, opmul: False, opdiv: False, oppow: True, oprt: True } symbol = {1: '1', opadd: '+', opsub:'-', opmul:'*', opdiv:'/', oppow:'^', oprt:'√'} ignore = 2**expTwoignore + 1 if expTwoignore == 0: ignore = 0 def printtree(k, prefix=''): report = f"{k}: " newprefix = prefix + ' ' for c in range(0, len(reva)): try: ix = reva[c].index(k) except: continue report += f"{lopd[c][ix]}{symbol[oper[c][ix]]}{ropd[c][ix]}, " left = False if lopd[c][ix] > 5: report += printtree(lopd[c][ix], prefix=newprefix) left = True if ropd[c][ix] > 5: if left: report += f"\n{newprefix}" report += printtree(ropd[c][ix], prefix=newprefix) break if not prefix: report += "\n" return report maxmoves = 32 for moves in range(2,maxmoves+1): fresh = [] isfresh = {} newoper = [] newlopd = [] newropd = [] print(f"Generating complexity {moves}...") for lmoves in range(1,moves//2+1): for mm in reva[lmoves]: for nn in reva[moves-lmoves]: big = nn; lil = mm; if (nn < mm): big = mm; lil = nn for op in ops: for ordr in range(0, 2 if trybothorders[op] else 1): if ordr: (m,n) = (lil,big) else: (m,n) = (big,lil) candidate = ops[op](m,n) if candidate <= 0: continue if ignore > 0 and candidate > ignore: continue if candidate in known: continue fix = -1 if candidate in isfresh: fix = isfresh[candidate] if op >= newoper[fix]: continue if fix < 0: isfresh[candidate] = len(fresh) fresh.append(candidate) newoper.append(op) newlopd.append(m) newropd.append(n) else: newoper[fix] = op newlopd[fix] = m newropd[fix] = n fmin = fresh[0] fmax = fresh[0] for ix in range(0, len(fresh)): if fresh[ix] < fmin: fmin = fresh[ix] elif fresh[ix] > fmax: fmax = fresh[ix] print(f"Added {len(fresh)} values from {fmin} ln/n {math.log(fmin)/moves} to {fmax} ln/n {math.log(fmax)/moves}.") fmed = fresh[len(fresh)//2] # not actually median print(f" Fresh middle {fmed} ln {math.log(fmed)} ln/n {math.log(fmed)/moves}") reva.append(fresh) lopd.append(newlopd) ropd.append(newropd) oper.append(newoper) for k in fresh: known[k] = moves # print data print([known[i] for i in range(1,79)]) # print annotated data for n in range(2,101): print(printtree(n)) # print b-file n = 1 limit = 10001 while n in known and n < limit: print(f"{n} {known[n]}") n += 1