Incidently, A126364 has a rational generating function (and equivalently a linear recurrence). Note that the base 3 equivalent is A078057 (essentially the same as A001333). Franklin T. Adams-Watters