cp's OEIS Frontend

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

%I A003156 M3239 #66 Jul 30 2025 11:20:11
%S A003156 1,4,5,6,9,12,15,16,17,20,21,22,25,26,27,30,33,36,37,38,41,44,47,48,
%T A003156 49,52,55,58,59,60,63,64,65,68,69,70,73,76,79,80,81,84,85,86,89,90,91,
%U A003156 94,97,100,101,102,105,106,107,110,111,112,115,118,121,122,123,126,129,132
%N A003156 A self-generating sequence (see Comments for definition).
%C A003156 From _N. J. A. Sloane_, Dec 26 2020: (Start)
%C A003156 The best definitions of the triple [this sequence, A003157, A003158] are as the rows a(n), b(n), c(n) of the table:
%C A003156 n: 1, 2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
%C A003156 a: 1, 4,  5,  6,  9, 12, 15, 16, 17, 20, 21, 22, ...
%C A003156 b: 3, 8, 11, 14, 19, 24, 29, 32, 35, 40, 43, 46, ...
%C A003156 c: 2, 7, 10, 13, 18, 23, 28, 31, 34, 39, 42, 45, ...
%C A003156 where a(1)=1, b(1)=3, c(1)=2, and thereafter
%C A003156 a(n) = mex{a(i), b(i), c(i), i<n},
%C A003156 b(n) = a(n) + 2*n,
%C A003156 c(n) = b(n) - 1.
%C A003156 Then a,b,c form a partition of the positive integers.
%C A003156 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.
%C A003156 (End)
%C A003156 a(n) is the number of ones before the n-th zero in the Feigenbaum sequence A035263. - _Philippe Deléham_, Mar 27 2004
%C A003156 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
%C A003156 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
%D A003156 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003156 Alois P. Heinz, <a href="/A003156/b003156.txt">Table of n, a(n) for n = 1..1000</a>
%H A003156 Jean-Paul Allouche, <a href="/A026465/a026465.pdf">On the morphism 1 -> 121, 2 -> 12221</a>, Preprint, 2024 [Local copy, with permission]. See also <a href="https://doi.org/10.1007/978-3-031-78369-2_1">Optimization, Discrete Mathematics and Applications to Data Sciences</a>, Springer Optimization and Its Applications, Springer, Cham, 2025, and <a href="https://webusers.imj-prg.fr/~jean-paul.allouche/121-12221.pdf">author's site</a>, CNRS France, 2024. See p. 6.
%H A003156 L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/10-1/carlitz3-a.pdf">Fibonacci representations of higher order</a>, Fib. Quart., 10 (1972), 43-69. [Here a, b, c are A003144, A003145, A003146.]
%H A003156 L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/10-5/carlitz3-a.pdf">Representations for a special sequence</a>, Fibonacci Quarterly 10.5 (1972), 499-518, 550. [A003156, A003157, A003158 are on page 500.]
%H A003156 Robbert Fokkink and Gandhar Joshi, <a href="https://arxiv.org/abs/2507.16956">On Cloitre's hiccup sequences</a>, arXiv:2507.16956 [math.CO], 2025. See pp. 8, 17
%F A003156 a(n) = A079523(n) - n + 1 = A003157(n) - 2n = A003158(n) - 2n + 1. - _Philippe Deléham_, Feb 28 2004
%F A003156 a(n) = A036554(n) - n = A072939(n) - n - 1 = 2*A003159(n) - n. - _Philippe Deléham_, Apr 10 2004
%F A003156 a(n) = Sum_{k = 1..n} A080426(k). - _Philippe Deléham_, Apr 16 2004
%p A003156 a:= proc(n) global l; while nops(l)<n do l:= map (d-> [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
%t A003156 Position[Nest[Flatten[# /. {0 -> {0, 2, 1}, 1 -> {0}, 2 -> {0}}]&, {0}, 7], 0] // Flatten (* _Jean-François Alcover_, Mar 14 2014 *)
%o A003156 (Haskell)  following Deléham
%o A003156 a003156 n = a003156_list !! (n-1)
%o A003156 a003156_list = scanl1 (+) a080426_list
%o A003156 -- _Reinhard Zumkeller_, Oct 27 2014
%o A003156 (Python)
%o A003156 def A003156(n):
%o A003156     def bisection(f,kmin=0,kmax=1):
%o A003156         while f(kmax) > kmax: kmax <<= 1
%o A003156         kmin = kmax >> 1
%o A003156         while kmax-kmin > 1:
%o A003156             kmid = kmax+kmin>>1
%o A003156             if f(kmid) <= kmid:
%o A003156                 kmax = kmid
%o A003156             else:
%o A003156                 kmin = kmid
%o A003156         return kmax
%o A003156     def f(x):
%o A003156         c, s = n+x, bin(x)[2:]
%o A003156         l = len(s)
%o A003156         for i in range(l&1,l,2):
%o A003156             c -= int(s[i])+int('0'+s[:i],2)
%o A003156         return c
%o A003156     return bisection(f,n,n)-n # _Chai Wah Wu_, Jan 29 2025
%Y A003156 Cf. A001511, A003157, A003158, A003159, A007413, A007913, A029883, A033485, A035263, A036554, A036585, A056196, A065882, A065883, A072939, A079523, A072939, A080426, A088172, A092412, A092606.
%Y A003156 See also A003144, A003145, A003146.
%K A003156 nonn
%O A003156 1,2
%A A003156 _N. J. A. Sloane_
%E A003156 More terms from _Alois P. Heinz_, Oct 31 2009
%E A003156 Incorrect equation removed from formula by _Peter Munn_, Dec 11 2020