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

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, 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, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Comments

From Jean-Paul Allouche and Michel Dekking, Sep 08 2019: (Start)

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:

1 -> 322, 2 -> 1212, 3 -> 323232, 4 -> 412.

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.

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.

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.

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)).

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,...

is a purely morphic sequence, fixed point of the morphism 1 -> 123, 2 -> 212, 3 -> 1232323.

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.

(End)

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

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Claude Lenormand, Deux transformations sur les mots, 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.

Crossrefs

Cf. A010060, A026465, A080426.

Cf. A054977.

Programs

Haskell

import Data.List (group)
a026490 n = a026490_list !! (n-1)
a026490_list = map length $ group a026465_list
-- Reinhard Zumkeller, Jul 15 2014

Mathematica

Length /@ Split[Length /@ Split[ThueMorse[Range[0, 200]]]] (* Vladimir Reshetnikov, Apr 27 2016 *)

Python

def A026490(n):
    if n==1: return 1
    if n&1: return 2
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x):
        c, s = x, bin(x)[2:]
        l = len(s)
        for i in range(l&1,l,2):
            c -= int(s[i])+int('0'+s[:i],2)
        return c
    m = n>>1
    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

Formula

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