21
\$\begingroup\$

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 , so shortest answer in bytes wins.

Improve this question
\$\endgroup\$
0

17 Answers 17

Reset to default
18
\$\begingroup\$

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({\left\lceil \frac{1-k^2}{2k} \right\rceil}^2+1, {\left\lceil \frac{1+k^2}{2k} \right\rceil}^2-1\right)\$.

Improve this answer
\$\endgroup\$
8
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 16 bytes

nD(‚>I·/înTS·<-ß

Port of @alephalpha's Mathematica answer, with inspiration from @Sok's Pyth answer, so make sure to upvote both of them!

Try it online or verify all test cases.

Explanation:

n # Take the square of the (implicit) input # i.e. 0.05 → 0.0025 D(‚ # Pair it with its negative # i.e. 0.0025 → [0.0025,-0.0025] > # Increment both by 1 # i.e. [0.0025,-0.0025] → [1.0025,0.9975] I· # Push the input doubled # i.e. 0.05 → 0.1 / # Divide both numbers with this doubled input # i.e. [1.0025,0.9975] / 0.1 → [10.025,9.975] î # Round both up # i.e. [10.025,9.975] → [11.0,10.0] n # Take the square of those # i.e. [11.0,10.0] → [121.0,100.0] TS # Push [1,0] · # Double both to [2,0] < # Decrease both by 1 to [1,-1] - # Decrease the earlier numbers by this # i.e. [121.0,100.0] - [1,-1] → [120.0,101.0] ß # Pop and push the minimum of the two # i.e. [120.0,101.0] → 101.0 # (which is output implicitly)
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Neat, thanks for linking the answer that has the formula used. I was doing mental gymnastics trying to figure out the formula from 05AB1E's ever-odd syntax. \$\endgroup\$ Commented Feb 26, 2019 at 15:40
3
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Japt, 18 16 bytes

-2 bytes from Shaggy

_=¬u1)©U>½-½aZ}a

Try it online!

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Might be shorter using Arnauld's solution \$\endgroup\$ Commented Feb 26, 2019 at 4:11
  • \$\begingroup\$ A little shuffling saves a byte. \$\endgroup\$ Commented Feb 26, 2019 at 11:57
  • \$\begingroup\$ Oh... of course i could have reversed that :|. Also that %1 && is nasty, not sure if using Arnauld's solution would be shorter (maybe not) \$\endgroup\$ Commented Feb 26, 2019 at 11:59
  • \$\begingroup\$ 16 bytes by reassigning Z¬u1 to Z at the beginning of the function. \$\endgroup\$ Commented Feb 26, 2019 at 12:00
  • \$\begingroup\$ The other method appears to be 26: [1,-1]®*U²Ä /U/2 c ²-Z} rm \$\endgroup\$ Commented Feb 27, 2019 at 0:18
3
\$\begingroup\$

Pyth, 22 21 bytes

hSm-^.Ech*d^Q2yQ2d_B1

Try it online here, or verify all the test cases at once here.

Another port of alephalpha's excellent answer, make sure to give them an upvote!

hSm-^.Ech*d^Q2yQ2d_B1 Implicit: Q=eval(input()) _B1 [1,-1] m Map each element of the above, as d, using: ^Q2 Q^2 *d Multiply by d h Increment c yQ Divide by (2 * Q) .E Round up ^ 2 Square - d Subtract d S Sort h Take first element, implicit print

Edit: Saved a byte, thanks to Kevin Cruijssen

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I don't know Pyth, but is it possible to create [-1,1] in 3 bytes as well, or do you need an additional reverse so it becomes 4 bytes? If it's possible in 3 bytes, you could do that, and then change the *_d to *d and the +d to -d. Also, does Pyth not have a Minimum builtin, instead of sort & take first? \$\endgroup\$ Commented Feb 26, 2019 at 13:58
  • 1
    \$\begingroup\$ @KevinCruijssen The order of the two elements isn't important as we're taking the minimum, though I can't think of a way of creating the pair in 3 bytes. A good catch on changing it to - ... d though, that saves me a byte! Thanks \$\endgroup\$ Commented Feb 26, 2019 at 14:30
  • \$\begingroup\$ @KevinCruijssen Also there isn't a single byte minimum or maximum function unfortunately :o( \$\endgroup\$ Commented Feb 26, 2019 at 14:31
  • 1
    \$\begingroup\$ Ah, of course. You map over the values, so it doesn't matter if it's [1,-1] or [-1,1]. I was comparing the *d and -d with my 05AB1E answer, where I don't use a map, but can subtract/multiply a 2D array from/with another 2D array, so I don't need a map. Glad I could help to save a byte in that case. :) And thanks for the inspiration for my 05AB1E answer. \$\endgroup\$ Commented Feb 26, 2019 at 14:39
3
\$\begingroup\$

Perl 6, 34 33 29 bytes

-1 byte thanks to Grimy

{+(1...$_>*.sqrt*(1|-1)%1>0)}

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ -1 byte by replacing >= with >. Square roots of integers are either integer or irrational, so the equality case provably cannot happen. \$\endgroup\$ Commented Feb 26, 2019 at 13:03
  • 1
    \$\begingroup\$ @Grimy Thanks, this seems to be allowed according to the challenge rules. (Though floating-point numbers are always rational, of course.) \$\endgroup\$ Commented Feb 26, 2019 at 13:16
2
\$\begingroup\$

APL (Dyalog Unicode), 27 bytesSBCS

⌊/0~⍨¯1 1+2*⍨∘⌈+⍨÷⍨1(+,-)×⍨

Try it online!

Monadic train taking one argument. This is a port of alephalpha's answer.

How:

⌊/0~⍨¯1 1+2*⍨∘⌈+⍨÷⍨1(+,-)×⍨ ⍝ Monadic train ×⍨ ⍝ Square of the argument 1(+,-) ⍝ 1 ± that (returns 1+k^2, 1-k^2) ÷⍨ ⍝ divided by +⍨ ⍝ twice the argument ∘⌈ ⍝ Ceiling 2*⍨ ⍝ Squared ¯1 1+ ⍝ -1 to the first, +1 to the second 0~⍨ ⍝ Removing the zeroes ⌊/ ⍝ Return the smallest
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

k=>{double n=2,p;for(;!((p=Math.Sqrt(n)%1)>0&p<k|1-p<k);n++);return n;}

Try it online!

-4 bytes thanks to Kevin Cruijssen!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ You can save a byte by putting the n++ in the loop, so the -1 can be removed from the return: k=>{double n=1,p;for(;Math.Abs(Math.Round(p=Math.Sqrt(0d+n))-p)>k|p%1==0;n++);return n;} \$\endgroup\$ Commented Feb 26, 2019 at 12:39
  • \$\begingroup\$ Also, the 0d+ can be removed, can it not? \$\endgroup\$ Commented Feb 26, 2019 at 12:59
  • \$\begingroup\$ @KevinCruijssen Yes it can, I just forgot the n was already a double \$\endgroup\$ Commented Feb 26, 2019 at 15:56
2
\$\begingroup\$

Java (JDK), 73 70 bytes

k->{double i=1,j;for(;(j=Math.sqrt(++i)%1)==0|j>=k&1-j>=k;);return i;}

Try it online!

-3 bytes thanks to @ceilingcat

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Java 8, 85 bytes

n->{double i=1,p;for(;Math.abs(Math.round(p=Math.sqrt(i))-p)>n|p%1==0;i++);return i;}

Port of EmbodimentOfIgnorance's C# .NET answer.

Try it online.

The Math.round can alternatively be this, but unfortunately it's the same byte-count:

n->{double i=1,p;for(;Math.abs((int)((p=Math.sqrt(i))+.5)-p)>n|p%1==0;i++);return i;}

Try it online.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

MathGolf, 16 bytes

²_b*α)½╠ü²1bαm,╓

Try it online!

Not a huge fan of this solution. It is a port of the 05AB1E solution, which is based on the same formula most answers are using.

Explanation

² pop a : push(a*a) _ duplicate TOS b push -1 * pop a, b : push(a*b) α wrap last two elements in array ) increment ½ halve ╠ pop a, b, push b/a ü ceiling with implicit map ² pop a : push(a*a) 1 push 1 b push -1 α wrap last two elements in array m explicit map , pop a, b, push b-a ╓ min of list
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Is every symbol considered a byte in code golfing? Because some of your characters require more than a single byte. I don't mean to nit-pick, I'm genuinely wondering :) \$\endgroup\$ Commented Feb 27, 2019 at 12:05
  • 1
    \$\begingroup\$ Good question! A "byte" in golfing relates to the minimum file size required to store a program. The text used to visualize those bytes can be any bytes. I have chosen Code Page 437 to visualize my scripts, but the important part is the actual bytes that define the source code. \$\endgroup\$ Commented Feb 27, 2019 at 13:07
  • 1
    \$\begingroup\$ A good example of the number of characters and number of bytes being different is this answer. Here, the 'ԓ' character is actually 2 bytes, but the rest are 1 byte characters. \$\endgroup\$ Commented Feb 27, 2019 at 13:08
1
\$\begingroup\$

Forth (gforth), 76 bytes

: f 1 begin 1+ dup s>f fsqrt fdup fround f- fabs fdup f0> fover f< * until ;

Try it online!

Explanation

Starts a counter at 1 and Increments it in a loop. Each iteration it checks if the absolute value of the counter's square root - the closest integer is less than k

Code Explanation

: f \ start a new word definition 1 \ place a counter on the stack, start it at 1 begin \ start and indefinite loop 1+ \ add 1 to the counter dup s>f \ convert a copy of the counter to a float fsqrt \ get the square root of the counter fdup fround f- \ get the difference between the square root and the next closes integer fabs fdup \ get the absolute value of the result and duplicate f0> \ check if the result is greater than 0 (not perfect square) fover f< \ bring k to the top of the float stack and check if the sqrt is less than k * \ multiply the two results (shorter "and" in this case) until \ end loop if result ("and" of both conditions) is true ; \ end word definition
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 13 bytes

I have not managed to get anything terser than the same approach as alephalpha
- go upvote his Mathematica answer!

²;N$‘÷ḤĊ²_Ø+Ṃ

Try it online!

How?

²;N$‘÷ḤĊ²_Ø+Ṃ - Link: number, n (in (0,1)) ² - square n -> n² $ - last two links as a monad: N - negate -> -(n²) ; - concatenate -> [n², -(n²)] ‘ - increment -> [1+n², 1-(n²)] Ḥ - double n -> 2n ÷ - divide -> [(1+n²)/n/2, (1-(n²))/n/2] Ċ - ceiling -> [⌈(1+n²)/n/2⌉, ⌈(1-(n²))/n/2⌉] ² - square -> [⌈(1+n²)/n/2⌉², ⌈(1-(n²))/n/2⌉²] Ø+ - literal -> [1,-1] _ - subtract -> [⌈(1+n²)/n/2⌉²-1, ⌈(1-(n²))/n/2⌉²+1] Ṃ - minimum -> min(⌈(1+n²)/n/2⌉²-1, ⌈(1-(n²))/n/2⌉²+1)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt, 14 bytes

_=¬aZ¬r¹©U¨Z}a

Try it

_=¬aZ¬r¹©U¨Z}a :Implicit input of integer U _ :Function taking an integer Z as an argument = : Reassign to Z ¬ : Square root of Z a : Absolute difference with Z¬ : Square root of Z r : Round to the nearest integer ¹ : End reassignment © : Logical AND with U¨Z : U greater than or equal to Z } :End function a :Return the first integer that returns true when passed through that function
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl 5 -p, 42 bytes

$t=sqrt++$\while($p=abs$t-int$t)>$_||!$p}{

Try it online!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.