Using Finite Automata to Compute the Base-b Representation of the Golden Ratio and Other Quadratic Irrationals
摘要
We show that the nth digit of the base-b representation of the golden ratio is a finite-state function of the Zeckendorf representation of \(b^n\) , and hence can be computed by a finite automaton. Similar results can be proven for any quadratic irrational. We use a satisfiability (SAT) solver to prove, in some cases, that the automata we construct are minimal.