I would like to find the highest number of the form $a + b\sqrt{2}$ less than a given value, where $a$ and $b$ are nonnegative integers. For example, if the value was $8.4$, then just trying all possible combinations less than $8.4$ would yield $a = 4$ and $ b = 3$, as $4+3\sqrt{2} = 8.243$, and no other values of $a$ and $b$ yield a value closer to $8.4$, but still less than $8.4$.
Asked
Active
Viewed 72 times
2
-
Why do you think there is any method other than brute force? – fleablood Feb 20 '19 at 19:16
-
Totally brute force for $a + b \sqrt{2} \le c$ would require checking $\lfloor c \rfloor \lfloor c/\sqrt{2} \rfloor \approx c^2/\sqrt{2}$ pairs $(a,b)$. But it's easy to do in $O(c)$. – Robert Israel Feb 20 '19 at 20:47
1 Answers
0
Since $a$ is an integer, we only need to find an integer $b$ such that the fractional part of $b\sqrt{2}$ is closest to the fractional part of $8.4$. Now it is easy to see that we obtain $b=3$, since we have the additional restriction that $b<8$. In general, the fractional part of $n\sqrt{2}$ is dense in $[0,1]$, for $n\in \Bbb N$.
Dietrich Burde
- 130,978