# Author: Manfred Scheucher
# Date  : Jul 23 2015, updated Feb 08 2024


from sys import argv
k = int(argv[1]) # compute terms of sequence with up to this number of digits
assert(k>=1)

sequence = []
compute_further_terms = False
further_terms = []

def find(a=""):
	m = len(a) # recursively build integers x with up to k digits (which are encoded as string a) 
	# such that x has no common digits with x^2 and x^3 

	forbidden = set()
	if m > 0:
		x  = int(a)
		x2 = x**2 	
		x3 = x**3

		if a[0] != '0' and not set(a) & set(str(x2)+str(x3)):
			# if a has no trailing zeros (it is minimal representative of x) 
			# and all digits of x are distinct from x^2 and x^3, then output solution
			sequence.append(x)

		# only m digits of x are set, so only m digits of x^2 and x^3 are determined. 
		# omit the rest for recursion
		forbidden = set(str(x2 % 10**m)+str(x3 % 10**m))
	
	further_digit_options = set('0123456789')-forbidden

	if further_digit_options and further_digit_options != {'0'}:
		# appending trailing zeros will never give a new integer
		if m < k:
				for d in further_digit_options: 
					# digits which already occur in x^2 or x^3 are not allowed 
					find(str(d)+a) # add digit and continue recursively

		elif compute_further_terms:
			further_terms.append((further_digit_options,a))


find()

print(f"the following terms with at most {k} digits exist:")
for i,x in enumerate(sorted(sequence)):
	print(f"a({i+1}) = {x}")


if compute_further_terms:
	print(f"all further terms (with more than {k} digits) when written as string")
	print("match the following regular expression:")
	print("(see https://www.w3schools.com/python/python_regex.asp)")
	for further_digit_options,a in further_terms:
		print('['+''.join(further_digit_options)+']+'+a)