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

\$\endgroup\$

15 Answers 15

16
\$\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)\$.

\$\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!

\$\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)
\$\endgroup\$
  • \$\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\$ – Magic Octopus Urn Feb 26 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)

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

\$\endgroup\$
3
\$\begingroup\$

Japt, 18 16 bytes

-2 bytes from Shaggy

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Might be shorter using Arnauld's solution \$\endgroup\$ – ASCII-only Feb 26 at 4:11
  • \$\begingroup\$ A little shuffling saves a byte. \$\endgroup\$ – Shaggy Feb 26 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\$ – ASCII-only Feb 26 at 11:59
  • \$\begingroup\$ 16 bytes by reassigning Z¬u1 to Z at the beginning of the function. \$\endgroup\$ – Shaggy Feb 26 at 12:00
  • \$\begingroup\$ The other method appears to be 26: [1,-1]®*U²Ä /U/2 c ²-Z} rm \$\endgroup\$ – ASCII-only Feb 27 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

\$\endgroup\$
  • 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\$ – Kevin Cruijssen Feb 26 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\$ – Sok Feb 26 at 14:30
  • \$\begingroup\$ @KevinCruijssen Also there isn't a single byte minimum or maximum function unfortunately :o( \$\endgroup\$ – Sok Feb 26 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\$ – Kevin Cruijssen Feb 26 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!

\$\endgroup\$
  • \$\begingroup\$ -1 byte by replacing >= with >. Square roots of integers are either integer or irrational, so the equality case provably cannot happen. \$\endgroup\$ – Grimy Feb 26 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\$ – nwellnhof Feb 26 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
\$\endgroup\$
2
\$\begingroup\$

Java (JDK), 73 bytes

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

Try it online!

\$\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!

\$\endgroup\$
  • \$\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\$ – Kevin Cruijssen Feb 26 at 12:39
  • \$\begingroup\$ Also, the 0d+ can be removed, can it not? \$\endgroup\$ – Kevin Cruijssen Feb 26 at 12:59
  • \$\begingroup\$ @KevinCruijssen Yes it can, I just forgot the n was already a double \$\endgroup\$ – Embodiment of Ignorance Feb 26 at 15:56
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.

\$\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
\$\endgroup\$
  • \$\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\$ – schroffl Feb 27 at 12:05
  • \$\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\$ – maxb Feb 27 at 13:07
  • \$\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\$ – maxb Feb 27 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
\$\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) 
\$\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.