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