Given input of a positive integer n, write a program that completes the following process.

  • Find the smallest positive integer greater than n that is a perfect square and is the concatenation of n and some other number. The order of the digits of n may not be changed. The number concatenated onto n to produce a perfect square may be called r_1.
  • If r_1 is not a perfect square, repeat the above process with r_1 as the new input to the process. Repeat until r_k is a perfect square, denoted s.
  • Print the value of sqrt(s).

Input can be taken in any format. You can assume that n is a positive integer. If any r_k has a leading zero (and r_k≠0), the zero can be ignored.

Test cases

Here are some test cases. The process demonstrates the above steps.

Input:   23
Process: 23, 2304, 4
Output:  2

Input:   10
Process: 10, 100, 0
Output:  0

Input:   1
Process: 1, 16, 6, 64, 4
Output:  2

Input:   5
Process: 5, 529, 29, 2916, 16
Output:  4

Input:   145
Process: 145, 145161, 161, 16129, 29, 2916, 16
Output:  4

Input:   1337
Process: 1337, 13373649, 3649, 36493681, 3681, 368102596, 2596, 25969216, 9216
Output:  96

This is code golf. Standard rules apply. The shortest answer (in bytes) wins.


7 Answers 7


Pyth, 26 bytes

LsI@b2 fy=sh.fys+QZ1\0)@Q2

Test suite

Output is as a float. If output as an int is desired, it would be 1 extra byte.


LsI@b2 fy=sh.fys+QZ1\0)s@Q2
                               Q = eval(input())
L                              def y(b): return
   @b2                         Square root of b
 sI                            Is an integer.
       f              )        Find the first positive integer T that satisfies
           h.f     1\0         Find the first digit string Z that satisfies
                +QZ            Concatenation of Q and Z
               s               Converted to an integer
              y                Is a pergect square.
          s                    Convert the string to an integer
         =                     Assign result to the next variable in the code, Q
        y                      Repeat until result is a perfect square
                               (The space) Discard return value
                        @Q2    Take square root of Q and print.

MATL, 35 44.0 bytes


Try it online!

XK        % implicit input: n. Copy to clipboard K
`         % do...while. Each iteration applies the algorithm
  `       %   do...while. Each iteration tests a candidate number
    x     %     delete top of stack
    @2^   %     iteration index squared
    t     %     duplicate
    V     %     convert to string                
    K     %     paste from clipboard K: n or r_k
    V     %     convert to string  
    Xf    %     find one string within another. Gives indices of starting matches, if any 
    1=a~  %     test if some of those indices is 1. If not: next iteration
  ]       %   end. We finish with a perfect square that begins with digits of n or r_k
  V       %   convert to string
  K       %   paste from clipboard K: n or r_k
  VnQ0h   %   index of rightmost characters, as determined by r_k
  )       %   keep those figures only
  U       %   convert to number. This is the new r_k
  XK      %   copy to clipboard K, to be used as input to algorithm again, if needed
  X^      %   square root
  1\      %   fractional part. If not zero: apply algorithm again
          % implitic do...while loop end
          % implicit display

Python 2, 98


Try it online.

  • \$\begingroup\$ Since we're in float abuse territory anyway... while x**.5%1: maybe? \$\endgroup\$
    – Sp3000
    Feb 1, 2016 at 13:18
  • \$\begingroup\$ @Sp3000 thanks! I've golfed it down a bit more now. \$\endgroup\$
    – grc
    Feb 1, 2016 at 13:49
  • \$\begingroup\$ @Ampora only the ideone link printed the process, but I've changed that now. \$\endgroup\$
    – grc
    Feb 1, 2016 at 13:49

Python, 200 198 178 bytes

import math
def r(i):
 while str(j*j)[:len(str(i))]!=str(i):j+=1
 return int(str(j*j)[len(str(i)):])
while math.sqrt(q)%1!=0:q=r(q)
  • \$\begingroup\$ You could save a good number of bytes by shortening math.sqrt to m. \$\endgroup\$
    – Arcturus
    Feb 1, 2016 at 0:37
  • \$\begingroup\$ @Ampora Aww yeah, saved 2 bytes \$\endgroup\$ Feb 1, 2016 at 0:48

Brachylog, 26 bytes


Try it online!

The last test case was omitted in the TIO link because it alone takes more than a minute to execute. I ran it on my laptop and the correct result was achieved in no more than two hours.

{                             The input
 ~a₀                          is a prefix of
    X√                        X, the square root of which
      ℕ                       is a whole number.
       ∧YcX                   Y concatenated is X.
           ∧Yh?               The input is the first element of Y.
               ∧Yb            The rest of Y,
                  c           concatenated,
                      }       is the output
                   ℕ          which is a whole number.
                    ≜         Make sure that it actually has a value,
                     !        and discard all choice points.
{                     }ⁱ      Keep feeding that predicate its own output until
                        √     its output's square root
                         ℕ    is a whole number
                              which is the output.

The second-to-last is necessary for when the initial input is already a perfect square, so the first perfect square which has it as a prefix is itself, and ! is necessary to make sure that backtracking iterates instead of finding a larger concatenated square, but I don't really know why is necessary, I just know that 5 produces a wrong answer without it.

  • \$\begingroup\$ (Thanks to a bug in the parser, that horrible mess of named variables and s is actually shorter than using a sandwich.) \$\endgroup\$ Jun 24, 2019 at 6:49

Perl 6, 101 bytes

put (q(get),&q...!(*.sqrt%1))[*-1].sqrt
my &q = {
  $^k; # declare placeholder parameter
  # set default scalar to:
  $_ = ( # a list
    # code block that generates every perfect square
    # larger than the input
    { ++( $ ||= $k.sqrt.Int )**2 }
    ...   # produce a sequence
    /^$k/ # ending when it finds one starting with the argument
  )[*-1]; # last value in sequence

  # take the last value and remove the argument
  # and turn it into a number to remove leading zeros

put (     # print the result of:
  q(get),     # find the first candidate
  &q          # find the rest of them
  ...         # produce a sequence
  !(*.sqrt%1) # ending with a perfect square
)[*-1]        # last value in sequence
.sqrt         # find the sqrt

ES7, 116 bytes

n=>{do{for(i=n;!(r=(''+Math.ceil((i*=10)**0.5)**2)).startsWith(+n););n=r.replace(+n,'');r=n**0.5}while(r%1);return r}

Yes, I could probably save a byte by using eval.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.