login
A307177
Decimal expansion of smallest nontrivial base-10 number that contains all pairwise products of its digits as substrings.
0
1, 0, 1, 2, 0, 1, 4, 0, 1, 5, 2, 1, 6, 2, 4, 2, 5, 3, 0, 3, 2, 7, 2, 8, 1, 8, 3, 5, 4, 5, 6, 3, 6, 4, 8, 4, 9
OFFSET
37,4
COMMENTS
"Pairwise products" includes the squares of the digits.
Suggested by Ricardo Palomino, who mentioned the trivial numbers A007088.
If any digit other than 0 or 1 appears, then all ten digits appear, as can easily be checked for each digit. For example, if 2 appears then 2*2 = 4 appears, which implies that 2*4 = 8 appears and {1,6} (from 4*4 = 16) appear, which implies that 3 appears (from 4*8 = 32), which implies that 3*3 = 9 appears, which implies that {2,7} appear (from 3*9), which implies that {5,6} appear (from 7*8), which implies that 0 appears (from 2*5 = 10).
There are 37 distinct products (10 with one digit and 27 with two digits) of pairs of digits from {0,1,...,9}.
Rob Pratt solved an asymmetric traveling salesman problem (ATSP) on 38 nodes to find the minimum number of digits, which turns out to be 37, and then solved a sequence of integer linear programming problems (minimizing one digit at a time from left to right) to find the minimum such 37-digit number.
EXAMPLE
1012014015216242530327281835456364849.
CROSSREFS
A203565 considers only products of adjacent digits.
Sequence in context: A349706 A271466 A218581 * A340264 A291878 A131487
KEYWORD
nonn,cons,fini,full,base
AUTHOR
Rob Pratt, Mar 27 2019
STATUS
approved