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.

$\endgroup$
4
  • $\begingroup$ What does it mean to know something "as a decimal of arbitrary precision"? $\endgroup$ Nov 26 '12 at 11:27
  • $\begingroup$ Just that I can acquire it, perhaps through Newton's method, to any place value. For example 5+sqrt(3) = 6.7320508.... and I can keep going. $\endgroup$
    – Dan
    Nov 26 '12 at 11:29
  • $\begingroup$ Could you give us an explicit $n$ that you have in mind? $\endgroup$
    – lhf
    Nov 26 '12 at 11:58
  • 2
    $\begingroup$ What about $n = 3 = 2 + \sqrt{1} = 1 + \sqrt{4}$? Do you assume that $b$ is not a square? $\endgroup$
    – huon
    Nov 26 '12 at 15:03
7
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ How exactly do you know when you have the period? $\endgroup$ Nov 26 '12 at 11:32
  • 1
    $\begingroup$ When you see a repetition, you assume you have the period, you calculate $a$ and $b$ based on this assumption, then you check to see whether you were right by computing a few hundred more decimal places. Look, the problem is clearly not a terribly practical one, we have to make some assumptions to make a go of it. $\endgroup$ Nov 26 '12 at 11:37
  • $\begingroup$ Is this a special solution? Or would it work for other powers and more complex combinations, a/b + c*d^e etc? $\endgroup$
    – Dan
    Nov 26 '12 at 11:39
  • 1
    $\begingroup$ Yes, the Inverse Symbolic Calculator is essentially an algorithm for finding these integer-linear combinations, supplemented with some table look-up. $\endgroup$ Nov 26 '12 at 11:55
  • 1
    $\begingroup$ since a,b are positive integers the continued fraction will have period $< 2n$. $\endgroup$
    – user50336
    Nov 26 '12 at 14:03
1
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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$.

$\endgroup$

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.