cp's OEIS Frontend

A135472 Shortest and lexicographically earliest string of decimal digits with property that when made into cycle every pair of digits from 0,0 to 9,9 can be seen exactly once.

%I A135472 #10 Aug 09 2016 11:01:40
%S A135472 0,0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,
%T A135472 1,9,2,2,3,2,4,2,5,2,6,2,7,2,8,2,9,3,3,4,3,5,3,6,3,7,3,8,3,9,4,4,5,4,
%U A135472 6,4,7,4,8,4,9,5,5,6,5,7,5,8,5,9,6,6,7,6,8,6,9,7,7,8,7,9,8,8,9,9
%N A135472 Shortest and lexicographically earliest string of decimal digits with property that when made into cycle every pair of digits from 0,0 to 9,9 can be seen exactly once.
%C A135472 Comments from _Max Alekseyev_, Feb 14 2008: (Start) It is easy to prove that such a string exists and, moreover, it can be closed into a circle of length 100.
%C A135472 Namely, let us construct a (directed) de Bruijn graph G on vertices V={0,1,2,3,4,5,6,7,8,9}, where every vertex is connected to every other vertex (including itself - so there is a self-loop at every vertex) by a directed arc. The arcs in G "encode" all possible 2-digit strings.
%C A135472 Any string over the alphabet V can be viewed as a path in G. If the string contains all 2-digit strings as substrings, then the corresponding path passes through every arc in G. The shortest such path is an Eulerian one (if it exists) and it indeed exists in G.
%C A135472 The indegree of every vertex in G equals its outdegree, implying that there exists an Eulerian cycle. Such a cycle has length 100 and visit every vertex 10 times.
%C A135472 So we want to find an Eulerian cycle resulting in the lexicographically earliest string. Such a cycle can be easily found by traversing G in a greedy manner. (End)
%Y A135472 Cf. A102167.
%K A135472 nonn,fini,full,base,nice
%O A135472 1,5
%A A135472 Patrick A. Kirol (sunwukong(AT)povn.com), Feb 08 2008
%E A135472 Confirmed by _Max Alekseyev_, _Joshua Zucker_ and _Joerg Arndt_, Feb 14 2008
%E A135472 Edited by _N. J. A. Sloane_, Feb 18 2008