A Python coding exercise asks to make a function f such that f(k) is the k-th number such that its k-th digit from the left and from the right sums to 10 for all k. For example 5, 19, 28, 37 are the first few numbers in the sequence.
I use this function that explicitly checks if the number 'n' satisfies the property:
def check(n):
#even digit length
if len(str(n)) % 2 == 0:
#looping over positions and checking if sum is 10
for i in range(1,int(len(str(n))/2) + 1):
if int(str(n)[i-1]) + int(str(n)[-i]) != 10:
return False
#odd digit length
else:
#checking middle digit first
if int(str(n)[int(len(str(n))/2)])*2 != 10:
return False
else:
#looping over posotions and checking if sum is 10
for i in range(1,int(len(str(n))/2) + 1):
if int(str(n)[i-1]) + int(str(n)[-i]) != 10:
return False
return True
and then I loop over all numbers to generate the sequence:
for i in range(1, 10**9):
if check(i):
print(i)
However the exercise wants a function f(i) that returns the i-th such number in under 10 seconds. Clearly, mine takes a lot longer because it generates the entire sequence prior to number 'i' to calculate it. Is it possible to make a function that doesn't have to calculate all the prior numbers?
Testing every natural number is a bad method. Only a small fraction of the natural numbers have this property, and the fraction decreases quickly as we get into larger numbers. On my machine, the simple Python program below took over 3 seconds to find the 1,000th number (2,195,198), and over 26 seconds to find the 2,000th number (15,519,559).
# Slow algorithm, only shown for illustration purposes
# '1': '9', '2': '8', etc.
compl = {str(i): str(10-i) for i in range(1, 10)}
def is_good(n):
# Does n have the property
s = str(n)
for i in range((len(s)+1)//2):
if s[i] != compl.get(s[-i-1]):
return False
return True
# How many numbers to find before stopping
ct = 2 * 10**3
n = 5
while True:
if is_good(n):
ct -= 1
if not ct:
print(n)
break
n += 1
Clearly, a much more efficient algorithm is needed.
We can loop over the length of the digit string, and within that, generate numbers with the property in numeric order. Sketch of algorithm in pseudocode:
for length in [1 to open-ended]:
if length is even, middle is '', else '5'
half-len = floor(length / 2)
for left in (all 1) to (all 9), half-len, without any 0 digits:
right = 10's complement of left, reversed
whole-number = left + middle + right
Now, note that the count of numbers for each length is easily computed:
Length First Last Count
1 5 5 1
2 19 91 9
3 159 951 9
4 1199 9911 81
5 11599 99511 81
In general, if left-half has n digits, the count is 9**n.
Thus, we can simply iterate through the digit counts, counting how many solutions exist without having to compute them, until we reach the cohort that contains the desired answer. It should then be relatively simple to compute which number we want, again, without having to iterate through every possibility.
The above sketch should generate some ideas. Code to follow once I’ve written it.
Code:
def find_nth_number(n):
# First, skip cohorts until we reach the one with the answer
digits = 1
while True:
half_len = digits // 2
cohort_size = 9 ** half_len
if cohort_size >= n:
break
n -= cohort_size
digits += 1
# Next, find correct number within cohort
# Convert n to base 9, reversed
base9 = []
# Adjust n so first number is zero
n -= 1
while n:
n, r = divmod(n, 9)
base9.append(r)
# Add zeros to get correct length
base9.extend([0] * (half_len - len(base9)))
# Construct number
left = [i+1 for i in base9[::-1]]
mid = [5] * (digits % 2)
right = [9-i for i in base9]
return ''.join(str(n) for n in left + mid + right)
n = 2 * 10**3
print(find_nth_number(n))