Smallest Square Function-CodePudding

Consider a positive integer n. What will be the smallest number k such that if we concatenate the digits of n with those of k we get a perfect square?

For example, for n=1 the smallest k is 6 since 16 is a perfect square.

For n=4, k has to be 9 because 49 is a perfect square.

For n=35, k is 344, since 35344=1882 is the smallest perfect square starting with the digits 35.

Define the smallestSquare function that takes a positive integer n and returns the smallest integer k whose concatenation of the digits of n,k results in a perfect square.

For now all I have is this, which checks wether the given number is a perfect square or not. I would like to solve this using recursion but I'm not even sure where to start.

from math import sqrt

def isSquare(n):
  return n == int(sqrt(n)   0.5) ** 2
  
def smallestSquare(n):

CodePudding user response：

No recursion is necessary:

def smallestSquare(n):
    x = 1
    while isSquare(int(str(n) str(x))) == False:
        x  = 1
    return int(str(n) str(x))

CodePudding user response：

If, given some number 'n', you are looking for the smallest perfect suqare that begins with 'n', the following is an approach that should work:

import math

def find_smallest_perfect_square(start: int) -> int:
    while True:
        if int(math.sqrt(start)) != math.sqrt(start):
            start  = 1
        else:
            return start
        
def find_concatenation(n: int) -> int:
    str_n = str(n)
    while True:
        val = find_smallest_perfect_square(n)
        if str(val).startswith(str_n):
            return val
        else:
            n = val   1

Testing:

for i in range(10):
    print (f'The smallest perfect square that begins with {i} is {find_concatenation(i)}')

# Result:
    # The smallest perfect square that begins with 0 is 0
    # The smallest perfect square that begins with 1 is 1
    # The smallest perfect square that begins with 2 is 25
    # The smallest perfect square that begins with 3 is 36
    # The smallest perfect square that begins with 4 is 4
    # The smallest perfect square that begins with 5 is 529
    # The smallest perfect square that begins with 6 is 64
    # The smallest perfect square that begins with 7 is 729
    # The smallest perfect square that begins with 8 is 81
    # The smallest perfect square that begins with 9 is 9

If what you're looking for is "the smallest value of k" which, when concatenated with n, yields a perfect square - the above approach is not guaranteed to give you what you want. If that's what you require, please specify.