Given a decimal number k, find the smallest integer n such that the square root of n is within k of an integer. However, the distance should be nonzero - n cannot be a perfect square.

Given k, a decimal number or a fraction (whichever is easier for you), such that 0 < k < 1, output the smallest positive integer n such that the difference between the square root of n and the closest integer to the square root of n is less than or equal to k but nonzero.

If i is the closest integer to the square root of n, you are looking for the first n where 0 < |i - sqrt(n)| <= k.

Rules

• You cannot use a language's insufficient implementation of non-integer numbers to trivialize the problem.


• Otherwise, you can assume that k will not cause problems with, for example, floating point rounding.

Test Cases

.9         > 2

.5         > 2

.4         > 3

.3         > 3

.25        > 5

.2         > 8

.1         > 26

.05        > 101

.03        > 288

.01        > 2501

.005       > 10001

.003       > 27888

.001       > 250001

.0005      > 1000001

.0003      > 2778888

.0001      > 25000001

.0314159   > 255

.00314159  > 25599

.000314159 > 2534463

Comma separated test case inputs:

0.9, 0.5, 0.4, 0.3, 0.25, 0.2, 0.1, 0.05, 0.03, 0.01, 0.005, 0.003, 0.001, 0.0005, 0.0003, 0.0001, 0.0314159, 0.00314159, 0.000314159

This is code-golf, so shortest answer in bytes wins.

Wolfram Language (Mathematica), 34 bytes

Min[⌈.5/#+{-#,#}/2⌉^2+{1,-1}]&

Try it online!

Explanation

The result must be of the form $m^2 pm 1$ for some $m in mathbb{N}$. Solving the inequations $sqrt{m^2+1} - m le k$ and $m - sqrt{m^2-1} le k$, we get $m ge frac{1-k^2}{2k}$ and $m ge frac{1+k^2}{2k}$ respectively. So the result is $operatorname{min}left({leftlceil frac{1-k^2}{2k} rightrceil}^2+1, {leftlceil frac{1+k^2}{2k} rightrceil}^2-1right)$.

JavaScript (ES7),  51  50 bytes

f=(k,n)=>!(d=(s=n**.5)+~(s-.5))|d*d>k*k?f(k,-~n):n

Try it online!

(fails for the test cases that require too much recursion)

Non-recursive version,  57  56 bytes

k=>{for(n=1;!(d=(s=++n**.5)+~(s-.5))|d*d>k*k;);return n}

Try it online!

Or for 55 bytes:

k=>eval(`for(n=1;!(d=(s=++n**.5)+~(s-.5))|d*d>k*k;);n`)

Try it online!

(but this one is significantly slower)

J, 39 29 bytes

[:<./_1 1++:*:@>.@%~1+(,-)@*:

NB. This shorter version simply uses @alephalpha's formula.

Try it online!

39 bytes, original, brute force

2(>:@])^:((<+.0=])(<.-.)@(-<.)@%:)^:_~]

Try it online!

Handles all test cases

Japt, 18 bytes

_¬%1©U>½-Z¬u1 a½}a

Try it online!

Python, 42 bytes

lambda k:((k-1/k)//2)**2+1-2*(k<1/k%2<2-k)

Try it online!

Based on alephalpha's formula, explicitly checking if we're in the $m^2-1$ or $m^2+1$ case via the condition k<1/k%2<2-k.

Python 3.8 can save a byte with an inline assignment.

Python 3.8, 41 bytes

lambda k:((a:=k-1/k)//2)**2-1+2*(a/2%1<k)

Try it online!

These beat my recursive solution:

50 bytes

f=lambda k,x=1:k>.5-abs(x**.5%1-.5)>0 or-~f(k,x+1)

Try it online!

C# (Visual C# Interactive Compiler), 89 bytes

k=>{double n=1,p;for(;Math.Abs(Math.Round(p=Math.Sqrt(0d+n++))-p)>k|p%1==0;);return n-1;}

Try it online!