cp's OEIS Frontend

A339949 a(n) is the greatest runlength in all n-sections of the infinite Fibonacci word A014675.

%I A339949 #50 Feb 19 2025 12:06:40
%S A339949 2,3,5,6,7,3,2,12,4,4,4,4,18,2,3,6,20,5,3,2,30,4,3,4,4,9,2,3,9,4,4,3,
%T A339949 4,47,2,3,5,10,6,3,2,15,4,4,4,4,13,2,3,7,8,5,3,2,77,4,3,5,6,8,3,2,10,
%U A339949 4,4,3,4,24,2,3,6,78,6,3,2,22,4,3,4,4,11,2
%N A339949 a(n) is the greatest runlength in all n-sections of the infinite Fibonacci word A014675.
%C A339949 Equivalently a(n) is the greatest runlength in all n-sections of the infinite Fibonacci word A003849.
%C A339949 From _Jeffrey Shallit_, Mar 23 2021: (Start)
%C A339949 We know that the Fibonacci word has exactly n+1 distinct factors of length n.
%C A339949 So to verify a(n) we simply verify there is a monochromatic arithmetic progression of length a(n) and difference n by examining all factors of length (n*a(n) - n + 1) (and we know when we've seen all of them). Next we verify there is no monochromatic AP of length a(n)+1 and difference n by examining all factors of length n*a(n) + 1.
%C A339949 Again, we know when we've seen all of them. (End)
%H A339949 Gandhar Joshi, <a href="/A339949/b339949.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..232 from Jeffrey Shallit).
%H A339949 Dmitry Badziahin and Jeffrey Shallit, <a href="https://arxiv.org/abs/2006.15842">Badly approximable numbers, Kronecker's theorem, and diversity of Sturmian characteristic sequences</a>, arXiv:2006.15842 [math.NT], 2020.
%H A339949 Gandhar Joshi and Dan Rust, <a href="https://arxiv.org/abs/2501.05830">Monochromatic arithmetic progressions in the Fibonacci word</a>, arXiv:2501.05830 [math.NT], 2025. See p. 9.
%F A339949 From _Gandhar Joshi_, Jan 14 2025: (Start)
%F A339949 phi = the golden ratio. g(n) = min {n*phi mod 1, 1 - (n*phi mod 1)}.
%F A339949 If g(n) <= (phi)^(-2), a(n) = ceiling{((phi)^(-1))/g(n)};
%F A339949 otherwise, a(n) = 2*ceiling{((phi)^(-1)-g(n))/g(2n)}. (End)
%e A339949 For n  >= 1,  r =  0..n, k >= 0, let A014675(n*k+r) denote the k-th term of the r-th n-section of A014675; i.e.,
%e A339949 (A014675(k)) = 212212122122121221212212212122122121221212212212122121...
%e A339949   has runlengths 1,1,2,1,1,1,2,1,2,1,...; a(1) = 2.
%e A339949 (A014675(2k)) = 22112211222122212221122112221222122211221122112221222...
%e A339949   has runlengths 2,2,2,2,3,1,3,1,3,2,...
%e A339949 (A014675(2k+1)) = 122212221122112211222122211221122112221222122211221...
%e A339949    has runlengths 1,3,1,3,2,2,2,2,2,3,...; a(2) = 3.
%e A339949 (A014675(3k)) = 22111222211122221122222112222211222211122221112222111...
%e A339949   has runlengths 2,3,4,3,4,2,5,2,5,2,4,3,4,3,...
%e A339949 (A014675(3k+1)) = 112222111222211122221112222111222211222221122221112...
%e A339949   has runlengths 2,4,3,4,3,4,3,4,3,4,,5,2,4,3,...
%e A339949 (A014675(3k+2)) = 222211222221122221112222111222211122221112222112222...
%e A339949   has runlengths 4,2,5,2,4,3,4,3,4,3,4,3,4,2,...; a(3) = 5.
%t A339949 r = (1 + Sqrt[5])/2; z = 4000;
%t A339949 f[n_] := Floor[(n + 2) r] - Floor[(n+1) r];  (* A014675 *)
%t A339949 t = Table[Max[Map[Length,Union[Split[Table [f[n m], {n, 0, Floor[z/m]}]]]]], {m, 1, 20}, {n, 1, m}];
%t A339949 Map[Max, t] (* A339949 *)
%o A339949 (PARI)
%o A339949 phi = quadgen(5);
%o A339949 g(n) = min(frac(n * phi), 1 - frac(n * phi));
%o A339949 a(n) = if (g(n) <= (1 / phi)^2, ceil((1 / phi) / g(n)), 2*ceil(((1 / phi) - g(n)) / g(2 * n))); \\ _Gandhar Joshi_, Jan 14 2025
%Y A339949 Cf. A001622, A003849, A014675, A339950.
%K A339949 nonn,easy
%O A339949 1,1
%A A339949 _Clark Kimberling_, Dec 26 2020
%E A339949 a(61) corrected by _Jeffrey Shallit_, Mar 23 2021