Smallest number such that concatenation is a square

Question

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 code-golf, so shortest code in bytes wins

Answer 1

05AB1E, 7 bytes

∞<.Δ«Å²

Try it online or verify all test cases.

05AB1E (legacy), 8 bytes

[N«Å²#}N

Try it online or verify all test cases.

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.

Answer 2

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

Answer 3

J, ²⁷ 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

Answer 4

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!

Answer 5

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.

Answer 6

Perl 5 -pal, 30 bytes

$_=0;$_++while"@F$_"**.5=~/\./

Try it online!

Answer 7

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);
}

Answer 8

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!

Answer 9

Python 2, 47 49 bytes

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

Try it online!

Answer 10

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.

Answer 11

Python 3, 51 bytes

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

Try it online!

Answer 12

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.

Answer 13

Pyth, 18 16 15 11 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 2⁵².

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!

Answer 14

Pyth, 35 33 30 23 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 2⁵², having false positives with numbers very close to a perfect square.

Assumes that the input has no leading zeroes.

 f&J>K`*TTlzq+z`sJK)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!

Answer 15

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

Answer 16

Japt, 10 bytes

@s+X ¬v1}a

Try it

Answer 17

PHP, 53 47 44 bytes

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

Try it online!

Answer 18

Japt, 10 bytes

_siU ¬%1}f

Saved a byte thanks to @AZTECCO

Try it

Answer 19

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

Answer 20

JavaScript (Node.js), 38 Bytes

Try it Online!

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

Answer 21

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

Answer 22

Perl 5, 35 40 bytes

$k=0;L:$_="$n$k"**.5;!/\./ or$k++,goto L

Try it online!

Answer 23

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

Answer 24

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.

Answer 25

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
```

Answer 26

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.

Answer 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!

Answer 28

Java, 75 63 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.

Answer 29

Haskell, 93 88 bytes

[j|i<-(show.(^2))<$>[0..],i/=n,n`isPrefixOf`i,j<-[drop(length n)i],j=="0"||j!!0/='0']!!0

Try it online!

Answer 30

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!