1
$\begingroup$

Say I have a series of real numbers of arbitrary precision. It is a known fact that the real numbers will eventually result in a pure integer (not rounded)

What would be the most efficient way to predict how many steps to the next integer.

for example in the following series it is simple to determine the next integer value.

2.1, 4.2, 6.3 ...

0.1 divides into 1 10 times therefore the next integer in the series comes after the 10th iteration.

But what if the numbers are not so easy for example in the series...

378.0872915, 496.4625614, 591.2874514, 672.6574576, 745.0246992

The integer number arrives after the 11th iteration and is 1126 but how could I predict that?

example 2 in the series

277.9712215, 382.2844896, 463.3471822, 531.9682234, 592.5199075

The next integer doesn't arrive till the 3234th iteration and is 12120

How could I have predicted that with the least possible number of steps?

It is ok for the prediction to be wrong as we could move to the predicted number in series, test, re-calibrate and try again until the answer is found.

EDIT: I didn't want to add this as I think its an unnecessary diversion and I might start getting answers like 'factor it' The number sequence is generated using this equation $$sqrt(x^2+bx+c)-x$$ the first real number in the series is when $x = 0$

EDIT 2:

As can be seen from the responses below as soon as I added Edit 1 I have started to get the inevitable 'Factor it' responses. I am looking for a way to predict the next possible integer value. I do not expect the prediction to be correct the first time around, I do hope it can be resolved by an iterative approach to the predictions.

Edit 3: The following image shows a graph of the series. the shape of the graph is always the same although of course the actual numbers are not.

graph of the number series

$\endgroup$
18
  • $\begingroup$ What's the reason for the second series to get at $1126$ after eleven iterations? Why not $1003$ after seventeen? $\endgroup$
    – egreg
    Dec 6 '15 at 22:58
  • $\begingroup$ Because 1003 is not in the series. The first 11 numbers are 378.0872915, 496.4625614, 591.2874514, 672.6574576, 745.0246992, 810.8216717, 871.5499986, 928.2138793, 981.5241281, 1032.0057637, 1080.0596314, 1126.0000000 $\endgroup$ Dec 6 '15 at 23:03
  • $\begingroup$ Who told you? I mean, what's the rule? $\endgroup$
    – egreg
    Dec 6 '15 at 23:05
  • $\begingroup$ See my edit in the original question. $\endgroup$ Dec 6 '15 at 23:13
  • 1
    $\begingroup$ That's not an "unnecessary diversion", it changes the question from completely hopeless to solvable. Write the equation as $x^2 + b x + c = y^2$ or $(x - b/2 - y)(x + b/2 - y) = b^2/4 - c$. Assuming $b$ is an even integer and $c$ is an integer, you look at factors of $b^2/4 - c$... $\endgroup$ Dec 6 '15 at 23:35
1
$\begingroup$

We can add $x$ and square each term, following which the sequence is a quadratic polynomial in $x$.

$378.0872915, 496.4625614, 591.2874514, 672.6574576, 745.0246992\dots$

Adding $x$, we get,

$378.0872915, 497.4625614, 593.2874514, 675.6574576, 749.0246992\dots$

Squaring, we get,

$142950, 247469, 351990, 456513, 561038\dots$

It is not difficult to solve systems of equations or use Lagrange interpolation to get the quadratic:

$x^2+104518x+142950$

For a term to be an integer, we need to solve the Diophantine equation:

$x^2+104518x+142950=y^2$

To reduce the number of terms, let's try to complete the square:

$(x+52259)^2-2730860131=y^2$ or $y^2-(x+52259)^2=-2730860131$

By factoring $-2730860131$ into $2$ factors of the same parity, we can find integer solutions to this, the $2$ factors being $y+(x+52259)$ and $y-(x+52259)$.

If the $x$ coefficient is odd, say the equation was,

$x^2+104517x+142950=y^2$

We can complete the square again:

$(x+52258.5)^2-2730807872.25=y^2$ or $y^2-(x+52258.5)^2=-2730807872.25$

Multiplying both sides by $4$, we get:

$(2y)^2-(2x+104517)^2=-10923231489$

We need to find $2$ odd factors of $-10923231489$ to be $2y+(2x+104517)$ and $2y-(2x+104517)$.

To answer your question if it is possible to do without factoring, suppose you find the solution with an alternative method. Then we can take out the quadratic and plug $x$ in.

As such, we can find $y$ by taking the square root.

As such, we would have found the factors of some big number, which is expressed in terms of $x$ and $y$ ($y+(x+52259)$ and $y-(x+52259)$ or $2y+(2x+104517)$ and $2y-(2x+104517)$), which are both obtainable. So, if you find the solution, it means you have somehow factored the number.

$\endgroup$
4
  • $\begingroup$ I don't understand the part where you say "So, if you find the solution, it means you have somehow factored the number." But to find the solution you are expousing factoring. $\endgroup$ Dec 7 '15 at 0:06
  • $\begingroup$ Edited: "with an alternative method". $\endgroup$
    – Element118
    Dec 7 '15 at 0:12
  • $\begingroup$ An alternative method is what I am trying to develop. $\endgroup$ Dec 7 '15 at 0:21
  • $\begingroup$ This assumes an alternative method exists, and by using it, we can obtain a factorisation. $\endgroup$
    – Element118
    Dec 7 '15 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.