cp's OEIS Frontend

A368747 Self-describing bit sequences from the beta transform.

%I A368747 #36 Mar 02 2024 14:13:21
%S A368747 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,
%T A368747 42,48,49,50,52,53,54,56,57,58,59,60,61,62,63,64,72,80,82,84,96,97,98,
%U A368747 100,101,104,105,106,108,109,112,113,114,115,116,117,118,120
%N A368747 Self-describing bit sequences from the beta transform.
%C A368747 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.
%C A368747 The number of such valid polynomials of degree m is given by Moreau's necklace counting function A001037.
%C A368747 The bit sequences are not Lyndon words, and cannot be rotated, although there are the same number of them (given by the necklace function).
%C A368747 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).
%H A368747 Linas Vepstas, <a href="/A368747/b368747.txt">Table of n, a(n) for n = 0..10000</a>
%H A368747 Linas Vepstas, <a href="https://arxiv.org/abs/1812.10593">On the Beta Transform</a>, arXiv:1812.10593 [math.DS], 2018.
%F A368747 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.
%e A368747 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.
%e A368747 n=2 generates a polynomial whose largest root is the limit of Narayana's A058265.
%e A368747 n=3 ... is the tribonacci limit A058265.
%e A368747 n=4 ... is the 2nd Pisot number A086106.
%e A368747 n=5 is not valid (not self-describing).
%e A368747 n=6 ... is A109134.
%e A368747 n=7 ... is the tetranacci limit A086088.
%e A368747 n=8 ... is the silver (plastic) number A060006.
%e A368747 n=9 is not valid (not self-describing).
%e A368747 n=10 ... is a Pisot number A293506.
%e A368747 n=11 is not valid (not self-describing).
%e A368747 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.
%K A368747 nonn
%O A368747 0,3
%A A368747 _Linas Vepstas_, Feb 06 2024