@jinxonik / UniLecs puzzle #52

puzzle_52_ext.py

# Find numbers of specified length that are complete squares with ascending sorted non-repeating digits in specified radix
# Returns list of found values of None on invalid radix or length parameters
def find_perfect_squares(radix, length):

  if not 2 <= radix <= 36 or not 1 <= length < radix:
    return None

  from math import ceil, floor

  digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  s_min = int(digits[1:length+1], radix)
  s_max = int(digits[radix-length:radix], radix)

  digs = ((length-1)//2)
  d_min = length - digs - 1

  pots = [1]*(digs+1)
  pot = 1
  for i in range(digs-1, -1, -1):
    pot *= radix
    pots[i] = pot

  values = []

  # convert n from decimal to radix
  def convert(n):
    result = ""
    while n > 0:
      n, r = divmod(n, radix)
      result = digits[r] + result
    return result

  # find values
  def find(n, idx, last):
    for x in range(radix):
      m = x * pots[idx] + n
      s = m * m
      if idx == 0:
        if s_min <= s <= s_max:
          value = convert(s)
          prev = ""
          for c in value:
            ok = (c > prev)
            if not ok: break
            prev = c
          if ok: values.append(value)
      else:
        d = s // pots[idx] % radix
        if d_min+idx < d < last:
          find(m, idx-1, d)

  find(0, digs, radix)

  return values

################################################################################

if __name__ == "__main__":

  try:
    radix, length = map(int, input("Please enter 'radix' and 'length' (via space): ").split(" "))
  except:
    print("Incorrect numbers are specified!")
    exit()

  from time import time
  start = time()
  values = find_perfect_squares(radix, length)
  print(f"Elapsed time: {time()-start:.6f} sec")

  if values is None:
    print("Invalid values: 'radix' must be 2..36, 'length' must be 1..(radix-1)!")
  else:
    if len(values) == 0:
      print("No numbers are found :(")
    else:
      print(f"Found {len(values)} number{'s' if len(values) > 1 else ''}:")
      print(*values, sep="\n")