s10_automorphic_numbers.py

# -*- coding: utf-8 -*-
"""S10-Automorphic Numbers.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1vdVfQwsz2pPtvazzKsqCL4wMcOfK_fJ5

**Our Naive Try**
"""

import math
order = int(input())

o = 4
a = 5 

i5 = 5
i6 = 6
while True:
  for d in range(1,11):
    n5 = math.ceil(math.log10(i5))
    a = d*(10**n5)+i5
    nn5 = math.ceil(math.log10(a))
    a2 = a**2
    if (a2-a)%(10**nn5)==0:
        o+=1
        i5=a

    n6 = math.ceil(math.log10(i6))
    b = d*(10**n6)+i6
    b2 = b**2
    nn6 = math.ceil(math.log10(b))
    if (b2-b)%(10**nn6)==0:
        o+=1
        i6=b


  #print(n5,n6,a,b,i5,i6)


  if o>=order:
    break

   

if o>order:  
  print(min(i5,i6))
else:
  print(max(i5,i6))

"""**Based on a math formula, much much faster**"""

d = 20

# set up variables
total = 3
n_five = 5
n_six = 6


# print a title and the first 3 digits
print( "Automorphic Numbers up to " + str(d) + " Digits Long:")
print( "  1")
print("  5")
print("  6")


# find new n_five and n_six automorphic numbers based on the equations
#  n' = -2n^3 + 3n^2 (mod 10^(k + 1)) and n_five + n_six = 10^k + 1,
#  for n as a known automorphic number with k digits
for k in range(1, d):
  n_five = (-2 * n_five ** 3 + 3 * n_five ** 2) % (10 ** (k + 1))
  n_six = 10 ** (k + 1) + 1 - n_five
  if n_six < n_five:
    if n_six > (10 ** k):
       print ("  " + str(n_six))
       total += 1
    if n_five > (10 ** k):
      print ("  " + str(n_five))
      total += 1
  else:
            if n_five > (10 ** k):
                print ("  " + str(n_five))
                total += 1
            if n_six > (10 ** k):
                print ("  " + str(n_six))
                total += 1


    # print the total
print ("Total: " + str(total))