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|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)