A080426 a(1)=1, a(2)=3; all terms are either 1 or 3; each run of 3's is followed by a run of two 1's; and a(n) is the length of the n-th run of 3's.

1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1

Offset: 1

Author

John W. Layman, Feb 18 2003

Keywords

• nonn

Comments

It appears that the sequence can be calculated by any of the following three methods: (1) Start with 1 and repeatedly replace (simultaneously) all 1's with 1,3,1 and all 3's with 1,3,3,3,1. [Equivalently, trajectory of 1 under the morphism 1 -> 1,3,1; 3 -> 1,3,3,3,1. - N. J. A. Sloane, Nov 03 2019] (2) a(n)= A026490(2n). (3) Replace each 2 in A026465 (run lengths in Thue-Morse) with 3.

Length of n-th run of 1's in the Feigenbaum sequence A035263 = 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, .... - Philippe Deléham, Apr 18 2004

Another construction. Let S_0 = 1, and let S_n be obtained by applying the morphism 1 -> 3, 3 -> 113 to S_{n-1}. The sequence is the concatenation S_0, S_1, S_2, ... - D. R. Hofstadter, Oct 23 2014

a(n+1) is the number of times n appears in A003160. - John Keith, Dec 31 2020

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, CNRS France, 2024. See pp. 5-6.
• Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
• D. R. Hofstadter, Anti-Fibonacci numbers, Oct 23 2014.

Crossrefs

Cf. A026465, A026490, A035263, A003156, A328979, A003160.

Arises in the analysis of A075326, A249031 and A249032.

Programs

Haskell

-- following Deléham
import Data.List (group)
a080426 n = a080426_list !! n
a080426_list = map length $ filter ((== 1) . head) $ group a035263_list
-- Reinhard Zumkeller, Oct 27 2014

Mathematica

Position[ Nest[ Flatten[# /. {0 -> {0, 2, 1}, 1 -> {0}, 2 -> {0}}]&, {0}, 8], 0] // Flatten // Differences // Prepend[#, 1]& (* Jean-François Alcover, Mar 14 2014, after Philippe Deléham *)
nsteps=7;Flatten[SubstitutionSystem[{1->{3},3->{1,1,3}},{1},nsteps]] (* Paolo Xausa, Aug 12 2022, using D. R. Hofstadter's construction *)

PARI

A080426(nmax) = my(a=[1], s=[[1, 3, 1], [], [1, 3, 3, 3, 1]]); while(length(a)A080426(100) \\ Paolo Xausa, Sep 14 2022, using method (1) from comments

Python

def A080426(nmax):
    a, s = "1", "".maketrans({"1":"131", "3":"13331"})
    while len(a) < nmax: a = a.translate(s)
    return list(map(int, a[:nmax]))
print(A080426(100)) # Paolo Xausa, Aug 30 2022, using method (1) from comments

Python

def A080426(n):
    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
    return bisection(lambda x:f(x)+n,n,n)-bisection(lambda x:f(x)+n-1,n-1,n-1)-1 # Chai Wah Wu, Jan 29 2025

Formula

a(1) = 1; for n>1, a(n) = A003156(n) - A003156(n-1). - Philippe Deléham, Apr 16 2004