Conference rusure::math

1191.0. "Sequence to cover all N-digit numbers" by VMSDEV::HALLYB (The Smart Money was on Goliath) Thu Feb 15 1990 12:39

    Various DIR commands failed to find mention of this problem.
    Find the shortest string that contains all possible two-digit
    decimal sequences.
    
    Find the shortest string that contains all possible 3-digit
    sequences.  Is there any way to generalize?
    
    This is reated to the background discussion below, from RISKS.
    
In RISKS-7.69 Vince Manis tells us that his General Electric
answering machine has only 256 possible access codes for remote
message retrieval.  I have the same machine.  Valid combinations
are 3 consecutive touch tones of the form [0-7][0-7][0-3].
 
In RISKS-7.73 William Curtiss points out that most answering
machines just ignore digits until you get the correct security
code.  "As long as the incoming stream contains the code
somewhere you are given access.  Since 256 combinations needs
three digits, a carefully constructed string of 258 digits will
contain every possible combination (for example, if the code is
a triplet composed of just the numbers 1 and 2 then the string
1211122212 contains all eight triplets)."
 
The shortest string of digits that I was able to generate for
defeating my answering machine was 452 digits:
 
000100200301101201302102202303103203304004104204305005105205
306006106206307007107207311121131221231321331401411421431501
511521531601611621631701711721732223233240241242243250251252
253260261262263270271272273330034034134234335035135235336036
136236337037137237344044144244345045145245346046146246347047
147247354054154254355055155255356056156256357057157257364064
164264365065165265366066166266367067167267307407417427437507
51752753760761762763770771772773
 
DTMF decoding chips are required to recognize a tone as short
as 50 milliseconds with an interdigit interval of another 50
milliseconds, making a total of 100 ms for each digit.  So the
whole 452 digit string could be dialed within 45.2 seconds
using a demon dialer.  Since my answering machine will wait a
minute or more while you leave a message, it could be cracked
with just one phone call.
 
Can anyone suggest an algorithm to generate a shorter string
than I have above, or better yet, an optimal string?  A string
length of 258 digits is a lower bound, but is there necessarily
a solution that short?
 
I checked more than a dozen different answering machines on the
market that allow remote message retrieval using touch tones, and
the best let you select combinations of the form [0-9][0-9][0-9].
A key space of 1000 combinations is hardly any improvement.
 
Denis Coskun    dcoskun%alias@csri.utoronto.ca   utcsri!alias!dcoskun

    See note 277.  I've added the keyword MEANDER to these notes.