From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: question- hard to say in one line. [Strings of digits]
Date: 24 Oct 1995 04:43:04 GMT
>Andrew W Heckman (drchem@iastate.edu) wrote:
>: How do u arrange a string of numbers such that the consecutive digits in
>: the string would together include numbers 1 to 1000, with the string as
>: short as possible?
The original message has rolled off my system, but I thought
I would pursue the question a bit. Clearly there is a
3001-digit string which will suffice (001002003...9991000), and
something like 1000 digits are necessary (maybe a little fewer,
since we really only have to ensure all the integers 101,...,1000
are included -- these include the smaller numbers as substrings).
The purpose of this note is to show that in fact there is a
sequence of precisely 1000 digits which has the necessary properties.
Apart from the question of how we wish to include integers with
leading 0's, this is then the best result possible.
Here is the sequence:
70797802125994225691148612397004543910429033344078
77362296395080363758485611380414917448763556067695
18607271108238793864765552029235762094977064169316
28925590489659740838995282781774689053586870393066
18359644129932685015126456315222165378829831926050
75742852175444725196643617342054593460929538849073
72867291340030313208985116885419962498713006567190
68107776603233748814715002529730267099922014119866
78975040989154245833940232731224189558081875348016
13304694179482185510621451360272115828329336421055
70247857120494775646143112847059548410979088349578
22367796845035368258935666385914467493768056517640
18157226103738243819760052579280767594427019164816
73920090939604745338445237786274139008581370843011
18809699124432135060121956865277160878379886921550
20747352625499720696193662347554043415924038399028
72317246345530863253980616335464967998263051562690
13102276153288743314265057524230717044927514669811
78425095984654795888945732281279184058531820343516
68309194629437180010171406365772665873324836971000
What follows is a discussion of how to create such a sequence.
Let the nth digit be a_n. Then we are looking for a sequence of
integers a_n in Z_10 such that every integer between 1 and 1000
occurs as x_n = 100*a_n + 10*a_(n+1) + a_(n+2) for some n >= 1.
Let me try to arrange the digits a_n so that there is as little
repitition in the above sequence as possible. Indeed, suppose I can
arrange it so that the simultaneous equations
a_n = a_m
a_(n+1)= a_(m+1)
a_(n+2)= a_(m+2)
imply n=m if 1 <= n,m <= 1000. Then the first thousand three-digit
combinations are all distinct, and so must cover all possibilities
from 000 to 999. (We'll arrange for 1000 to be included too.)
My method for finding such a sequence will be to find these digits so that
(a_n, a_(n+1), a_(n+2)) = (a_n, a_(n+1), a_(n+2)) mod 2 iff n=m mod 8
and so that (a_n, a_(n+1), a_(n+2)) = (a_n, a_(n+1), a_(n+2)) mod 5
iff n=m mod 125. This will accomplish what I suggested in the previous
paragraph.
This is really standard stuff in linear recurrence relations. If you
pick a few starting values for a_1, a_2, a_3 and then determine further
a_n with a recurrence relation a_(n+3) = r1 a_(n+2) + r2 a_(n+1) + r3 a_n,
then the triples (a_(n+2), a_(n+1), a_n) follow each from the previous
by multiplication by the companion matrix
( r1 r2 r3 )
( 1 0 0 )
( 0 1 0 )
which we call A so that the n'th triple is A^n v (with v = (a_3,a_2,a_1).)
Then two triples are equal iff A^n v = A^m v, i.e. iff v is an eigenvector
of A^(n-m) with eigenvalue 1. (I will assume r3 <>0 so that A is
non-singular. Then over any field it is invertible. We use the fields Z_2
and Z_5.) On the other hand, the eigenvalues of A are the roots of
the characteristic polynomial X^3 - r1 X^2 - r2 X - r3, and the eigenvalues
of A^(n-m) are powers of these. So what we do is to choose r1, r2, r3
so that the eigenvalues have the maximum possible multiplicative order.
This requires choosing the r_i to make the polynomials irreducible and
to have their roots be primitive roots of the extension field GF(p^3)
they generate. It is possible to do so, and the r_i will have order p^3-1.
With a little trial and error I find that the polynomial associated to
r1=0, r2=1, r3=1 works for p=2; for p=5, using r1=0, r2=1, r3=2 works.
In each case we may start, for example, with the sequence
a_1=0, a_2=0, a_3=1, although as I'll explain shortly, a_3=7 is better.
I adjust these sequences in just one way: between each of the sets of
p^3-1 integers I insert a zero. This gives me a sequence of p^3
terms such that two triples are equal iff they are spaced p^3 terms apart.
Thus I have these sequences a_0, a_1, ...
for p=2: 0 0 0 1 0 1 1 1 [repeat]
for p=5: 0 0 0 2 0 2 4 2 3 0 2 ... 2 4 3 3 1 4 2 1 [repeat]
Finally I choose the sequence of a_n in Z_10 to reduce to these
sequences mod 2 and mod 5. This is the sequence with a_0=a_1=a_2=0
followed by the thousand digits shown above, repeated ad infinitum.
By construction this will give me all 3-digit sequences. In particular, this
includes all the numbers from 000 to 999. The only pattern of 000 in
here occurs right at the beginning, and of course at a_1000=a_1001=a_1002=0.
By choosing to begin with a_3=7 rather than the more natural
a_3=1, we have arranged it so a_999=1. Thus we could skip the initial
zero terms a_0, a_1, and a_2 and adjoin the last three zero terms, and get
a sequence of precisely 1000 digits with everything required (assuming it's
OK to have the strings 7 and 70 instead of 007 and 070 at front).
dave