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