cp's OEIS Frontend

A026490 Length of n-th run of identical symbols in A026465.

%I A026490 #55 Apr 21 2025 08:37:20
%S A026490 1,1,2,3,2,1,2,1,2,3,2,3,2,3,2,1,2,1,2,3,2,1,2,1,2,3,2,1,2,1,2,3,2,3,
%T A026490 2,3,2,1,2,1,2,3,2,3,2,3,2,1,2,1,2,3,2,3,2,3,2,1,2,1,2,3,2,1,2,1,2,3,
%U A026490 2,1,2,1,2,3,2,3,2,3,2,1,2,1,2,3,2,1,2,1,2,3
%N A026490 Length of n-th run of identical symbols in A026465.
%C A026490 From _Jean-Paul Allouche_ and _Michel Dekking_, Sep 08 2019: (Start)
%C A026490 This sequence is a morphic sequence, i.e., the letter to letter image of a fixed point of a morphism. The morphism is defined on a four-letter alphabet:
%C A026490     1 -> 322, 2 -> 1212, 3 -> 323232, 4 -> 412.
%C A026490 The letter-to-letter map is given by 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 1. The fixed point is the fixed point with prefix 4.
%C A026490 How is this obtained? Note that A026465 only has runs of the forms 2, 11 and 222. A026465 itself is the fixed point of the morphism alpha: 1 -> 121, 2 -> 12221.
%C A026490 The images of the runs under alpha are alpha(2) = 12221, alpha(11) = 121121, alpha(222) = 122211222112221. Coding the runs with their lengths this induces a morphism on the coded runs: 1 -> 32, 2 -> 1212, 3 -> 323232.
%C A026490 Here we use the fact that all three alpha-images have 1 as a prefix and as a suffix. This yields the 2 (coding of 11) at the end of the three images 32, 1212, 323232. The letter 4 is then added to deal with the somewhat strange fact that a(1)=1, a(2)=1. Strange, because the word 11 occurs nowhere else in (a(n)).
%C A026490 Actually, one can show in a similar way, using the square of the morphism 1 -> 2, 2 -> 211 instead of the morphism alpha, that (a(n+1)) = 1,2,3,2,1,2,...
%C A026490 is a purely morphic sequence, fixed point of the morphism 1 -> 123, 2 -> 212, 3 -> 1232323.
%C A026490 One sees from this (by projecting 1, 3 -> 1, 2 -> 2) that (a(n)) has the property a(2n+1) = 2 for all n > 1. Also, by removing the 2's, one sees that the sequence of 1's and 3's is the fixed point of the morphism 1 -> 131, 3 -> 13331, which is the sequence A080426.
%C A026490 (End)
%C A026490 Because the absolute difference between any pair of adjacent terms is 1 (excluding the first pair of adjacent terms), the length of n-th runs of this sequence is A054977, that is, 2 followed by an infinite sequence of 1's. - _Keith J. Bauer_, Feb 10 2024
%H A026490 Reinhard Zumkeller, <a href="/A026490/b026490.txt">Table of n, a(n) for n = 1..10000</a>
%H A026490 Claude Lenormand, <a href="/A318921/a318921.pdf">Deux transformations sur les mots</a>, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003. - _N. J. A. Sloane_, Sep 09 2018. See page 2.
%F A026490 a(1)=1, a(2n) = A080426(n) for all n > 0, a(2n+1) = 2 for all n > 1. - _Jean-Paul Allouche_ and _Michel Dekking_, Sep 08 2019
%t A026490 Length /@ Split[Length /@ Split[ThueMorse[Range[0, 200]]]] (* _Vladimir Reshetnikov_, Apr 27 2016 *)
%o A026490 (Haskell)
%o A026490 import Data.List (group)
%o A026490 a026490 n = a026490_list !! (n-1)
%o A026490 a026490_list = map length $ group a026465_list
%o A026490 -- _Reinhard Zumkeller_, Jul 15 2014
%o A026490 (Python)
%o A026490 def A026490(n):
%o A026490     if n==1: return 1
%o A026490     if n&1: return 2
%o A026490     def bisection(f,kmin=0,kmax=1):
%o A026490         while f(kmax) > kmax: kmax <<= 1
%o A026490         kmin = kmax >> 1
%o A026490         while kmax-kmin > 1:
%o A026490             kmid = kmax+kmin>>1
%o A026490             if f(kmid) <= kmid:
%o A026490                 kmax = kmid
%o A026490             else:
%o A026490                 kmin = kmid
%o A026490         return kmax
%o A026490     def f(x):
%o A026490         c, s = x, bin(x)[2:]
%o A026490         l = len(s)
%o A026490         for i in range(l&1,l,2):
%o A026490             c -= int(s[i])+int('0'+s[:i],2)
%o A026490         return c
%o A026490     m = n>>1
%o A026490     return bisection(lambda x:f(x)+m,m,m)-bisection(lambda x:f(x)+m-1,m-1,m-1)-1 # _Chai Wah Wu_, Jan 29 2025
%Y A026490 Cf. A010060, A026465, A080426.
%Y A026490 Cf. A054977.
%K A026490 nonn
%O A026490 1,3
%A A026490 _Clark Kimberling_