there are a lot of things you can compute by using digit sequences as programs.
method of binary exponentiation, pingala in 200 BC. binary sequence of n used to efficiently compute m^n.
the nth fibonacci number can be computed quickly from the base-2 digit sequence of n.
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. e.g. thue-morse sequence. eric showed a graphic of the first 2^10 entries in the thue-morse sequence.
generalization to automatic sequences. what if you want to find the number of 1's in the binary expansion of any number? the length of digits could by anything, so you need to generalize automatic sequences which only take finite inputs. what is the number of 1's on the nth row of rule 90?
dissect the thue-morse sequence. take every other term recursively. only a finite number of sequences occur. do the same thing with the sequence that counts the number of 1's in binary. get a new sequence at every step, where every sequence is a linear combination of the first two. this is a k-regular sequence. with k=3 you take every third term. use linear algebra to construct a machine model for regular sequences. associate a matrix with each number. replace every digit in the binary number with its respective matrix. eric showed the matrices generating the sum of the first n terms of the thue-morse sequence. the size of the matrices reflect the complexity of the problem. how many numbers less than or equal to n can be written as the sum of 3 squares?
additive CAs. how many black cells are on the nth row? for rule 90 it's a 2-regular sequence. eric conjectures that the solution for any additive CA is a regular sequence (he feels it's true, but doesn't have a proof yet). what is the sequence on a particular column of rule 90? these also always seem to be regular sequences. the rank of the 2 regular sequence corresponding to the nth column of rule 90 is *also* a 2-regular sequence (of rank 6). that result of eric's is only about a week old.
jason cawley suggested enumerating matrices and seeing what sequences they generate.
Comments