A368747 Self-describing bit sequences from the beta transform.

0, 1, 2, 3, 4, 6, 7, 8, 10, 12, 13, 14, 15, 16, 20, 24, 25, 26, 28, 29, 30, 31, 32, 36, 40, 42, 48, 49, 50, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 72, 80, 82, 84, 96, 97, 98, 100, 101, 104, 105, 106, 108, 109, 112, 113, 114, 115, 116, 117, 118, 120

Offset: 0

Author

Linas Vepstas, Feb 06 2024

Keywords

• nonn

Comments

A bit sequence b_0, b_1, ..., b_k of the binary representation of an odd integer 2n+1 is self-describing if the largest real root beta of the monic polynomial p_n(x) = x^(k+1) - b_0 * x^k - b_1 * x^(k-1) - ... - b_k regenerates the same bit sequence when the beta transform t(x) = (beta * x) mod 1 is iterated for x=1, the generated bit being zero or one, depending on whether the modulo was taken or not. Not all integers n generate such self-describing polynomials; the sequence given here begins the list of valid self-describing polynomials.

The number of such valid polynomials of degree m is given by Moreau's necklace counting function A001037.

The bit sequences are not Lyndon words, and cannot be rotated, although there are the same number of them (given by the necklace function).

The bit sequences are not isomorphic to the irreducible polynomials over the field F_2 of two elements, although there are the same number of them (given by the necklace function).

Examples

			n=1 generates p_1(x) = x^2 - x - 1 whose largest real root is the golden mean A000045. Iteration of the golden mean under the beta transform terminates after two steps, and requires modulo-one to be applied at each step, thus giving the bit sequence 11.
n=2 generates a polynomial whose largest root is the limit of Narayana's A058265.
n=3 ... is the tribonacci limit A058265.
n=4 ... is the 2nd Pisot number A086106.
n=5 is not valid (not self-describing).
n=6 ... is A109134.
n=7 ... is the tetranacci limit A086088.
n=8 ... is the silver (plastic) number A060006.
n=9 is not valid (not self-describing).
n=10 ... is a Pisot number A293506.
n=11 is not valid (not self-describing).
Sequences corresponding to larger values of n are not (currently) in the OEIS, except when n = 2^m - 1, which are limits to the generalized Fibonacci numbers.
		

Links

• Linas Vepstas, Table of n, a(n) for n = 0..10000
• Linas Vepstas, On the Beta Transform, arXiv:1812.10593 [math.DS], 2018.

Formula

The binary representation for every integer 2n+1 encodes a polynomial p_n(x) but not all such polynomials have (positive, real) roots r_n that are self-describing. An integer n is valid if it is self-describing; the validity filter is theta_n(r_n) = 1 where theta_n(x) is recursively defined as theta_n(x) = theta_{n/2}(x) * (x < r_{n/2}) if n is even, and theta_n(x) = theta_{(n-1)/2}(x) if n is odd. The sequence starts with theta_0(x) = 1.