Numbers as Programs:
The Power of Digit Sequences

Eric Rowland

Rutgers University

Using digit sequences in computation

The base-k "digit sequence" of a number n is the sequence {(Subscript[n, l]),…,(Subscript[n, 1]),(Subscript[n, 0])} of its digits in base k.

The digit sequence of n can be thought of as a list of instructions — a program — that generates n, in the sense that n==(Subscript[n, l])(k^l)+⋯+(Subscript[n, 1])(k^1)+(Subscript[n, 0])(k^0)==FromDigits[{(Subscript[n, l]),…,(Subscript[n, 1]),(Subscript[n, 0])},k].

Table[FromDigits[IntegerDigits[n,2],2],{n,0,15}]

We use digit sequences to do arithmetic, and this can be thought of as using digits sequences as "programs".

But there are many other ways to interpret {(Subscript[n, l]),…,(Subscript[n, 1]),(Subscript[n, 0])} as a program that computes something interesting.

Binary exponentiation

An early (implicit) use of digit sequences as programs is the method of binary exponentiation known by Pingala in 200 BCE, in which the binary representation of n is used to efficiently compute (m^n) by repeated squaring.

TraditionalForm[ColumnWrap[Table[{Row[{n," == ",BaseForm[n,2]," == ",Fold[If[#2==0,2\[Cross]#1,2\[Cross]#1+1]&,1,Rest[IntegerDigits[n,2]]]}]},{n,15}],3,2,Alignment->"=="]]

Read the binary digits from left to right:  0 means "square", and 1 means "square and multiply by m".
(See pages 615 and 1093.)

TraditionalForm[ColumnWrap[Table[{Row[{(m^n)," == ",Fold[If[#2==0,PrecedenceForm[((#1)^2),0],((#1)^2)\[Cross]m]&,m,Rest[IntegerDigits[n,2]]]}]},{n,15}],3,8,Alignment->"=="]]

The Fibonacci sequence

The nth Fibonacci number can be computed quickly from the base-2 digit sequence of n.  (See page 890.)

Fibonacci[100]

FoldList[#1/.{a_,b_,s_}:>If[#2==0,{a (a+2 b),a (2 a-b)+s,1},{(a+b) (a+2 b)-s,a (a+2 b),-1}]&,{1,0,-1},Rest[IntegerDigits[100,2]]]

Basically, we can compute Fibonacci[n] and Fibonacci[n-1] in terms of Fibonacci[m] and Fibonacci[m-1], where m==FromDigits[Most[IntegerDigits[n,2]],2].

If n is even, then…
Fibonacci[n]==Fibonacci[2m]==Fibonacci[m](Fibonacci[m]+2Fibonacci[m-1]) Fibonacci[n-1]==Fibonacci[2m-1]==Fibonacci[m](2Fibonacci[m]-Fibonacci[m-1])+(((-1))^m)

If n is odd, then…
Fibonacci[n]==Fibonacci[2m+1]==(Fibonacci[m]+Fibonacci[m-1])(Fibonacci[m]+2Fibonacci[m-1])-(((-1))^m) Fibonacci[n-1]==Fibonacci[2m]==Fibonacci[m](Fibonacci[m]+2Fibonacci[m-1])

FullSimplify[Fibonacci[2 m]==Fibonacci[m] (Fibonacci[m]+2 Fibonacci[m-1]),m∈Integers]

FullSimplify[Fibonacci[2 m-1]==Fibonacci[m] (2 Fibonacci[m]-Fibonacci[m-1])+(((-1))^m),m∈Integers]

FullSimplify[Fibonacci[2 m+1]==(Fibonacci[m]+Fibonacci[m-1]) (Fibonacci[m]+2 Fibonacci[m-1])-(((-1))^m),m∈Integers]

FullSimplify[Fibonacci[2 m]==Fibonacci[m] (Fibonacci[m]+2 Fibonacci[m-1]),m∈Integers]

Pascal's triangle

In 1852, Kummer discovered his famous result stating that the highest power to which a prime p divides Binomial[n,m] is the number of carries used when adding m and n-m in base p. There have subsequently been several generalizations of this result, also relying on digit sequences.

ArrayPlot[Table[IntegerExponent[Binomial[n,m],2],{n,0,127},{m,0,n}]]

Automatic sequences

A k-automatic sequence is a sequence of numbers for which the nth term is computed by feeding the base-k digits of n into a finite automaton.

The Thue–Morse sequence

The Thue–Morse sequence is defined as the parity of the number of 1s in the binary representation of n.  It is 2-automatic.

Table[Mod[Total[IntegerDigits[n,2]],2],{n,0,15}]

The Thue–Morse sequence is generated by the following finite automaton.

GraphPlot[{{1->1,Style["0",17]},{1->0,Style["1",17]},{0->1,Style["1",17]},{0->0,Style["0",17]}}/.{1->Style["state 1",15],0->Style["state 0",15]},DirectedEdges->True,SelfLoopStyle->.2,VertexLabeling->True]

Table[Fold[{##1}/.{{0,0}->0,{0,1}->1,{1,0}->1,{1,1}->0}&,0,Reverse[IntegerDigits[n,2]]],{n,0,15}]

The Thue–Morse sequence

The first (2^10) entries in the Thue–Morse sequence:

ArrayPlot[Partition[Table[Mod[Total[IntegerDigits[n,2]],2],{n,0,1023}],32]]

Generalization

Automatic sequences necessarily take on only finitely many values.  It would be nice to generalize them to include related sequences that take on infinitely many values.  For example…

Examples

How many times does 1 appear in the binary representation of n?

Table[DigitCount[n,2,1],{n,0,15}]

ListLinePlot[DigitCount[Range[0,63],2,1],ImageSize->300]

Examples

What is the sum of the first n terms of the Thue–Morse sequence?

Accumulate[ThueMorse[Range[0,15]]]

ListLinePlot[Accumulate[ThueMorse[Range[0,63]]],ImageSize->300]

Examples

How many times does 2 divide n?

Table[IntegerExponent[n,2],{n,15}]

ListLinePlot[IntegerExponent[Range[64],2],ImageSize->300]

Examples

How many black cells are there on each row of rule 90?

ArrayPlot[CellularAutomaton[90,{{1},0},(2^8)-1],ImageSize->300]

Total/@CellularAutomaton[90,{{1},0},15]

ListLinePlot[Total/@CellularAutomaton[90,{{1},0},63],ImageSize->300]

Toward a generalization

Let's dissect the Thue–Morse sequence...

With[{f=ThueMorse},Manipulate[Graphics[{Text["->",{-1,1}],Style[Table[Text[f[n],{n,1}],{n,0,31}],Bold],Table[Text[f[n],Which[t≤0,{n,-t},t≤1,{n,0},t≤2,{(1/2) n (3-t),0},True,{(n/2),0}]],{n,0,63,2}],If[t<2,Table[Text[f[n],Which[t≤1,{n,-t},t≤2,{(1/2) (n+1) (3-t)-1,-1},True,{((n-1)/2),-1}]],{n,1,63,2}],{Text["->",{-1,-1}],Style[Table[Text[f[n],{((n-1)/2),-1}],{n,1,63,2}],Bold],Table[Text[f[n],Which[t≤3,{((n-1)/2),1-t},t≤4,{((n-1)/2),-2},t≤5,{(1/4) (n-1) (6-t),-2}]],{n,1,127,4}],Table[Text[f[n],If[t≤4,{((n-1)/2),1-t},{(1/4) (n+1) (6-t)-1,-3}]],{n,3,127,4}]}]},PlotRange->{{-1.5,31.5},{-3.5,1.5}}],{{t,-1,"1"},-1,2,Trigger,AppearanceElements->{"PlayButton","PauseButton","ResetButton"},DefaultDuration->4},{{t,-1,"2"},2,5,Trigger,AppearanceElements->{"PlayButton","PauseButton","ResetButton"},DefaultDuration->4},AppearanceElements->None,ControlPlacement->Left]]

When we repeatedly take "every other term" subsequences, there are only a finite number of sequences that occur.

Toward a generalization

Now let's do the same with the number of 1s in binary:

With[{f=DigitCount[#1,2,1]&},Manipulate[Graphics[{Text["->",{-1,1}],Style[Table[Text[f[n],{n,1}],{n,0,31}],Bold],Table[Text[f[n],Which[t≤0,{n,-t},t≤1,{n,0},t≤2,{(1/2) n (3-t),0},True,{(n/2),0}]],{n,0,63,2}],If[t<2,Table[Text[f[n],Which[t≤1,{n,-t},t≤2,{(1/2) (n+1) (3-t)-1,-1},True,{((n-1)/2),-1}]],{n,1,63,2}],{Text["->",{-1,-1}],Style[Table[Text[f[n],{((n-1)/2),-1}],{n,1,63,2}],Bold],Table[Text[f[n],Which[t≤3,{((n-1)/2),1-t},t≤4,{((n-1)/2),-2},t≤5,{(1/4) (n-1) (6-t),-2},True,{((n-1)/4),-2}]],{n,1,127,4}],Text["->",{-1,-1}],Style[Table[Text[f[n],Which[t≤4,{((n-1)/2),1-t},t≤5,{(1/4) (n+1) (6-t)-1,-3},True,{((n-3)/4),-3}]],{n,3,127,4}],If[t≤5,None,Bold]],If[t≤5,{},{Text["->",{-1,-3}],Text["⋮",{15,-5}]}]}]},PlotRange->{{-1.5,31.5},{-5.5,1.5}}],{{t,-1,"1"},-1,2,Trigger,AppearanceElements->{"PlayButton","PauseButton","ResetButton"},DefaultDuration->4},{{t,-1,"2"},2,5.1,Trigger,AppearanceElements->{"PlayButton","PauseButton","ResetButton"},DefaultDuration->4.13},AppearanceElements->None,ControlPlacement->Left]]

We will continue to get a new sequence at every step.  But these sequences are very closely related; in fact every sequence is a linear combination of the first two.

seq00=Table[DigitCount[n,2,1],{n,0,15,1}]

seq11=Table[DigitCount[n,2,1],{n,1,31,2}]

2 seq11-seq00

So a natural generalization is to consider sequences for which repeatedly taking "every other term" subsequences eventually results in sequences all of which are linear combinations of previous ones.

Regular sequences

A k-regular sequence is a sequence a(n) of numbers for which there are finitely many sequences such that each subsequence a((k^e)n+r) (for e≥0, 0≤r<(k^e)) is a linear combination of them.

With some linear algebra, one can construct a machine model for regular sequences.
Assign an r×r matrix to each number 0,1,…,k-1.  Then replace each base-k digit d by the corresponding matrix (Subscript[μ, d]), and multiply them all together.  Finally, multiply by a certain row vector λ on the left and a certain column vector κ on the right.

Examples of regular sequences

For example, the sequence that counts the number of 1s in binary is given by (Subscript[μ, 0])=(({{1, 0}, {0, 1}})) and (Subscript[μ, 1])=(({{0, 1}, {-1, 2}})), with λ=(({{1, 0}})) and κ=(({{0}, {1}})).

TraditionalForm[Column[With[{matrices={{{1,0},{0,1}},{{0,1},{-1,2}}}},Table[a[n]==a[BaseForm[n,2]]==CenterDot@@Join[{{{1,0}}},matrices[[IntegerDigits[n,2]+1]],{{{0},{1}}}]=={1,0}.Dot@@matrices[[IntegerDigits[n,2]+1]].{0,1},{n,0,7}]],Alignment->"=="]]

Table[DigitCount[n,2,1],{n,0,7}]

RegularRepresentation[DigitCount[Range[0,63],2,1],2,MatrixForm->True]

Examples of regular sequences

The sum of the first n terms of the Thue–Morse sequence:

Accumulate[ThueMorse[Range[0,15]]]

ListLinePlot[Accumulate[ThueMorse[Range[0,63]]],ImageSize->300]

RegularRepresentation[Accumulate[ThueMorse[Range[0,31]]],2,MatrixForm->True]

Examples of regular sequences

The number of times that 2 divides n:

Table[IntegerExponent[n,2],{n,15}]

ListLinePlot[IntegerExponent[Range[64],2],ImageSize->300]

RegularRepresentation[IntegerExponent[Range[64],2],2,MatrixForm->True]

More examples of regular sequences

How many times does 2 divide n!?

Table[IntegerExponent[n!,2],{n,0,15}]

ListLinePlot[IntegerExponent[Range[0,63]!,2],ImageSize->300]

RegularRepresentation[IntegerExponent[Range[0,31]!,2],2,MatrixForm->True]

More examples of regular sequences

How many times does 2 divide the nth Fibonacci number?

Table[IntegerExponent[Fibonacci[n],2],{n,16}]

ListLinePlot[IntegerExponent[Fibonacci[Range[64]],2],ImageSize->300,PlotRange->All]

RegularRepresentation[IntegerExponent[Fibonacci[Range[(2^7)]],2],2,MatrixForm->True]

More examples of regular sequences

How many numbers ≤n can be written as the sum of three squares?

Accumulate[Table[Boole[Length[PowersRepresentations[n,3,2]]>0],{n,0,15}]]

ListLinePlot[Accumulate[Table[Boole[Length[PowersRepresentations[n,3,2]]>0],{n,0,63}]],ImageSize->300]

RegularRepresentation[Accumulate[Table[Boole[Length[PowersRepresentations[n,3,2]]>0],{n,0,(2^6)}]],2,MatrixForm->True]

Additive cellular automata

Regular sequences come up very frequently when one studies additive cellular automata.

Animate[ArrayPlot[CellularAutomaton[150,{Normal[SparseArray[{1->1,t->1}]],0},{127,All}],Frame->None,PixelConstrained->1],{{t,1,""},1,30,1},AnimationDirection->ForwardBackward]

Some additive cellular automata:

GraphicsGrid[{(Tooltip[ArrayPlot[CellularAutomaton[#1,{{1},0},{(2^8)-1,All}],ImageSize->350],#1]&)/@{90,150},(Tooltip[ArrayPlot[CellularAutomaton[{#1,2,(3/2)},{{1},0},{(2^8)-1,All}],ImageSize->350],#1]&)/@{27030,39270}}]

Rows

How many black cells are on each row?

RegularRepresentation[Total/@CellularAutomaton[90,{{1},0},(2^5)-1],2,MatrixForm->True]

RegularRepresentation[Total/@CellularAutomaton[150,{{1},0},(2^5)-1],2,MatrixForm->True]

RegularRepresentation[Total/@CellularAutomaton[{27030,2,(3/2)},{{1},0},(2^5)-1],2,MatrixForm->True]

RegularRepresentation[Total/@CellularAutomaton[{39270,2,(3/2)},{{1},0},(2^6)-1],2,MatrixForm->True]

Columns

What is the sequence of cells in a particular column of rule 90?

ArrayPlot[CellularAutomaton[90,{{1},0},(2^4)-1],ImageSize->100]

They are all 2-automatic sequences.

RegularRepresentation[CellularAutomaton[90,{{1},0},{(2^5)-1,{{0}}}],2,MatrixForm->True]

RegularRepresentation[CellularAutomaton[90,{{1},0},{(2^5)-1,{{1}}}],2,MatrixForm->True]

RegularRepresentation[CellularAutomaton[90,{{1},0},{(2^5)-1,{{2}}}],2,MatrixForm->True]

RegularRepresentation[CellularAutomaton[90,{{1},0},{(2^5)-1,{{3}}}],2,MatrixForm->True]

Columns

How does the "rank" of each 2-automatic sequence grow?

ListLinePlot[Transpose[{Range[-31,31],(Length[First[RegularRepresentation[#1,2]]]&)/@Transpose[CellularAutomaton[90,{{1},0},{(2^11)-1,{-31,31}}]]}]]

It turns out that this sequence is 2-regular!  Its rank is 6.

RegularRepresentation[{1,2,3,4,4,5,5,5,5,6,6,6,6,7,6,7,6,8,7,8,7,8,7,8,7,9,8,9,7,9,8,9,7,10,9,10,8,10,9,10,8,10,9,10,8,10,9,10,8,11,10,11,9,11,10,11,8,11,10,11,9,11,10,11,8,12,11,12,10,12,11,12,9,12,11,12,10,12,11,12,9,12,11,12,10,12,11,12,9,12,11,12,10,12,11,12,9,13,12,13,11,13,12,13,10,13,12,13,11,13,12,13,9,13,12,13,11,13,12,13,10,13,12,13,11,13,12,13,9,14,13,14,12,14,13,14,11,14,13,14,12,14,13,14,10,14,13,14,12,14,13,14,11,14,13,14,12,14,13,14,10,14,13,14,12,14,13,14,11,14,13,14,12,14,13,14,10,14,13,14,12,14,13,14,11,14,13,14,12,14,13,14,10,15,14,15,13,15,14,15,12,15,14,15,13,15,14,15,11,15,14,15,13,15,14,15,12,15,14,15,13,15,14,15,10,15,14,15,13,15,14,15,12,15,14,15,13,15,14,15,11,15,14,15,13,15,14,15,12,15,14,15,13,15,14,15},2,MatrixForm->True]

Columns

A similar fact holds for rule 150.  The rank in this case is 8.

ListLinePlot[Transpose[{Range[-31,31],(Length[First[RegularRepresentation[#1,2]]]&)/@Transpose[CellularAutomaton[150,{{1},0},{(2^11)-1,{-31,31}}]]}]]

RegularRepresentation[{1,2,3,4,4,5,5,5,5,6,6,6,6,7,6,7,6,8,7,8,7,9,7,9,7,9,8,9,7,9,8,9,7,10,9,10,8,11,9,11,8,11,10,11,8,10,10,10,8,11,10,11,9,12,10,12,8,12,10,12,9,11,10,11,8,12,11,12,10,14,11,14,9,14,12,14,10,12,12,12,9,13,12,13,11,14,12,14,9,14,11,14,11,13,11,13,9,13,12,13,11,15,12,15,10,15,13,15,11,13,13,13,9,13,13,13,11,15,13,15,10,15,12,15,11,13,12,13,9,14,13,14,12,17,13,17,11,17,15,17,12,14,15,14,10,15,15,15,13,17,15,17,11,17,13,17,13,15,13,15,10,15,14,15,13,17,14,17,12,17,15,17,13,15,15,15,10,14,15,14,12,17,15,17,12,17,14,17,12,14,14,14,10,15,14,15,13,18,14,18,12,18,16,18,13,15,16,15,11,16,16,16,14,18,16,18,12,18,14,18,14,16,14,16,10,16,14,16,14,18,14,18,12,18,16,18,14,16,16,16,11,15,16,15,13,18,16,18,12,18,14,18,13,15,14,15},2,MatrixForm->True]

Rule numbers

What do the rule numbers look like for additive cellular automata?

This is the number of the 2-color, radius 5 rule that performs addition (of eleven cells) modulo 2:

r=;

The (reversed) binary digits of r are the first (2^11) terms of the Thue–Morse sequence.

Reverse[IntegerDigits[r,2]]==ThueMorse[Range[0,(2^11)-1]]

Primary references

Jean-Paul Allouche & Jeffrey Shallit, "The ring of k-regular sequences", Theoretical Computer Science 98 (1992) 163–197.

Stephen Wolfram, A New Kind of Science (Wolfram Media 2002).