The A010784 sequence at OEIS is the sequence containing only numbers with distinct digits. This is a finite amount.
What I've been trying to do is find several numbers in this sequence with certain attributes.
E.g: 6 is a distinct number of magnitude 10. This can be found as follows:
Now I'm trying the highest numbers available for several magnitudes of order.
Let's say all orders from 1 up to 20.
What I'm currently doing is loop from the highest possible distinct number, which is 9,876,543,210 and the highest unique number of magnitude 1, down to a very low number.
This method feels extremely inefficient. At least, to me it does.
I'm pretty sure I'm missing some stuff about factoring that should be able to make things a lot faster.
def unique_num(num):
# Check whether number is unique.
return Boolean
def unique_num_magnitude(num):
# Check of which magnitude the unique number is
return Integer
# Dictionary with the current highest values
# for each magnitude.
values = {1: 987654321...}
# Set limits
upper_limit = 9876543210
lower_limit = 1
for numbers in range(upper_limit, lower_limit, -1):
unique = unique_num(num) # Boolean
if (unique):
magnitude = unique_num_magnitude(num)
if (values[magnitude] < num):
values[magnitude] = num
Sure there is better way. You should build the numbers bottom up, i.e. if a number a1...ak (these are k digits) is not of magnitude N so that a digit appears twice within the first k digits of the result for any multiplicand 2..N then neither is any number b1...bm a1...ak. This provides a categorically faster recursive enumeration procedure because it cuts an exponential amount of search space away. Details left as an exercise to OP.
Longer explanation:
Assume there is a procedure
magnitude(number_str)
that calculates the magnitude for the number number_str represented in 10-base, so that the procedure returns 0 if number_str contains at least one double occurrence of a digit, 1 if number_str has every digit distinct but multiplying the number by two results in a digit occurring multiple times, etc.
This procedure can be implemented in terms of another one
unique_digits(number_str)
which returns true if all digits in number_str are unique, otherwise false.
Now then magnitude can be implemented as
magnitude(number_str):
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(int_to_str(k))):
k = k + n
i = i + 1
return i
Now this magnitude procedure can be changed to a nocarry_magnitude that changes the check subtly:
nocarry_magnitude(number_str, limit):
l = length(number_str)
assert (l > 0)
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(right_substring(int_to_str(k), l))):
k = k + n
i = i + 1
if (i == limit):
break
return i
This procedure checks for the multiple times occurring digits only in as many rightmost digits (lowest-order digits) of the product in the loop as there were digits in the original input. A limit parameter is needed to make sure the procedure terminates as it's possible that the procedure runs in an infinite loop otherwise. Clearly for any string s it holds that
magnitude(s) <= nocarry_magnitude(s, M) for large M
For instance, take number 19:
19 * 1 = 19
19 * 2 = 38
19 * 3 = 57
19 * 4 = 76
19 * 5 = 95
19 * 6 = 114 // magnitude("19") = 5
19 * 7 = 133 // nocarry_magnitude("19", 100) = 6
What I wrote above in the short description is that if
nocarry_magnitude(s, x) == k for x > k
then for any string that's obtained by postfixing s (denote this by x + s below), it holds that
x : string of digits
magnitude(x + s) <= nocarry_magnitude(x + s, m) <= nocarry_magnitude(s, m)
when m >= magnitude(x + s)
The first inequality comes from the claim above and the second one is obvious from the definition of nocarry_magnitude. Note that magnitude(x + s) <= magnitude(s) is a non-theorem in general as exemplified by
magnitude( "56") = 1 // 56 * 2 = 112
magnitude("256") = 12 // the first duplicate occurs at 3328
which is caused by the carry. nocarry_magnitude ignores the carry which is why the suffix of a string has always as large nocarry-magnitude as any extension of it (towards left, i.e. higher-order digits).
Now then you can write a significantly faster recursive procedure as this for searching for numbers with magnitude at least M:
search(str):
if (str != ""):
int n = nocarry_magnitude(str, M)
if (n < M):
return # the optimization
int k = magnitude(str)
if (k >= M):
store_answer(str)
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + str)
search("")
Here's a full Python implementation (searching for magnitude 36):
def unique_digits(s):
r = (len(list(s)) == len(set(s)))
return r
def magnitude(s):
n = int(s)
k = n
assert n > 0
i = 0
while (unique_digits(str(k))):
k = k + n
i = i + 1
return i
def nocarry_magnitude(s, limit):
l = len(s)
assert l > 0
n = int(s)
assert n > 0
k = n
i = 0
while (unique_digits(str(k)[-l:])):
k = k + n
i = i + 1
if (i >= limit):
break
return i
M = 36
def search(s):
if (not(s == "")):
n = nocarry_magnitude(s, M)
if (n < M):
return
k = magnitude(s)
if (k >= M):
print "Answer: %s |" % s,
i = int(s)
k = i
n = 1
while (n <= M):
print k,
k = k + i
n = n + 1
print
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + s)
search("")
And here's a run that takes less than one second; this finds the answer '27' which seems to be the unique number that provides the record magnitude 36:
Answer: 27 | 27 54 81 108 135 162 189 216 243 270 297 324 351 378 405
432 459 486 513 540 567 594 621 648 675 702 729 756 783
810 837 864 891 918 945 972