Solve 57|x^3 - 3y^3| < x for integers x and y.     [1]
--------------------------------------------------------

Interesting problem.

The positive left side requires that x is also positive.

Rearranging gives:

 |  x^3 - 3y^3  |
 | ------------ | < 1/57        ( 1/57 ~= 0.01754 )     [2]
 |      x       |

Minimizing the left side fraction can be done by minimizing
the numerator and/or maximizing the denominator.

The numerator is minimized when x^3 = 3y^3, which means
that x/y = 3^(1/3). 

(In the following I will denote 3^(1/3) (the cube root of 3)
by "r".)

Since r is irrational, x/y can never be = r. Defining the
error e = x/y - r, let's see what influence e has on the left
side of [2]:

 | {x^3 - 3y^3} / x | =
 | {x^3 - 3[x/(e+r)]^3} / x | =
 | { [1 - 3/(e+r)^3] * x^3 } / x | =
 | [1 - 3/(e+r)^3] * x^2 | =
 | [(e+r)^3 - 3]/[(e+r)^3] * x^2 | = 
 | [e^3 + 3e^2r + 3er^2]\[e^3 + 3e^2r + 3er^2 + 3] * x^2 |    [3]

with x and y significantly higher than 1, it is possible to
find a fraction x/y that gives an error e<<1. This enables us
to simplify [3] by ignoring the terms with higher powers of e:

 | [e^3 + 3e^2r + 3er^2]\[e^3 + 3e^2r + 3er^2 + 3] * x^2 | ~=
 | [3er^2]/[3] * x^2 | =
 | er^2 * x^2 |

assuming that the magnitude of x (and y) roughly corresponds
to the negative magnitude of e (the digits in x and y can be
used to generate a similar number of the digits of r), we see
that just maximizing x (the left denominator in [2]) is not 
going to minimize the left fraction.

We need a fraction x/y that by chance produces a lot more
digits of r than they have digits themselves.

After starting with a linear search for good approximations for
r and not even getting close to a solution, I therefore made a 
genetic algorithm that searched for fractions with low values of 
|x^3-3y^3|/x. It stored a number of the best fractions so far, 
and tried to find new ones by mutating (adding/subtracting small 
values to/from x and y, or multiplying x and y with a small number) 
and combining (adding/subtracting the xes and ys of two fractions 
to/from each other) fractions. Every now and then all but the very
best fractions were discarded, in order to avoid getting stuck 
with a set where all combinations or mutations would be worse than
the entire set itself.

This approach quickly got me closer to 1/57. However, not close
enough before I suffered from lack of precision in the standard 
long double floating point type in my c++ implementation.

I therefore implemented a new class to handle the basic operations
needed (addition, subtraction, multiplication and division by 
standard integers) on integers of arbitrary size. I let the program
run for a long while, and it slowly found better and better x/y 
combinations.

I have been working with the problem in breaks at work and running
the program in the background. After about 3 weeks and approximately
160 million new fractions, the solution appeared:

 x=19772597992797256813360849110398944123707421679471461
 y=13709553741508707869007784331326651892441479038865747

(and then also a solution to 141|x^3-3y^3|<x).

An interesting observation I came across while playing with this
problem is the patterns you get if you create a dot-plot of all
the fractions that are stored in the genetic algorithm: let the
x-axis be log(x) and the y-axis be log(e) (or use an approximation
E ~= e: E = e+e^2/r+e^3/r^5 = (x^3-3y^3)/(r^5*y^3) ).


Thanks,

 Trygve Flathen
 
 ---------------------------------------------------------------
 
 I computed solutions to:
 |x3 - 3y3| < x
  
 and got the following values:
  
 10=13^3-3*(9^3)
 51=75^3-3*(52^3)
 -587=949^3-3*(658^3)
 -10351=13361^3-3*(9264^3)
 37230=73011^3-3*(50623^3)
 -5624980=6193523^3-3*(4294349^3)
 -38489658=59472423^3-3*(41235875^3)
  
 Because I used 64 bits computation, the program overflowed for x>100000000
  
 It seems that x/|x^3-3*y^3| < 2, at least for x<100,000,000
  
 Does
 57 |x3 - 3y3| < x
 have a solution ?
  
JC

------------------------------------------------------------

Hi Ed.  Modulo any typos, here are my results.

x and y such that 57 abs(x^3-3 y^3)<x are given by

19772597992797256813360849110398944123707421679471461
and
13709553741508707869007784331326651892441479038865747

In the continued fraction expansion of 3^(1/3), large values (139, 249)
occur at positions 64 and 109.  So the 63rd and 108th convergents should
give particularly close values to 3^(1/3), or, after cubing, give x^3
fairly close to 3 y^3.  (relatively speaking, of course, as these values
and their differences get huge.)

The first of these gives x and y of

70640712374303774483336694754
and
48979534352883915272063169091

which is unfortunately only a solution of 32 abs(x^3-3 y^3)<x, but is
still worth noting.  The second convergent gives the desired solution
given at the beginning.

The continued fraction expansion of 3^(1/3) is

1,2,3,1,4,1,5,1,1,6,2,5,8,3,3,4,2,6,4,4,1,3,2,3,4,
1,4,9,1,8,4,3,1,3,2,6,1,6,1,3,1,1,1,1,12,3,1,3,1,1,
4,1,6,1,5,1,2,1,3,3,11,8,1,139,8,2,8,5,1,2,2,2,2,3,1,
1,2,1,1,1,52,2,46,2,2,3,3,1,5,1,6,1,6,1,1,1,6,1,20,10,
4,8,1,1,1,2,1,2,249,...

I suspect Mathematica has a function for continued fractions, so the
solution would take very little time.  I used DeriveXM, and spent 3 to 4
hours total.

Thanx.  Gary Mulkey

-----------------------------------------------------------
x=19772597992797256813360849110398944123707421679471461
y=13709553741508707869007784331326651892441479038865747

This is truncating the continued fraction expansion of 3^(1/3) when the next coefficient is 249
we can also find

x=20483870118197037889751255424678953987936154715153171838783
y=14202722288785984527207783859106186677688857756031157572204

where 141|x^3 - 3y^3| < x.

Richard Heylen 
---------------------------------------------------------------