# Challenge

Write a program or function that takes a number $$\n\$$ and returns the smallest $$\k\$$ such that concatenation $$\n'k\$$ is a square. This sequence is described by A071176 on the OEIS.

# I/O Examples

input --> output

1   -->    6 (4^2)
10  -->    0 (10^2)
35  -->  344 (188^2)
164 -->  836 (406^2)
284 --> 2596 (1686^2)


# Rules

• Input will always be a positive decimal integer
• Output will be a positive decimal integer with no leading 0's or 0
• Standard I/O rules apply
• No standard loopholes
• This is , so shortest code in bytes wins
• I think your answer for 164 may be incorrect. Why 405^2 = 164025, making the answer 025, no? Commented Jan 17, 2020 at 21:21
• @Xcali I banged my head on the desk about that one too, but it's what oeis.org says is right. I believe the mathematical definition of concatenation doesn't allow for leading 0's... Commented Jan 17, 2020 at 21:30
• OK, then. It makes my code shorter to ignore the leading 0s anyway. Commented Jan 17, 2020 at 21:31
• Despite not being able to find a 'mathematical' definition of concatenation, it does certainly seem as if leading 0's aren't allowed. I'll update the question to clarify this. Commented Jan 17, 2020 at 22:43
• @640KB interesting that from that list 49 00, 64 00  and 81 00 are not allowed but 10 0 is. It seems 0 is allowed but a zero with additional leading zeros is not. Commented Jan 17, 2020 at 23:47

# 05AB1E, 7 bytes

∞<.Δ«Å²


# 05AB1E (legacy), 8 bytes

[N«Å²#}N


Alternative 8-byter which works in both 05AB1E versions (credit to @Grimmy):

[N«Å²iNq


Try it online (no test suite due to the program terminate q).

Explanation:

∞         # Push an infinite list in the range [1, ...]
<        # Decrease each by 1 to make the range [0, ...]
.Δ      # Find the first value which is truthy for:
«     #  Concat the value to the (implicit) input-integer
Å²   #  And check whether it is a square number
# (after which this found first value is output implicitly as result)

[         # Start an infinite loop:
N«       #  Concat the 0-based loop index to the (implicit) input-integer
Å²     #  If it's a square number:
#    #   Stop the infinite loop
}N        # After the infinite loop has stopped: push the last index
# (after which this found index is output implicitly as result)

[         # Start an infinite loop:
N«       #  Concat the 0-based loop index to the (implicit) input-integer
Å²i    #  If it's a square number:
N   #   Push the index again
q  #   And terminate the program
#   (after which this index is output implicitly as result)


The legacy version didn't had the ∞ builtin, and in the new version it isn't possible to push the last index N after a loop is terminated, which is why I decided to post both solutions.

• Modern 6 with Δ«Å²Nα. Commented Jan 17, 2020 at 12:40
• Actually my suggested 6 fails for 183673469387755102041 (yes this is the smallest counter-example I could find). Commented Jan 17, 2020 at 12:48
• @Grimmy I was actually trying to find a counter example where n concatted with n in the first iteration would be square, but my test program timed out. That's unfortunate, but still very original approach! Commented Jan 17, 2020 at 12:49
• @Grimmy: I'm not sure what your program does precisely, but it seems to me 13223140496 might be a smaller counterexample, as I expect an answer of 9685186064? Commented Jan 18, 2020 at 3:13
• @A.Rex Indeed, any number that is a square when concatenated to itself will be a counter-example. Those are fairly rare. Commented Jan 18, 2020 at 10:52

# Perl 6, 23 bytes

{(0...($_~*)**.5%%1)-1}  Try it online! ### Explanation { } # Anonymous codeblock (0... )-1 # Find the first number ($_~*)             # That when appended to the input
**.5         # Has a sqrt
%%1      # That is whole


# J, 27 21 bytes

(]+0<1|2%:,&.":)^:_&0


Try it online!

-6 bytes thanks to FrownyFrog

• ( )^:_ invoke the verb in parens continuously until it's output stops changing
• &0 set the right argument -- the one that will change each iteration -- to 0 (the left argument, the input, will remain fixed)

Now let's break down what's in the parens

• ]+ the right arg plus...
• 0< 0 or 1, depending on if 0 is less than...
• 1| the reminder when 1 divides...
• 2%: the square root of...
• ,&.": the left arg (original input) catted with , the right arg "under" &. stringification ":: ie, turn them both into strings, cat them, then convert back to an int

# JavaScript (ES7), 33 bytes

Takes input as a string.

f=(n,k=0)=>(n+k)**.5%1?f(n,k+1):k


Try it online!

# R, 45 bytes

n=scan();while((paste0(n,+F):1)^.5%%1)F=F+1;F


Try it online!

Throws a warning for each iteration noting that it only uses the first element of the vector as a loop condition. This will run out of space for large inputs since it constructs a vector of length $$\n'k\$$ at each iteration; this version will work for larger inputs and should be a bit faster, at a cost of 4 bytes.

• This doesn't seem to be working on the first two test cases. n=1 is returning 44, n=10 is returning 89. Commented Jan 20, 2020 at 19:07
• @ThomasMarkov if you're running them sequentially in a single session, the global variable F won't be reset properly. Commented Jan 20, 2020 at 19:45

# Perl 5-pal, 30 bytes

$_=0;$_++while"@F$_"**.5=~/\./  Try it online! • It's worth noting that since this relies on Perl's default print formatting of floating point numbers, the smallest input it fails with is 2026559 → 23218529 (even though Perl does use IEEE 754, thus would be able to handle all inputs less than 20256971 with a non-typographical "is integer?" test such as $x-int($x)). Not saying it needs changing, just noting the issue. Commented Jan 20, 2020 at 14:27 • Nice answer! I didn't have **.5 in my brief attempt just now, which means you can get to 28 bytes using $\ : Try it online! Commented Jun 22, 2022 at 11:20

## C, 123 115 bytes (thanks, Jo King!)

n,k,m=10,x,p;main(){scanf("%d",&n);for(;k<m||(m*=10);++k)for(p=0;x=n*m+k,p<=x;++p)if(p*p==x)return printf("%d",k);}


I noticed this version can fail on not-very-large inputs due to integer overflow. So I, did a separate version, with less overflow.

## C, less overflow. 117 bytes

n,k,m=10,x,p;main(){scanf("%d",&n);for(;k<m||(m*=10);++k)for(p=0;x=n*m+k,p*p<=x;++p)if(p*p==x)return printf("%d",k);}


## Pretty Printed:

n, k, m = 10, x, p;
main() {
scanf("%d", &n);
for (; k < m || (m *= 10); ++k)
for (p = 0; x = n * m + k, p * p <= x; ++p)
if (p * p == x)
return printf("%d", k);
}

• I think your byte count is 123, not 124. I assume it's a trailing newline thing; can you double check to see if it compiles correctly without it (if present)? It worked for me on TIO but I'm not sure if they insert trailing newlines for you there. Try it online! Commented Jan 18, 2020 at 4:39
• @ValueInk ah yes. I had just checked the file size but it turns out my editor had inserted a trailing newline (which is not necessary in modern C). Thanks Commented Jan 18, 2020 at 19:14
• @JoKing I tried implementing those tweaks without looking at your code but couldn't squeeze as much. I did get rid of the goto though. Thank you! Commented Jan 18, 2020 at 19:41
• 89 bytes Commented Jan 19, 2020 at 14:13
• I like that your "less overflow" version is only 2 bytes longer; it's faster, too. Given that the 115 byte one fails at very small numbers: 218, 244, 245, 248, 254, 255, 279, 283, 284 (challenge-provided test case), 294, 296, 307, 308, 325, 333, 347, 354, 365, 366, and so on, I think maybe you should remove the 115 byte one and leave the 117 byte one as primary. (It of course still fails at 20737, but that's fine, as it must do so with a signed 32-bit int.) Commented Jan 20, 2020 at 16:03

# Brachylog, 8 bytes

;.c~^₂∧ℕ


Sadly enough it takes 3 bytes to check if a number is square and an extra ℕ is needed if the input is a square itself.

## Explanation

;.c~^₂∧ℕ     # Find a value
;.c          #   that concatenate to the input
~^₂       #     gives a square number
∧ℕ     # and make sure that value is a number
#   (otherwise we get the empty list for inputs that are square)


Try it online!

# Python 2, 47 49 bytes

f=lambda p,i=0:int(p+i)**.5%1and f(p,i+1)or i


Try it online!

# C++ (clang), 194 $$\\cdots\$$ 128 129 bytes

#import<string>
#define z std::to_string
int f(int n){for(int j=-1;;)for(long i=0,m=stol(z(n)+z(++j));i++<m;)if(i*i==m)return j;}


Try it online!

Added a byte to fix overflow error kindly pointed out by Deadcode.

• This fails (gives an incorrect answer) with many very small numbers: 218, 244, 245, 248, 254, 255, 279, 283, 284 (a test case provided by the challenge itself), 294, 296, 307, 308, 325, 333, 347, 354, 365, 366, and so on, due to integer overflow. Commented Jan 20, 2020 at 15:22
• @Deadcode Fix that - thanks! :-) Commented Jan 20, 2020 at 15:30
• Wow, very cool that clang has 64-bit long. I didn't know that! Some other dialects of C++ only have 32-bit long and require you to use long long to get 64 bits... Commented Jan 20, 2020 at 15:33
• @Deadcode Yeah, clang gives very good mileage per byte! :)))) Commented Jan 20, 2020 at 15:35

# Python 3, 51 bytes

f=lambda n,i=0:int(f'{n}{i}')**.5%1and f(n,i+1)or i


Try it online!

• This doesn't work for all of the test #s. 284 results in the recursion depth being exceeded. Commented Jan 17, 2020 at 20:24
• I think it's standard to assume unlimited recursion depth in Python answers.
– xnor
Commented Jan 17, 2020 at 22:13

# Ruby -pl, 43 bytes

i=1;i+=1until"#{i*i}"[/^#$_(?!0.|$)/]
$_=$'


Try it online!

Tests each square until it finds one that starts with the input and is followed by a number with no leading zero. I thought going in this direction rather than the more natural one would be shorter, but now I'm doubting that it is.

• "...but now I'm doubting that it is." Well, after tons of searching I couldn't find anything shorter that works on TIO (which runs Ruby 2.5.5). I think $_=(?0..).find{|i|eval($_+i)**0.5%1==0} works on 2.6 for 39 bytes (remove |i| and replace i with @1 in 2.7 for 37 bytes) but I'm having trouble installing those versions on my machine. Commented Jan 18, 2020 at 0:14
• Found a 42 byte solution that's TIO compatible using this technique. Try it online! Commented Jan 18, 2020 at 0:21

# Pyth, 18161511 10 bytes

Uses the floating point square root test, like most of the other answers. As such, the precision is eventually insufficient, and the smallest square it fails with is 4503599761588225 – with an input of 45035997, it returns 61588224 instead of 61588225 as it should. The smallest input it fails with is 20256971, returning 228498166 instead of 228498169 as it should. This is due to IEEE 754 floating point not being able to store precise integers greater than 252.

fsI@s+zT2Z


Try it online!

Ungolfed:

z = input()
Z = 0
for T in __import__('itertools').count(Z):
tmp = int(z + str(T))**0.5
if int(tmp) == tmp:
print(T)
break


Token by token explanation:

fsI@s+zT2Z
f            # (Implicitly print) First value of T for which the following is true:
Z   # where T iterates over [Z, Z+1, Z+2, ...] with Z=0
+zT     # the (string, since one of them is a string) concatenation of z and T
s        # Converted from string to integer
@    2    # To the 1/2 power
sI          # is Invariant under floor conversion to integer


# Packed Pyth, 9 bytes

Hex dump: CD CE 4C 0E 6A FD 54 65 68

Try it online!

# Pyth, 35333023 21 bytes

This is a program that uses only integer arithmetic. Since Python has arbitrary-precision integers, this is guaranteed to work for arbitrarily large numbers, whereas the square-root test used by most of the other answers fails with numbers greater than 252, having false positives with numbers very close to a perfect square.

Assumes that the input has no leading zeroes.

 f&J>K*TTlzq+zsJK)J


Try it online!

The leading space is needed to suppress printout of the value of T that resulted in loop termination, since f returns that value.

Ungolfed:

z = input()
for T in __import__('itertools').count(1):
K = str(T*T);
J = K[len(z):]
if len(J)!=0 and z+str(int(J))==K:
break
print(J)


# Packed Pyth, 19 bytes

Hex dump: 41 99 34 A7 D2 F0 2A A9 53 67 AE 2A FD 60 E7 2A 5A 99 40

Try it online!

# Burlesque, 28 bytes

sajpsq~!_+2R@)S[jfeupjq[-jE!


Try it online!

Pretty sure this could be shorter, a lot of work is trying to drop N letters.

sa       #Find the length of the input to know how many characters to drop
j        #Put at bottom
ps       #Parse the string to {int}
q~!      #Boxed "starts with"
_+       #Concatenate to make {int !~} "starts with int"
2R@      # 2...inf
)S[      #Infinite list of squares
jfe      #Find an element that starts with int
up       #Turn int to string
jq[-jE!  #Drop (length of int) characters leaving the tail

• Ah, accidentally removed the "up" while trying to shorten it. Commented Jan 17, 2020 at 15:57

# Japt, 10 bytes

@s+X ¬v1}a


Try it

# PHP, 5347 44 bytes

for($k=-1;fmod(sqrt($argn.++$k),1););echo$k;


Try it online!

• Nice +1. I have much to learn. Commented Jan 18, 2020 at 0:14
• It's only a crumb, but can't you start $k at 0? Commented Jan 18, 2020 at 0:31 • @GuillermoPhillips yeah, but if you start at 0 you have to do echo$k-1 at the end which is actually 1 byte more. Similarly $k-- doesn't work since you can't decrement NULL (though oddly you can increment it). The value of $k has to be 0 the first time through, or else the 10 test case will fail... good thought though! Commented Jan 18, 2020 at 1:07
• Why $argn? Just use $a and then you will save 3 bytes. Commented Jan 18, 2020 at 3:03
• @Kerkouch How does $a work as input? Unless you're suggesting using a predefined variable, which is not allowed – Jo King Commented Jan 18, 2020 at 10:47 # Japt, 10 bytes _siU ¬%1}f  Saved a byte thanks to @AZTECCO Try it • Commented Jan 20, 2020 at 8:15 # K (ngn/k), 21 19 bytes -2 bytes from @ovs's simplification {(1!%.,/$x,)(1+)/0}


Try it online!

• (cond)(code)/seed set up a while-reduce, seeded with 0, running the (code) clause until the (cond) clause returns a non-truthy value
• (1+) code that increments its input
• (1!%.,/$x,) the condition/check • .,/$x, append the current iteration value to the original input, convert each to a string, combine them, and eval the result (this converts the result to an integer)
• 1!% check if the remainder of the square root of the iteration value is non-zero
• I think you can drop the ~~
– ovs
Commented Jun 22, 2022 at 22:11
• Yep, nice simplification! (It works because the (cond) does a "truthiness" check versus requiring explicit 1's/0's) Commented Jun 22, 2022 at 22:51

# JavaScript (Node.js), 38 Bytes

Try it Online!

f=(a,b=[0])=>(a+b)**.5%1?f(a,[++b]):+b


# Jelly, 8 bytes

0ṭVÆ²ɗ1#


Try it online!

A monadic link taking as its argument an integer and returning an integer.

## Explanation

0    ɗ1# | Starting with zero, find 1 integer where the following is true as a dyad, using the original argument as the right argument
ṭ       | - Tag onto the end
V      | - Evaluate after converting to string and concatenating
Æ²    | - Check if perfect square

• How do you learn this? I'm trying to learn jelly but I can't seem to figure it out. I tried breaking down your code but the symbol ɗ doen't even appear on the atoms page on github Commented Jun 23, 2022 at 0:40

# Perl 5, 35 40 bytes

$k=0;L:$_="$n$k"**.5;!/\./ or$k++,goto L  Try it online! • Your $k=0 clause needs to be part of your code/byte count since it is absolutely necessary for getting the correct answer for the 10 input. Commented Jan 17, 2020 at 21:27
• @Xcali Fair point; fixed. Thanks for catching it. Commented Jan 17, 2020 at 21:43
• Neat technique there. It's worth noting that since this relies on Perl's default print formatting of floating point numbers, the smallest input it fails with is 2026559 → 23218529 (even though Perl does use IEEE 754, thus would be able to handle all inputs less than 20256971 with a non-typographical "is integer?" test such as $x-int($x)). Not saying it needs changing, just noting the issue. Commented Jan 20, 2020 at 14:27
• @Deadcode Good catch, thanks! Commented Jan 20, 2020 at 21:38

# cQuents, 13 bytes

#|1:#bA~N
?$$ Try it online! ## Explanation #|1 output nth element in sequence (remove to output indefinitely) : mode: sequence, output nth element in sequence # conditional: count N up, when true, add to sequence b call second line, passing A~N input concatenated to N ?$$         second line - sequence of squares - return true if a square and false if not


# Charcoal, 16 bytes

≔⁰ηＷ﹪₂Ｉ⁺θη¹≦⊕ηＩη


Try it online! Link is to verbose version of code. Explanation:

≔⁰η


Initialise the result to zero.

Ｗ﹪₂Ｉ⁺θη¹


Repeat until the concatenation is a square.

≦⊕η


Increment the result.

Ｉη


Output the result.

36 bytes for an efficient solution:

≔×χＮη


Try it online! Link is to verbose version of code. Explanation:

Multiply the input by 10.

≧⁺›₂η⌊₂ηη


Increment it unless it is already a square number.

Ｗ⌕ＩＸ⌈₂η²θ


Repeat until the square ceiling square root begins with the original input.

≧×χ


Multiply by 10.

η✂ＩＸ⌈₂η²Ｌθ


Output the suffix of the square ceiling square root.

# GolfScript, 24 bytes

I don't feel right to have a Burlesque answer without a GolfScript answer.(Please don't mind if this is a little bit slow, although they seem to produce the right result.)

-1{).2$\+~.),{.*}%?)!}do  Try it online! ## Explanation -1 # The counter for the current number (it is >= 0) { # Do at least 1 time until the number is a square number ) # Increment the counter . # Copy the counter (to create an integer) 2$                  #     Extract the 3rd-to-top to the top
\                 #     Make sure that the casting to string works
+                #     Join the numbers, as well as converting the
#     right operand to a string (input+count)
~               #     Evaluate the string to get a number

.              #     Copy the number for the square number check
),            #     Generate range from 0 to the number
{.*}%       #     Apply square for every number
?      #     Find out where the number is inside the sequence
#     (yields -1 for nonexistent)

)     #     Increment, to make nonexistent false and others true
!    #     Negate, which means we shouldn't find the first non-square number.
}do # End do loop, use TOS as condition

# Output the counter at the end
$$$$


# AWK, 29 bytes

{while(($0x++)^.5%1);$0=x-1}1


Works with mawk, gawk and nawk on macOS and Ubuntu but not with TiO for some reason.

• I also don't know why this happens, but I have faced this kind of error before. I managed to bypass it by assigning the result to $1 instead of $0, like this: {while(($0x++)^.5%1);$1=x-1}1. Try it online! Commented Jan 13, 2021 at 16:27

# RProgN 2, 13 bytes

x={x\.nš1%¬}é


# Explanation

x={x\.nš1%¬}é   #
x=              # Set 'x' to the input.
{        }é   # Run the enclosed function with raising integers untill it returns truthy, and spit out that number
x\.          # Place the input under the current number and concatenate them together
nš        # Convert to a number and get the square root
1%¬     # Is this a whole number?


Try it online!

# Java, 7563 61 bytes

Two bytes less thanks to Kevin Cruijssen.

And another two less in the second version again thanks to Kevin Cruijssen!

n->{int j=0;for(;Math.sqrt(new Long(n+j))%1>0;j++);return j;}


Try it online!

I also have another version with my first (and very different) approach, which is 107 92 93 91 bytes long:

n->{String a;for(long i=4;!(a=i*i+++"").matches(n+"([1-9].*|0)"););return a.split(n,2)[1];}


Try it online!

Both version have been tested against the first 10000 numbers.

• You can remove the parenthesis surrounding Math.sqrt(new Long(n+j))%1 to save 2 bytes. Commented Jan 29, 2020 at 12:53
• @KevinCruijssen True! In an initial version I needed them, but while refactoring I didn't realise I could remove them. Thanks! Commented Jan 29, 2020 at 12:59
• Np. Btw, in your second version you can also save 2 bytes: 1 by changing long i=4;String a;while(...); to String a;for(long i=4;...;); to save on the semi-colon, and 1 by removing the + in your regex, since the .* already covers this. Nice answer, btw! And welcome to CGCC! :) Commented Jan 29, 2020 at 13:07
• @KevinCruijssen Thanks again! I totally missed the long inside the for hack. And again the "+" was becuase of a previous version in which I didn't have the ".*|0" part, but whitout that part I didn't cover for the f(10) -> 0 case correctly and other solution with a 0 in them , but when I added it I didn't realise the "+" wasn't necessary any more. Really nice catch :). Commented Jan 29, 2020 at 14:16

# Haskell, 93 88 bytes

[j|i<-(show.(^2))<$>[0..],i/=n,nisPrefixOfi,j<-[drop(length n)i],j=="0"||j!!0/='0']!!0  Try it online! • Welcome to the site! head can be shorter done as !!0. Commented Jan 17, 2020 at 20:55 • Additionally your map could be <$> which would remove needing for the parentheses and save two bytes. Commented Jan 17, 2020 at 20:57
• And just one more if you are in a list comprehension x<-[s] is a byte shorter than let x=s Commented Jan 17, 2020 at 21:00
• @PostRockGarfHunter Thanks; updated! I wish I had a more elegant way to write the hideous j=="0"||j!!0/='0'. Commented Jan 17, 2020 at 21:37
• How about j==show(read j) Commented Jan 17, 2020 at 21:48

# PHP, 83 86 bytes

g:substr($k=$i*++$i,0,$l=strlen($n=$argn))==$n&&("$k")[$l]&&die(substr($k,$l));goto g;  Try it online! -9 bytes thanks to @640KB and bugs fixed (+12). Only fails for case 10 currently. ## Ungolfed <?php$number=$argv[1];$len = strlen($number);$i=0;
do {
$k =$i*$i; if (substr($k,0,$len)==$number && substr($k,$len,1)!='0') {
die(substr($k,$len));
}
\$i++;
} while (true);

?>


Try it online!

• Love the goto - will have to try to use that sometime! Good news is that you don't have to include the opening <?php  in your byte count so this would only be 79 bytes. Bad news is that this answer fails for test cases 1, 164 and 284`. Commented Jan 17, 2020 at 21:23
• Thanks, g:goto g; is the same cost as for(;;){}, but I'm a rebel! I will have to tame those pesky leading zeros. Commented Jan 18, 2020 at 0:11
• My first version was very similar to yours and I ran into the exact same problems, so I ended up scrapping it and doing it a different way. That's how it goes sometimes! Commented Jan 18, 2020 at 0:22