6
$\begingroup$

Suppose I had $n = a + \sqrt{b}$ as a decimal of arbitrary precision, but didn't know $a$ or $b$, except that they are positive integers.

If I had just $\sqrt{b}$, I could just square it and end up with something very close to an integer, so I'd have $b$.

If I take $n^2 - 2an$, I get $(a^2 + b + 2a\sqrt{b}) - (2a^2 + 2a\sqrt{b}) = b - a^2$ which will be an integer, but I don't have $a$...

Is there some way to take the sum of the integral and decimal portion of $n$ and do some integer voodoo there?

Thanks for any ideas.

  • 2
    What about $n = 3 = 2 + \sqrt{1} = 1 + \sqrt{4}$? Do you assume that $b$ is not a square?2012-11-26

4 Answers 4

7

You can calculate its continued fraction. Being a quadratic irrational, its continued fraction will be periodic. Once you have the period, you can work out $a$ and $b$ exactly.

EDIT: Probably a better method is to calculate the square of your number and then use an algorithm like PSLQ to look for a vanishing integer-linear combination of $1$, the number, and its square.

  • 1
    since a,b are positive integers the continued fraction will have period < 2n.2012-11-26
1

Using that $\sqrt{b}=\lfloor\sqrt{b}\rfloor+\{\sqrt{b}\}$, we get that $\{\sqrt{b}\}$ satisfies the following: $\{\sqrt{b}\}^2+2\{\sqrt{b}\}\lfloor\sqrt{b}\rfloor+\lfloor\sqrt{b}\rfloor^2=b$ and in particular it satisfies a relation of the form $\{\sqrt{b}\}^2+m\{\sqrt{b}\}=k$ for some positive integers $m,k$ (you can just check all $m$ up to $2n$ to find the solution). By irrationality of $\sqrt{b}$ (if it's not irrational, then the problem is unsolvable anyway), there is only one solution and once you have it, $\lfloor\sqrt{b}\rfloor$ must be $\frac{m}{2}$ and $k$'ll be $b-\lfloor\sqrt{b}\rfloor^2$, so $b$'ll be $k+\frac{m^2}{4}$.

0

Clearly $a \leq n$ and $b \leq n^2$ so you have only got finitely many possibilities to try. Compute the value of $x+\sqrt{y}$ to 100 decimals (say) for all positive integers $x,y$ such that $x\leq n$ and $y \leq n^2$. (You only need an upper bound for $n$ and $n^2$ here.) Also compute $n$ to 100 decimals. If you are lucky there is now only one combination of $x,y$ such that $x+\sqrt{y}$ could be equal to $n$. Then $a=x$ and $b=y$. Otherwise you double the number of digits you compute. Repeat as long as necessary.

0

Assuming that the integer part of $n$ is $N$, then you need to try the following

for $k=1$ to $N$

store smallest fractional part of ${(N-k)}^2$

(note if the smallest fractional part is $>0$ for example, $0.001$, then you would store that, and if it is close to $1$, for example, $0.998$, you would store $1-0.998=0.002$)

The $k$ that gave you the smallest value is your $a$.