#!/usr/bin/python3 -u

# --------------------------------------------------------------

# Please adjust following values

maxlen   = 100
minbase  = 2
maxbase  = 36
minpower = 2
maxpower = 10

mode = 0  # 0 = Sort numerical (lowest to biggest)
          # 1 = Sort by branch

# --------------------------------------------------------------

# Don't edit after this line

import string

print("IMMORTAL NUMBER SEARCH FOR BASE-B POWER-P")
print("Base:       {:>2} to {:>2}".format(minbase,maxbase))
print("Power:      {:>2} to {:>2}".format(minpower,maxpower))
print("Max length: {}".format(maxlen))
if mode == 0:
	print("Sort mode:  numerical")
elif mode == 1:
	print("Sort mode:  by branches")
else:
	print("ILLEGAL SORT MODE")
print("")

#def baseN(num,b,numerals="0123456789abcdefghijklmnopqrstuvwxyz"):
#	return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

def baseN(n, N):
    """ Return base N representation for int n. """
    base_n_digits = "0123456789abcdefghijklmnopqrstuvwxyz"
    result = ""
    if n < 0:
        sign = "-"
        n = -n
    else:
        sign = ""
    while n > 0:
        q, r = divmod(n, N)
        result += base_n_digits[r]
        n = q
    if result == "":
        result = "0"
    return sign + "".join(reversed(result))

def ordnum(i):
	if i == 1:
		return "1st"
	elif i == 2:
		return "2nd"
	elif i == 3:
		return "3rd"
	else:
		return "{}th".format(i)

#def isImmortal(n,b,p):
#	nb=baseN(n,b)
#	return baseN(n**p,b).endswith(nb)
def isImmortal(n,b,p):
	len = 1
	z = b
	while z < n:
		z = z * b
		len = len + 1
	return n**p % (b**len) == n

def rec_(n,b,p,l=1,m=10):
	out = []
	if isImmortal(n,b,p):
		if m > 0:
			out.append(n)
		if l<maxlen:
			for bx in range(0,b):
				nx = bx*b**l+n # add the digit "bx" in front of the number "n" and assign it to "nx"
				out_ = rec_(nx, b, p, l+1, bx)
				out = out + out_
	return out

def findImmort(b,p):
	print("Base {}".format(b))
	print("\tPower {}".format(p))
	if mode == 0:
		out = []
	for bx in range(0,b):
		if mode == 1:
			out = []
		out = out + rec_(bx, b, p)
		if mode == 1:
			out.sort()
			i=0
			for n in out:
				nb=baseN(n,b)
				i=i+1
				print("\t\t{:>5} immortal number at branch {}: {}".format(ordnum(i),baseN(bx,b),nb))
	if mode == 0:
		out.sort()
		i=0
		for n in out:
			nb=baseN(n,b)
			i=i+1
			print("\t\t{:>5} immortal number: {}".format(ordnum(i),nb))

for b in range(minbase,maxbase+1):
	for p in range(minpower,maxpower+1):
		findImmort(b,p)

# --------------------------------------------------------------