Affinely recursive sets and orderings of languages. (English) Zbl 1091.68066
Summary: An affinely recursive set \(S\) consists of integers defined by these rules: \(1 \in S\), and if \(x \in S\), then \(f(x)\in S\) for every \(f\) in a prescribed set \(F\) of affine functions with integer coefficients. If these functions are indexed by a set \(A\), then each \(x\) in \(S\) except 1 corresponds to a word in the language \(L(A)\) of nonempty words over the alphabet \(A\). Conditions are found for the correspondence to be bijective, so that the ordering of numbers in \(S\) induces an ordering of \(L(A)\). Moreover, since each \(x\) except 1 in \(S\) is of the form \(f(y)\) for some \(y\) in \(S\) and \(f\) in \(F\), the set \(S\) is partitioned by \(F\). The partition extends to \(L(A)\); viz., a component consists of words that end in the same letter. The distribution and limiting density within \(S\) of the numbers in each component is considered.
Software:
OEISOnline Encyclopedia of Integer Sequences:
Odious numbers: numbers with an odd number of 1’s in their binary expansion.Numbers whose binary representation ends in an even number of zeros.
Fibbinary numbers: if n = F(i1) + F(i2) + ... + F(ik) is the Zeckendorf representation of n (i.e., write n in Fibonacci number system) then a(n) = 2^(i1 - 2) + 2^(i2 - 2) + ... + 2^(ik - 2). Also numbers whose binary representation contains no two adjacent 1’s.
Numbers whose ternary expansion contains no 1’s.
Numbers whose base-3 representation contains no 2.
Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.
Numbers whose ternary expansion contains no 0.
Natural numbers having an even number of nonleading zeros in their binary expansion.
References:
[1] | J.-P. Allouche, J.O. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in: C. Ding, T. Helleseth, H. Niederreiter (Eds.), Sequences and Their Applications: Proceedings of SETA ’98, Springer-Verlag, Berlin, 1999, pp. 1-16.; J.-P. Allouche, J.O. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in: C. Ding, T. Helleseth, H. Niederreiter (Eds.), Sequences and Their Applications: Proceedings of SETA ’98, Springer-Verlag, Berlin, 1999, pp. 1-16. · Zbl 1005.11005 |
[2] | Allouche, J.-P.; Shallit, J. O., The ring of \(k\)-regular sequences, Theoret. Comput. Sci., 98, 163-197 (1992) · Zbl 0774.68072 |
[3] | Guy, R., Unsolved Problems in Number Theory (1994), Springer-Verlag: Springer-Verlag Berlin · Zbl 0805.11001 |
[4] | N.J.A. Sloane, On-line Encyclopedia of Integer Sequences, http://www.research.att.com/njas/sequences; N.J.A. Sloane, On-line Encyclopedia of Integer Sequences, http://www.research.att.com/njas/sequences · Zbl 1274.11001 |
[5] | J. Tamura, Some problems and results having their origin in the power series \(Σ_n^{+∞}z^{[ αn }zn\); J. Tamura, Some problems and results having their origin in the power series \(Σ_n^{+∞}z^{[ αn }zn\) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.