Data Redundancy

So, the best possible solution would be one in which each digit after the first seven (concatenated to the previous six) revealed a new phone number. It's length would be 7+10^7-1 = 10,000,006.

The string would be one in which every seven-digit substring [x1][x2]...[x7] represents a vertex in a directed graph and every eight-digit substring [x0][x1]...[x7] represents an edge from the vertex [x0][x1]...[x6] to the vertex [x1][x2]...[x7]. Since we don't want redundancy we don't want any phone number, or any vertex, to be seen twice. In other words we are looking for a Hamiltonian path (the sequence of edges that visits every seven-digit substring exactly once).

The number 1234567, for example, has edges of the form 1234567x where x is something in 0,1,...,9, (10 different values x could take on => 10 different edges outgoing) that go to numbers of the form 234567x. So, every vertex has ten outgoing edges and ten incoming edges. (Numbers like 1111111 with the edge 11111111 (eight ones) count self-edges, not that that is useful, but it makes us consistent about our number of incoming/outgoing edges. But I digress..)

Since determining whether a graph like this has a Hamiltonian path or cycle is supposed to be something like NP-hard, I try to just give an algorithm that I think would work for constructing a Hamiltonian cycle, with the resulting string having the aforementioned length of 10,000,006 (wherein the first six and last six digits are the same, so are actually redundant and we can say then that 10,000,000 digits provides sufficient information).

0. Somehow, like with a database or something, associate vertices with their respective incoming/outgoing edges.

1. Pick a seven-digit number/vertex.

2. Pick one of its outgoing edges. Bold-color this in so we know we are using that edge in our solution.

3. Hash-mark its incoming edges. We cannot use hash-marked edges until we have visited every other vertex. This way we guarantee that we will not close the cycle prematurely.

4. To prevent considering them later, delete every other outgoing edge from that vertex (including any hash-marked edges). Examine the vertices those outgoing edges go to; if there is only one edge remaining that goes into that vertex, bold-color that edge in. This way we guarantee that there is a way into every vertex.

Also, delete every incoming edge to that vertex. This way we will know not to consider it at some later vertex, and we will guarantee that we will not visit our current vertex twice. Examine the vertices the incoming edges are coming from. If there is only one remaining usable (hash-marked edges are not usable until the condition given in (3)) outgoing edge, bold-color it in; that guarantees a way out of every vertex.

5. At the new vertex chosen by the edge chosen in (2), pick an outgoing edge and repeat (4) until all vertices have been visited. If there is only one outgoing edge and it is bold-colored in, obviously move on to the next vertex where you have to make a decision.

I hope that works. It worked for small cases (up to 3-digit phone numbers and with up to 3 values for each digit) but that could just be attributed to the Law of Small Numbers. :P (Yay I haven't gotten to draw a graph in too long a time..)

m: Very nice. Since each vertex has an even number of edges (an even degree) we're guaranteed to find an Euler circuit, but that would clearly touch every vertex more than once (five times, actually). Although determining whether or not a graph has a Hamiltonian circuit is NP-hard, this problem describes a 7-dimensional hypercube, which is known to be Hamiltonian. (All hypercubes are Hamiltonian, except for the 1-dimentional hypercube.) That's basically what you said.

Gosh, I'm so impressed.

What she said.

Gee.. thanks. (As long as you aren't being sarcastic..) I was very happy to see and work on a math problem like that (haven't done so in nearly a year).

m: No, I'm totally serious.