# Squares in the Squares

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.

# 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.

Explanation:

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
@Q2    Take square root of Q and print.


# MATL, 35 44.0 bytes

XKx@2^tVKVXf1=a~]VKVnQ0h)UXKX^t1\


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

i=input();d=o=9
while~-d:
n=i;d=o+1;o=i=0
while(n*d+i)**.5%1:i=-~i%d;d+=9*d*0**i
print'%d'%n**.5

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

# Python, 200198 178 bytes

import math
def r(i):
j=int(i**.5)+1
while str(j*j)[:len(str(i))]!=str(i):j+=1
return int(str(j*j)[len(str(i)):])
q=r(int(input()))
while math.sqrt(q)%1!=0:q=r(q)
print(q**.5)

• You could save a good number of bytes by shortening math.sqrt to m. – Arcturus Feb 1 '16 at 0:37
• @Ampora Aww yeah, saved 2 bytes – ThereGoesMySanity Feb 1 '16 at 0:48

# Brachylog, 26 bytes

{~a₀X√ℕ∧YcX∧Yh?∧Ybcℕ≜!}ⁱ√ℕ


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.

• (Thanks to a bug in the parser, that horrible mess of named variables and ∧s is actually shorter than using a sandwich.) – Unrelated String Jun 24 '19 at 6:49

# Perl 6, 101 bytes

my&q={$^k;$_=({++($||=$k.sqrt.Int)**2}.../^$k/)[*-1];+S/$k//}
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 +S/$k//
}

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.