$x$ is fixed in $[0,1]$, $a_n,b_n,c_n$ are integers and not all of them are $0$
$y(a_n,b_n,c_n) = a_n x^3 + b_n x^2 + c_n x = Y_n$
Find an algorithm to go from $(a_n,b_n,c_n)$ to $(a_{n+1},b_{n+1},c_{n+1})$ where $Y_{n+1}$ is closer to an integer than $Y_n$
Preferably the algorithm would approximate extremely quickly with small coefficients(I believe I can prove that an optimal sequence exists in this sense)
The first thing that was suggested to me over IRC(#math on freenode) by muboto is to use continued fractions and the extended euclidean algorithm to find $n$ such that $np + mq = 1$ for the $p,q$ from the continued fraction. This doesn't seem to zoom very fast though(linear with the size of parameters if I judged it right).
I conjecture that it should be able to grow at least with the parameters to the third or fourth.
I have some data supporting it here
a,b, c,distance from an integer
5,1,-2,-0.00166826
5,5,-3,-0.0141376
5,6,-5,0.0111764
5,10,-6,-0.00129289
6,-9,-5,-0.000821762
6,-2,1,-0.0056958
6,0,-9,-0.000446392
6,3,-2,0.00714886
6,7,-3,-0.00532043
6,9,-13,-7.10226e-005
7,-19,-8,2.47379e-005
7,-10,-12,0.000400108
7,0,1,0.00312132
7,9,-3,0.00349669
8,-3,4,-0.000906223
8,6,0,-0.000530853
8,15,-4,-0.000155483
9,-13,1,-5.97227e-005
9,-4,-3,0.000315647
9,5,-7,0.000691017
11,-16,-30,3.81759e-005
11,-7,10,-0.000144183
11,2,6,0.000231186
11,11,2,0.000606556
13,-10,-21,-4.62847e-005
14,15,-13,-0.000601875
15,-4,-12,-0.000130745
15,5,-16,0.000244624
17,2,-3,-0.000215206
17,11,-7,0.000160164
17,295,17,-1.31322e-008
18,45,-3,-2.00573e-005
19,17,2,7.57032e-005
20,-29,-29,-2.15467e-005
20,-11,7,0.000171464
20,-2,47,-1.08954e-005
20,25,123,-2.44102e-007
21,23,11,-8.75739e-006
22,-5,16,8.70032e-005
22,48,-25,-6.61936e-006
23,-24,61,4.04531e-007
23,20,-20,8.91412e-005
24,1,25,2.54256e-006
25,26,-11,4.68059e-006
25,123,-133,-2.05265e-007
26,-73,-1,1.05316e-006
26,51,-47,6.81862e-006
27,-48,-37,3.1912e-006
27,-21,39,1.38425e-005
28,-147,-27,-4.36235e-007
28,4,3,1.59805e-005
29,29,-33,1.81186e-005
31,-196,-89,2.12398e-007
31,-18,17,2.72805e-005
31,35,-24,-6.6342e-005
32,7,-19,2.94185e-005
33,-12,26,-5.71801e-005
34,13,-10,-5.50421e-005
39,-368,-239,2.02658e-008
43,1,184,1.60429e-007
45,148,-10,-4.49367e-007
46,49,0,-4.0768e-006
47,74,-36,-1.93877e-006
48,-25,-26,-5.56619e-006
48,2,50,5.08512e-006
48,99,-72,1.99266e-007
49,27,14,7.22316e-006
50,52,-22,9.36119e-006
51,-171,34,-3.17039e-008
56,-73,-222,7.1336e-009
56,983,-205,-5.59139e-010
68,124,51,-4.48362e-008
70,50,25,-1.53423e-006
71,75,-11,6.03797e-007
72,-24,-1,-3.02363e-006
73,-834,-222,1.69412e-009
73,1,-37,-8.85602e-007
73,222,-205,-5.99863e-009
74,26,-73,1.25243e-006
94,51,50,1.00833e-006
96,-23,24,-4.81071e-007
97,2,-12,1.65696e-006
99,-72,-38,1.67562e-007
107,-244,-188,-2.45703e-008
116,223,-21,1.5443e-007
119,-47,85,-7.65401e-008
121,100,-109,-6.86336e-007
124,51,-171,-3.77026e-008
129,149,-427,1.13498e-009
142,-71,146,3.27991e-007
144,76,-48,-2.81805e-007
146,-612,-427,-4.30451e-009
146,444,-410,-1.19973e-008
147,27,-110,3.66828e-007
167,52,13,1.22726e-007
185,1132,-632,5.75837e-010
192,175,-120,-8.25387e-008
218,-119,47,9.1022e-008
225,-20,576,2.14704e-010
235,176,64,7.78898e-008
238,-94,170,-1.5308e-007
240,274,-192,1.16727e-007
243,4,-86,-1.14243e-007
281,-93,354,7.34831e-009
281,963,371,-3.44435e-010
286,5,98,4.61858e-008
291,103,-158,8.50234e-008
298,202,371,-5.78392e-009
332,-264,388,-2.43556e-008
337,-166,132,1.44819e-008
354,129,149,1.34968e-009
359,227,-107,4.01872e-008
388,-337,166,-1.7222e-008
405,-42,183,-3.03543e-008
410,56,-73,8.48328e-009
410,1112,-56,7.90541e-010
427,351,-56,-4.64894e-009
450,-40,1152,4.29409e-010
483,278,-278,2.48466e-009
500,573,-261,-1.06476e-008
506,943,947,-1.2973e-010
539,205,-500,9.61826e-009
556,500,-483,-3.51397e-009
579,109,725,1.56439e-009
612,427,-705,3.61963e-009
685,649,-910,-2.37899e-009
702,-1168,-927,-1.25738e-010
708,258,298,2.69936e-009
725,-503,298,-2.74012e-009
781,480,93,-3.29926e-009
837,407,-129,3.83434e-009
854,-354,-129,-1.60515e-009
910,629,-334,-2.16429e-009
927,-1188,-351,8.89665e-011
983,-205,-556,-4.70173e-010
1039,778,-761,-1.02931e-009
1079,-374,447,-1.39044e-009
1112,-56,-983,6.64803e-010
1168,927,-1188,1.05664e-010
1208,-225,20,-2.55468e-010
1264,758,-185,-8.14607e-010
1393,907,-612,3.20369e-010
1433,-245,596,-4.07636e-011
EDIT: I implememnted mobuto's solution in python as follows and the results obviously are inverse linear in terms of the parameters
from fractions import Fraction
x = 0.5**.25
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
def findpq(x, i):
tmp = Fraction(x).limit_denominator(100*i**2+1)
return tmp.numerator,tmp.denominator
def f(a,b,c):
return a*x**3 + b*x**2 + c*x
def nextabc(a,b,c,i):
p,q = findpq(x*x*x,i)
gcd, x1, y = egcd(p, q)
p,q = findpq(x*x,i)
gcd, x2, y = egcd(p,q)
p,q = findpq(x,i)
gcd, x3, y = egcd(p,q)
return (int(x1), int(x2), int(x3))
a=1
b=1
c=1
for i in range(100):
z = abs(f(a,b,c) - round(f(a,b,c)))
print(a,",",b,",",c)
print(z)
a,b,c = nextabc(a,b,c,i)
The PSLQ algorithm you can determine a,b,c to an arbitrary tolerance. I implemented this in python as follows
This will always converge to a set of numbers because PSLQ converges if the solution with the given tolerances exist and by Dirichlet's simultaneous approximation theorem the solution of $|ax^3 + bx^2 + cx + d| < n^{-3}$ in terms of $a,b,c$ exists for all x with $\max(a,b,c) \le n$. My implementation generates a csv file where the maximum $n$ the $a,b,c$ works for and the distance of $ax^3 + bx^2 + cx$ from an integer.
This doesn't give a nice form for them, but it is an algorithm to construct them which is all that was needed for the question.