A003156 -id:A003156 - cp's OEIS frontend

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

2, 7, 10, 13, 18, 23, 28, 31, 34, 39, 42, 45, 50, 53, 56, 61, 66, 71, 74, 77, 82, 87, 92, 95, 98, 103, 108, 113, 116, 119, 124, 127, 130, 135, 138, 141, 146, 151, 156, 159

Offset: 1

N. J. A. Sloane

nonn

Numbers not of the form Sum_{i>=2} e_i*A001045(i), with e(i) = 0 or 1.

Indices of b 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

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

Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 67.
L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Representations for a special sequence, Fibonacci Quarterly 10.5 (1972), 499-518, 550.

Cf. A001045, A003156, A003157, A079523, A092606.

def A003158(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-1 # Chai Wah Wu, Jan 29 2025

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

Definition clarified by N. J. A. Sloane, Dec 26 2020

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

Original entry on oeis.org

3, 8, 11, 14, 19, 24, 29, 32, 35, 40, 43, 46, 51, 54, 57, 62, 67, 72, 75, 78, 83, 88, 93, 96, 99, 104, 109, 114, 117, 120, 125, 128, 131, 136, 139, 142, 147, 152, 157, 160

Offset: 1

N. J. A. Sloane

nonn

Indices of c 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

These are the positions of 1 in A286044; complement of A286045; conjecture: a(n)/n -> 4. - Clark Kimberling, May 07 2017

			As a word, A286044 = 001000010010010000100..., in which 1 is in positions a(n) for n>=1.  - _Clark Kimberling_, May 07 2017

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

Clark Kimberling, Table of n, a(n) for n = 1..10000
L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Representations for a special sequence, Fibonacci Quarterly 10.5 (1972), 499-518, 550.

Cf. A003156, A003158, A010060, A286044, A286045.

s = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {0}, 9] (* Thue-Morse, A010060 *)
w = StringJoin[Map[ToString, s]]
w1 = StringReplace[w, {"011" -> "0"}]
st = ToCharacterCode[w1] - 48 (* A286044 *)
Flatten[Position[st, 0]]  (* A286045 *)
Flatten[Position[st, 1]]  (* A003157 *)
(* Clark Kimberling, May 07 2017 *)

def A003157(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

Numbers n such that A003159(n) is even. a(n) = A003158(n) + 1 = A036554(n) + n. - Philippe Deléham, Feb 22 2004

A339584 A ternary sequence: a(n) = 1 if n is in A003156, 2 if n is in A003157, 3 if n is in A003158.

Original entry on oeis.org

1, 3, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 1, 1, 3, 2, 1, 1, 1, 3, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 1, 1, 3, 2, 1, 1, 1, 3, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 1, 1, 3, 2, 1, 1, 1, 3, 2, 1, 1, 1, 3, 2, 1

Offset: 1

N. J. A. Sloane, Dec 26 2020

nonn

This has the same relationship to A003156-A003158 as A092782 does to A003144-A003146.

Cf. A003156, A003157, A003158; A003144, A003145, A003146, A080843, A092606, A092782.

Nest[Flatten[# /. {1 -> {1, 3, 2}, 2 -> 1, 3 -> 1}] &, {1}, 8] (* John Keith, Dec 28 2020 after Robert G. Wilson v's program for A092782. *)

a(n) = A092606(n) + 1. - John Keith, Dec 28 2020

A036554 Numbers whose binary representation ends in an odd number of zeros.

Original entry on oeis.org

2, 6, 8, 10, 14, 18, 22, 24, 26, 30, 32, 34, 38, 40, 42, 46, 50, 54, 56, 58, 62, 66, 70, 72, 74, 78, 82, 86, 88, 90, 94, 96, 98, 102, 104, 106, 110, 114, 118, 120, 122, 126, 128, 130, 134, 136, 138, 142, 146, 150, 152, 154, 158, 160, 162, 166, 168, 170, 174

Offset: 1

Tom Verhoeff

Fraenkel (2010) called these the "dopey" numbers.
Also n such that A035263(n)=0 or A050292(n) = A050292(n-1).
Indices of even numbers in A033485. - Philippe Deléham, Mar 16 2004
a(n) is an odious number (see A000069) for n odd; a(n) is an evil number (see A001969) for n even. - Philippe Deléham, Mar 16 2004
Indices of even numbers in A007913, in A001511. - Philippe Deléham, Mar 27 2004
This sequence consists of the increasing values of n such that A097357(n) is even. - Creighton Dement, Aug 14 2004
Numbers with an odd number of 2's in their prime factorization (e.g., 8 = 2*2*2). - Mark Dow, Sep 04 2007
Equals the set of natural numbers not in A003159 or A141290. - Gary W. Adamson, Jun 22 2008
Represents the set of CCW n-th moves in the standard Tower of Hanoi game; and terms in even rows of a [1, 3, 5, 7, 9, ...] * [1, 2, 4, 8, 16, ...] multiplication table. Refer to the example. - Gary W. Adamson, Mar 20 2010
Refer to the comments in A003159 relating to A000041 and A174065. - Gary W. Adamson, Mar 21 2010
If the upper s-Wythoff sequence of s is s, then s=A036554. (See A184117 for the definition of lower and upper s-Wythoff sequences.) Starting with any nondecreasing sequence s of positive integers, A036554 is the limit when the upper s-Wythoff operation is iterated.  For example, starting with s=(1,4,9,16,...) = (n^2), we obtain lower and upper s-Wythoff sequences
  a=(1,3,4,5,6,8,9,10,11,12,14,...) = A184427;
  b=(2,7,12,21,31,44,58,74,...) = A184428.
  Then putting s=a and repeating the operation gives
b'=(2,6,8,10,13,17,20,...), which has the same first four terms as A036554. - Clark Kimberling, Jan 14 2011
Or numbers having infinitary divisor 2, or the same, having factor 2 in Fermi-Dirac representation as a product of distinct terms of A050376. - Vladimir Shevelev, Mar 18 2013
Thus, numbers not in A300841 or in A302792. Equally, sequence 2*A300841(n) sorted into ascending order. - Antti Karttunen, Apr 23 2018

			From _Gary W. Adamson_, Mar 20 2010: (Start)
Equals terms in even numbered rows in the following multiplication table:
(rows are labeled 1,2,3,... as with the Towers of Hanoi disks)
   1,  3,  5,  7,  9, 11, ...
   2,  6, 10, 14, 18, 22, ...
   4, 12, 20, 28, 36, 44, ...
   8, 24, 40, 56, 72, 88, ...
   ...
As shown, 2, 6, 8, 10, 14, ...; are in even numbered rows, given the row with (1, 3, 5, 7, ...) = row 1.
The term "5" is in an odd row, so the 5th Towers of Hanoi move is CW, moving disc #1 (in the first row).
a(3) = 8 in row 4, indicating that the 8th Tower of Hanoi move is CCW, moving disc #4.
A036554 bisects the positive nonzero natural numbers into those in the A036554 set comprising 1/3 of the total numbers, given sufficiently large n.
This corresponds to 1/3 of the TOH moves being CCW and 2/3 CW. Row 1 of the multiplication table = 1/2 of the natural numbers, row 2 = 1/4, row 3 = 1/8 and so on, or 1 = (1/2 + 1/4 + 1/8 + 1/16 + ...). Taking the odd-indexed terms of this series given offset 1, we obtain 2/3 = 1/2 + 1/8 + 1/32 + ..., while sum of the even-indexed terms is 1/3. (End)

T. D. Noe, Table of n, a(n) for n = 1..1000
L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., Representations for a special sequence, Fib. Quart., 10 (1972), 499-518, 550 (see d(n) on page 501).
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
A. S. Fraenkel, Home Page
Aviezri S. Fraenkel, New games related to old and new sequences, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (2012), no. 1, 42-46.
Clark Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.
Eric Sopena, i-Mark: A new subtraction division game, arXiv:1509.04199 [cs.DM], 2015.
M. Stoll, Chabauty without the Mordell-Weil group, arXiv preprint arXiv:1506.04286 [math.NT], 2015.
Index entries for 2-automatic sequences.

Indices of odd numbers in A007814. Subsequence of A036552. Complement of A003159. Also double of A003159.

Cf. A000041, A003157, A003158, A005408, A052330, A072939, A079523, A096268 (characteristic function, when interpreted with offset 1), A141290, A174065, A300841.

a036554 = (+ 1) . a079523  -- Reinhard Zumkeller, Mar 01 2012

[2*m:m in [1..100] | Valuation(m,2) mod 2 eq 0]; // Marius A. Burtea, Aug 29 2019

Select[Range[200],OddQ[IntegerExponent[#,2]]&] (* Harvey P. Dale, Oct 19 2011 *)

is(n)=valuation(n,2)%2 \\ Charles R Greathouse IV, Nov 20 2012

def ok(n):
  c = 0
  while n%2 == 0: n //= 2; c += 1
  return c%2 == 1
print([m for m in range(1, 175) if ok(m)]) # Michael S. Branicky, Feb 06 2021

from itertools import count, islice
def A036554_gen(startvalue=1): return filter(lambda n:(~n & n-1).bit_length()&1,count(max(startvalue,1))) # generator of terms >= startvalue
A036554_list = list(islice(A036554_gen(),30)) # Chai Wah Wu, Jul 05 2022

is_A036554 = lambda n: A001511(n)&1==0 # M. F. Hasler, Nov 26 2024

def A036554(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) # Chai Wah Wu, Jan 29 2025

a(n) = A079523(n)+1 = A072939(n)-1.
a(n) = A003156(n) + n = A003157(n) - n = A003158(n) - n + 1. - Philippe Deléham, Apr 10 2004
Values of k such that A091297(k) = 2. - Philippe Deléham, Feb 25 2004
a(n) ~ 3n. - Charles R Greathouse IV, Nov 20 2012 [In fact, a(n) = 3n + O(log n). - Charles R Greathouse IV, Nov 27 2024]
a(n) = 2*A003159(n). - Clark Kimberling, Sep 30 2014
{a(n)} = A052330({A005408(n)}), where {a(n)} denotes the set of integers in the sequence. - Peter Munn, Aug 26 2019

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

A033485 a(n) = a(n-1) + a(floor(n/2)), a(1) = 1.

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 83, 101, 119, 142, 165, 195, 225, 262, 299, 346, 393, 450, 507, 577, 647, 730, 813, 914, 1015, 1134, 1253, 1395, 1537, 1702, 1867, 2062, 2257, 2482, 2707, 2969, 3231, 3530, 3829, 4175, 4521, 4914, 5307, 5757

Offset: 1

N. J. A. Sloane. This was in the 1973 "Handbook", but was then dropped from the database. Resubmitted by Philippe Deléham. Entry revised by N. J. A. Sloane, Jun 10 2012

Sequence gives the number of partitions of 2n into "strongly decreasing" parts (see the function s*(n) in the paper by Bessenrodt, Olsson, and Sellers); see the example in A040039.
a(A036554(n)) is even, a(A003159(n)) is odd. - Benoit Cloitre, Oct 23 2002
Partial sums of the sequence a(1)=1, a(1), a(1), a(2), a(2), a(3), a(3), a(4), a(4), a(5), a(5), a(6), ...; example: a(1) = 1, a(2) = 1+1 = 2, a(3) = 1+1+1 = 3, a(4) = 1+1+1+2 = 5, a(5) = 1+1+1+2+2 = 7, ... - Philippe Deléham, Jan 02 2004
The number of odd numbers before the n-th even number in this sequence is A003156(n). - Philippe Deléham, Mar 27 2004
There are no terms divisible by 4 and there are infinitely many terms divisible by {2,3,5,6,7,9,10,11,13,14,15} (see van Doorn link). - Ivan N. Ianakiev, Aug 06 2022 and Wouter van Doorn, Sep 17 2024
a(n) = A001401(n), for 1..14. A001401(15) = 84. - Wolfdieter Lang, Jan 09 2023

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..1000
J. Arkin, Problem H-102: Gone but not forgotten, Fibonacci Quarterly, Vol. 9 (1971), page 135.
Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, Unique path partitions: Characterization and Congruences, arXiv:1107.1156 [math.CO], 2011-2012.
Philippe Deléham, Letter to N. J. A. Sloane, Apr 20 1998
William Gasarch, What is known about that sequence, Computational Complexity blog, Jul 20 2022.
Wouter van Doorn, On the congruence properties and growth rate of a recursively defined sequence, arXiv:2406.09532 [math.NT], 2024.

Cf. A040039 (first differences), A178855 (partial sums).
Also half of A000123 (with first term omitted).
Cf. A022907.
Cf. A036554, A003159, A003156.
Cf. A007413, A178855, A131205.

import Data.List (transpose)
a033485 n = a033485_list !! (n-1)
a033485_list = 1 : zipWith (+)
   a033485_list (concat $ transpose [a033485_list, a033485_list])
-- Reinhard Zumkeller, Nov 15 2012

[n le 1 select 1 else Self(n-1) + Self(Floor(n/2)) : n in [1..60]]; // Vincenzo Librandi, Nov 20 2015

a:= proc(n) option remember;
      `if`(n<2, n, a(n-1)+a(iquo(n, 2)))
    end:
seq(a(n), n=1..60);  # Alois P. Heinz, Dec 16 2019

b[1]=1; b[n_] := b[n]=Sum[b[k], {k, 1, n/2}]; Table[b[n], {n, 3, 105, 2}] (* Robert G. Wilson v, Apr 22 2001 *)

PARI
```
a(n)=if(n<2,1,a(floor(n/2))+a(n-1))
```

from itertools import islice
from collections import deque
def A033485_gen(): # generator of terms
    aqueue, f, b, a = deque([2]), True, 1, 2
    yield from (1, 2)
    while True:
        a += b
        yield a
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A033485_list = list(islice(A033485_gen(),40)) # Chai Wah Wu, Jun 07 2022

a(n) = A000123(n)/2, for n >= 1.
Conjecture: lim_{n->oo} a(2n)/a(n)*log(n)/n = c = 1.64.... and a(n)/A(n) is bounded where A(n)=1 if n is a power of 2, otherwise A(n) = sqrt(n)*Product_{kBenoit Cloitre, Jan 26 2003
G.f.: A(x) satisfies x + (1+x)*A(x^2) = (1-x)*A(x). a(n) modulo 2 = A035263(n). - Philippe Deléham, Feb 25 2004
G.f.: (1/2)*(((1-x)*Product_{n>=0} (1-x^(2^n)))^(-1)-1). a(n) modulo 4 = A007413(n). - Philippe Deléham, Feb 28 2004
Sum_{k=1..n} a(k) = (a(2n+1)-1)/2 = A178855(n). - Philippe Deléham, Mar 18 2004
a(2n-1) = A131205(n). - Jean-Paul Allouche, Aug 11 2021
There exists a function f(n) such that n^f(n) < a(n) < n^(f(n) + epsilon) for all epsilon > 0 and all large enough n. - Wouter van Doorn, Sep 17 2024

A007413 A squarefree (or Thue-Morse) ternary sequence: closed under 1->123, 2->13, 3->2. Start with 1.

Original entry on oeis.org

1, 2, 3, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 3, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 3, 1, 3, 2, 1, 2, 3

Offset: 1

N. J. A. Sloane

a(n)=2 if and only if n-1 is in A079523. - Benoit Cloitre, Mar 10 2003
Partial sums modulo 4 of the sequence 1, a(1), a(1), a(2), a(2), a(3), a(3), a(4), a(4), a(5), a(5), a(6), a(6), ... - Philippe Deléham, Mar 04 2004
To construct the sequence: start with 1 and concatenate 4 -1 = 3: 1, 3, then change the last term (2 -> 1, 3 ->2 ) gives 1, 2. Concatenate 1, 2 with 4 -1 = 3, 4 - 2 = 2: 1, 2, 3, 2 and change the last term: 1, 2, 3, 1. Concatenate 1, 2, 3, 1 with 4 - 1 = 3, 4 - 2 = 2, 4 - 3 = 1, 4 - 1 = 3: 1, 2, 3, 1, 3, 2, 1, 3 and change the last term: 1, 2, 3, 1, 3, 2, 1, 2 etc. - Philippe Deléham, Mar 04 2004
To construct the sequence: start with the Thue-Morse sequence A010060 = 0, 1, 1, 0, 1, 0, 0, 1, ... Then change 0 -> 1, 2, 3,  and 1 -> 3, 2, 1,  gives: 1, 2, 3, , 3, 2, 1, ,3, 2, 1, , 1, 2, 3, , 3, 2, 1, , ... and fill in the successive holes with the successive terms of the sequence itself. - _Philippe Deléham, Mar 04 2004
To construct the sequence: to insert the number 2 between the A003156(k)-th term and the (1 + A003156(k))-th term of the sequence 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, ... - Philippe Deléham, Mar 04 2004
Conjecture. The sequence is formed by the numbers of 1's between every pair of consecutive 2's in A076826. - Vladimir Shevelev, May 31 2009

			Here are the first 5 stages in the construction of this sequence, together with Mma code, taken from Keranen's article. His alphabet is a,b,c rather than 1,2,3.
productions = {"a" -> "abc ", "b" -> "ac ", "c" -> "b ", " " -> ""};
NestList[g, "a", 5] // TableForm
a
abc
abc ac b
abc ac b abc b ac
abc ac b abc b ac abc ac b ac abc b
abc ac b abc b ac abc ac b ac abc b abc ac b abc b ac abc b abc ac b ac

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, No. 7 (1906), 1-22.

Paolo Xausa, Table of n, a(n) for n = 1..10000
Roger L. Bagula, Description of sequence as successive rows of a triangle
James D. Currie, Non-repetitive words: Ages and essences, Combinatorica 16.1 (1996): 19-40. See p. 20.
James D. Currie, Palindrome positions in ternary square-free words, Theoretical Computer Science, 396 (2008) 254-257.
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
V. Keranen, New Abelian Square-Free DT0L-Languages over 4 Letters, Theoretical Computer Science, Volume 410, Issues 38-40, 6 September 2009, Pages 3893-3900.
S. Kitaev and T. Mansour, Counting the occurrences of generalized patterns in words generated by a morphism, arXiv:math/0210170 [math.CO], 2002.
Andrzej Tomski and Maciej Zakarczemny, A note on Browkin's and Cao's cancellation algorithm, Technical Transections 7/2018.

Cf. A001285, A010060.
First differences of A000069.
Equals A036580(n-1) + 1.
Cf. A115384, A159481, A079523, A000120.

Nest[ Flatten[ # /. {1 -> {1, 2, 3}, 2 -> {1, 3}, 3 -> {2}}] &, {1}, 7] (* Robert G. Wilson v, May 07 2005 *)
2 - Differences[ThueMorse[Range[0, 100]]] (* Paolo Xausa, Oct 25 2024 *)

{a(n) = if( n<1 || valuation(n, 2)%2, 2, 2 + (-1)^subst( Pol(binary(n)), x,1))};

def A007413(n): return 2-(n.bit_count()&1)+((n-1).bit_count()&1) # Chai Wah Wu, Mar 03 2023

a(n) modulo 2 = A035263(n). a(A036554(n)) = 2. a(A003159(n)) = 1 if n odd. a(A003159(n)) = 3 if n even. a(n) = A033485(n) mod 4. a(n) = 4 - A036585(n-1). - Philippe Deléham, Mar 04 2004
a(n) = 2 - A029883(n) = 3 - A036577(n). - Philippe Deléham, Mar 20 2004
For n>=1, we have: 1) a(A108269(n))=A010684(n-1); 2) a(A079523(n))=A010684(n-1); 3) a(A081706(2n))=A010684(n). - Vladimir Shevelev, Jun 22 2009

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.

Original entry on oeis.org

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

John W. Layman, Feb 18 2003

nonn

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

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.

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

Arises in the analysis of A075326, A249031 and A249032.

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

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

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

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

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

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

A003160 a(1) = a(2) = 1, a(n) = n - a(a(n-1)) - a(a(n-2)).

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 8, 9, 9, 9, 10, 11, 12, 12, 12, 13, 14, 15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 24, 25, 25, 25, 26, 26, 26, 27, 27, 27, 28, 29, 30, 30, 30, 31, 32, 33, 33, 33, 34, 35, 36, 36, 36, 37, 37, 37, 38

Offset: 1

N. J. A. Sloane

nonn

Sequence of indices n where a(n-1) < a(n) appears to be given by A003156. - Joerg Arndt, May 11 2010

The number n appears A080426(n+1) times. - John Keith, Dec 31 2020

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

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Representations for a special sequence, Fibonacci Quarterly 10.5 (1972), 499-518, 550.

Cf. A003156, A005206, A080426, A095774, A095775.

a003160 n = a003160_list !! (n-1)
a003160_list = 1 : 1 : zipWith (-) [3..] (zipWith (+) xs $ tail xs)
   where xs = map a003160 a003160_list
-- Reinhard Zumkeller, Aug 02 2013

Block[{a = {1, 1}}, Do[AppendTo[a, i - a[[ a[[-1]] ]] - a[[ a[[-2]] ]] ], {i, 3, 76}]; a] (* Michael De Vlieger, Dec 31 2020 *)

PARI
```
a(n)=if(n<3,1,n-a(a(n-1))-a(a(n-2)))
```

@CachedFunction
def a(n): return 1 if (n<3) else n - a(a(n-1)) - a(a(n-2))
[a(n) for n in range(1, 81)] # G. C. Greubel, Nov 06 2022

a(n) is asymptotic to n/2.

Conjecture: a(n) = E/2 where we start with A := n + 1, B := 0, L := A085423(A), C := A000975(L-1), D := 0, E := C and until A = B consecutively apply B := A, A := 2*C - A - (L mod 2) + 2, L := A085423(A), C := A000975(L-1), D := D + 1, E := (1 + [A = B])*E + (-1)^D*C. - Mikhail Kurkov, May 12 2025

Edited by Benoit Cloitre, Jan 01 2003

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

A339584 A ternary sequence: a(n) = 1 if n is in A003156, 2 if n is in A003157, 3 if n is in A003158.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A036554 Numbers whose binary representation ends in an odd number of zeros.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Python

Python

Python

Python

Formula

Extensions

A033485 a(n) = a(n-1) + a(floor(n/2)), a(1) = 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

A007413 A squarefree (or Thue-Morse) ternary sequence: closed under 1->123, 2->13, 3->2. Start with 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs