A003156 A self-generating sequence (see Comments for definition).

1, 4, 5, 6, 9, 12, 15, 16, 17, 20, 21, 22, 25, 26, 27, 30, 33, 36, 37, 38, 41, 44, 47, 48, 49, 52, 55, 58, 59, 60, 63, 64, 65, 68, 69, 70, 73, 76, 79, 80, 81, 84, 85, 86, 89, 90, 91, 94, 97, 100, 101, 102, 105, 106, 107, 110, 111, 112, 115, 118, 121, 122, 123, 126, 129, 132

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

From N. J. A. Sloane, Dec 26 2020: (Start)

The best definitions of the triple [this sequence, A003157, A003158] are as the rows a(n), b(n), c(n) of the table:

n: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...

a: 1, 4, 5, 6, 9, 12, 15, 16, 17, 20, 21, 22, ...

b: 3, 8, 11, 14, 19, 24, 29, 32, 35, 40, 43, 46, ...

c: 2, 7, 10, 13, 18, 23, 28, 31, 34, 39, 42, 45, ...

where a(1)=1, b(1)=3, c(1)=2, and thereafter

a(n) = mex{a(i), b(i), c(i), i

b(n) = a(n) + 2*n,

c(n) = b(n) - 1.

Then a,b,c form a partition of the positive integers.

Note that there is another triple of sequences (A003144, A003145, A003146) also called a, b, c and also a partition of the positive integers, in a different paper by the same authors (Carlitz-Scovelle-Hoggatt) in the same volume of the same journal.

(End)

a(n) is the number of ones before the n-th zero in the Feigenbaum sequence A035263. - Philippe Deléham, Mar 27 2004

Number of odd numbers before the n-th even number in A007413, A007913, A001511, A029883, A033485, A035263, A036585, A065882, A065883, A088172, A092412. - Philippe Deléham, Apr 03 2004

Indices of a in the sequence closed under a -> abc, b -> a, c -> a, starting with a(1) = a; see A092606 where a = 0, b = 2, c = 1. - Philippe Deléham, Apr 12 2004

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]. See also Optimization, Discrete Mathematics and Applications to Data Sciences, Springer Optimization and Its Applications, Springer, Cham, 2025, and author's site, CNRS France, 2024. See p. 6.
• L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., Fibonacci representations of higher order, Fib. Quart., 10 (1972), 43-69. [Here a, b, c are A003144, A003145, A003146.]
• L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Representations for a special sequence, Fibonacci Quarterly 10.5 (1972), 499-518, 550. [A003156, A003157, A003158 are on page 500.]
• Robbert Fokkink and Gandhar Joshi, On Cloitre's hiccup sequences, arXiv:2507.16956 [math.CO], 2025. See pp. 8, 17

Crossrefs

Cf. A001511, A003157, A003158, A003159, A007413, A007913, A029883, A033485, A035263, A036554, A036585, A056196, A065882, A065883, A072939, A079523, A072939, A080426, A088172, A092412, A092606.

See also A003144, A003145, A003146.

Programs

Haskell

following Deléham
a003156 n = a003156_list !! (n-1)
a003156_list = scanl1 (+) a080426_list
-- Reinhard Zumkeller, Oct 27 2014

Maple

a:= proc(n) global l; while nops(l) [1, 3$d, 1][], l) od; `if` (n=1, 1, a(n-1) +l[n]) end: l:= [1]: seq (a(n), n=1..80); # Alois P. Heinz, Oct 31 2009

Mathematica

Position[Nest[Flatten[# /. {0 -> {0, 2, 1}, 1 -> {0}, 2 -> {0}}]&, {0}, 7], 0] // Flatten (* Jean-François Alcover, Mar 14 2014 *)

Python

def A003156(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 = n+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(f,n,n)-n # Chai Wah Wu, Jan 29 2025

Formula

a(n) = A079523(n) - n + 1 = A003157(n) - 2n = A003158(n) - 2n + 1. - Philippe Deléham, Feb 28 2004

a(n) = A036554(n) - n = A072939(n) - n - 1 = 2*A003159(n) - n. - Philippe Deléham, Apr 10 2004

a(n) = Sum_{k = 1..n} A080426(k). - Philippe Deléham, Apr 16 2004

Extensions

More terms from Alois P. Heinz, Oct 31 2009

Incorrect equation removed from formula by Peter Munn, Dec 11 2020

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.