# 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? – Xcali Jan 17 '20 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... – 640KB Jan 17 '20 at 21:30
• OK, then. It makes my code shorter to ignore the leading 0s anyway. – Xcali Jan 17 '20 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. – mabel Jan 17 '20 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. – Level River St Jan 17 '20 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α. – Grimmy Jan 17 '20 at 12:40
• Actually my suggested 6 fails for 183673469387755102041 (yes this is the smallest counter-example I could find). – Grimmy Jan 17 '20 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! – Kevin Cruijssen Jan 17 '20 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? – A. Rex Jan 18 '20 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. – Grimmy Jan 18 '20 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. – Thomas Markov Jan 20 '20 at 19:07
• @ThomasMarkov if you're running them sequentially in a single session, the global variable F won't be reset properly. – Giuseppe Jan 20 '20 at 19:45

## 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! – Value Ink Jan 18 '20 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 – Sebastián Mestre Jan 18 '20 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! – Sebastián Mestre Jan 18 '20 at 19:41
• 89 bytes – AZTECCO Jan 19 '20 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.) – Deadcode Jan 20 '20 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. – Deadcode Jan 20 '20 at 15:22
• @Deadcode Fix that - thanks! :-) – Noodle9 Jan 20 '20 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... – Deadcode Jan 20 '20 at 15:33
• @Deadcode Yeah, clang gives very good mileage per byte! :)))) – Noodle9 Jan 20 '20 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. – Benji Jan 17 '20 at 20:24
• I think it's standard to assume unlimited recursion depth in Python answers. – xnor Jan 17 '20 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. – Value Ink Jan 18 '20 at 0:14
• Found a 42 byte solution that's TIO compatible using this technique. Try it online! – Value Ink Jan 18 '20 at 0:21

$_=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. – Deadcode Jan 20 '20 at 14:27 # 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. – DeathIncarnate Jan 17 '20 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. – Guillermo Phillips Jan 18 '20 at 0:14 • It's only a crumb, but can't you start$k at 0? – Guillermo Phillips Jan 18 '20 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! – 640KB Jan 18 '20 at 1:07 • Why $argn? Just use $a and then you will save 3 bytes. – Kerkouch Jan 18 '20 at 3:03 • @Kerkouch How does $a work as input? Unless you're suggesting using a predefined variable, which is not allowed – Jo King Jan 18 '20 at 10:47

# Japt, 10 bytes

_siU ¬%1}f


Saved a byte thanks to @AZTECCO

Try it

• – AZTECCO Jan 20 '20 at 8:15

# 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


# 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. – Xcali Jan 17 '20 at 21:27
• @Xcali Fair point; fixed. Thanks for catching it. – Greg Bacon Jan 17 '20 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. – Deadcode Jan 20 '20 at 14:27
• @Deadcode Good catch, thanks! – Greg Bacon Jan 20 '20 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! – Pedro Maimere Jan 13 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. – Kevin Cruijssen Jan 29 '20 at 12:53
• @KevinCruijssen True! In an initial version I needed them, but while refactoring I didn't realise I could remove them. Thanks! – GuestUser Jan 29 '20 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! :) – Kevin Cruijssen Jan 29 '20 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 :). – GuestUser Jan 29 '20 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. – Wheat Wizard Jan 17 '20 at 20:55 • Additionally your map could be <$> which would remove needing for the parentheses and save two bytes. – Wheat Wizard Jan 17 '20 at 20:57
• And just one more if you are in a list comprehension x<-[s] is a byte shorter than let x=s – Wheat Wizard Jan 17 '20 at 21:00
• @PostRockGarfHunter Thanks; updated! I wish I had a more elegant way to write the hideous j=="0"||j!!0/='0'. – Greg Bacon Jan 17 '20 at 21:37
• How about j==show(read j) – Wheat Wizard Jan 17 '20 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. – 640KB Jan 17 '20 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. – Guillermo Phillips Jan 18 '20 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! – 640KB Jan 18 '20 at 0:22

# Lua, 96 bytes

n=io.read()i=0 while i do for j=0,n..i do if (n..i)+0==j*j then print(i)return end end i=i+1 end
`

Try it online!