A033485 -id:A033485 - cp's OEIS frontend

A075535 a(1)=1, a(n) = Sum_{k=1..n-1} min(a(k), a(n-k)).

1, 1, 2, 3, 4, 6, 8, 11, 14, 18, 22, 28, 34, 42, 50, 61, 72, 86, 100, 118, 136, 158, 180, 208, 236, 270, 304, 346, 388, 438, 488, 549, 610, 682, 754, 840, 926, 1026, 1126, 1244, 1362, 1498, 1634, 1792, 1950, 2130, 2310, 2518, 2726, 2962, 3198, 3468, 3738, 4042

Offset: 1

Benoit Cloitre, Jan 11 2003

nonn

Sequence gives 1/2 of the number of unique path partitions of the integer 2n; see the function w(n) as defined in the paper by Bessenrodt, Olsson, and Sellers.

T. D. Noe, Table of n, a(n) for n = 1..10000
Christine Bessenrodt, Jørn B. Olsson, and James A. Sellers, Unique path partitions: Characterization and Congruences, arXiv:1107.1156 [math.CO], 2011-2012.

Cf. A033485.

Fold[Append[#1, Total[Take[Flatten[Transpose[{#1, #1}]], #2]]] &, {1}, Range[53]] (* Birkas Gyorgy, Apr 18 2011 *)
a[1] = 1; a[2] = 1; a[n_] := a[n] = a[n - 1] + a[Floor[n/2]]; Array[a, 100] (* T. D. Noe, Apr 18 2011 *)

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

a(1)=a(2)=1; a(2n) = a(2n-1) + a(n); a(2n+1) = a(2n) + a(n); for n >= 3, a(n) = a(n-1) + a(floor(n/2)).

Let T(x) be the g.f. 1 + x + 2*x^2 + 3*x^3 + ... (i.e., with offset 0), then T(x) = 1 + x * (1+x)/(1-x) * T(x^2). - Joerg Arndt, May 11 2010

A022908 The sequence M(n) in A022905.

Original entry on oeis.org

0, 2, 5, 11, 20, 35, 56, 86, 125, 179, 248, 338, 449, 590, 761, 971, 1220, 1523, 1880, 2306, 2801, 3386, 4061, 4847, 5744, 6782, 7961, 9311, 10832, 12563, 14504, 16694, 19133, 21875, 24920, 28322, 32081, 36266, 40877, 45983, 51584

Offset: 1

Clark Kimberling

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000
J. M. Dover, On two OEIS conjectures, arXiv:1606.08033 [math.CO], 2016.

(* b = A022905 *) b[1] = 1; b[n_] := b[n] = b[n-1] + 1 + If[EvenQ[n], 2 b[n/2], b[(n-1)/2] + b[(n+1)/2]];
a[1] = 0; a[n_] := b[n-1] + 1;
Array[a, 50] (* Jean-François Alcover, Nov 11 2018 *)

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

a(n) = n + Sum_{k=1..n-1} A022907(k), n > 1. [corrected by Sean A. Irvine, May 22 2019]

a(1) = 0; a(n) = (1+3*A033485(2*n-3))/2 = A022905(n-1)+1, n > 1. - Philippe Deléham, May 30 2006

A062186 a(n) = a(n-1) - a(floor(n/2)), with a(1)=1.

Original entry on oeis.org

1, 0, -1, -1, -1, 0, 1, 2, 3, 4, 5, 5, 5, 4, 3, 1, -1, -4, -7, -11, -15, -20, -25, -30, -35, -40, -45, -49, -53, -56, -59, -60, -61, -60, -59, -55, -51, -44, -37, -26, -15, 0, 15, 35, 55, 80, 105, 135, 165, 200, 235, 275, 315, 360, 405, 454, 503, 556, 609, 665, 721, 780, 839, 899, 959, 1020, 1081, 1141, 1201, 1260

Offset: 1

Henry Bottomley, Jun 13 2001

sign

Period of oscillations above and below the axis more than doubles at each cycle.

			a(14) = a(13) - a(7) = 5 - 1 = 4.
a(15) = a(14) - a(7) = 4 - 1 = 3.

Cf. A033485, A062187, A062188.

from itertools import islice
from collections import deque
def A062186_gen(): # generator of terms
    aqueue, f, b, a = deque([0]), True, 1, 0
    yield from (1,0)
    while True:
        a -= b
        yield a
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A062186_list = list(islice(A062186_gen(),40)) # Chai Wah Wu, Jun 08 2022

G.f.: A(x) satisfies: A(x) = (x - (1 + x)*A(x^2))/(1 - x). - Ilya Gutkovskiy, May 04 2019

A062187 a(n+1) = a(n) - a(floor(n/2)), with a(0)=0, a(1)=1.

Original entry on oeis.org

0, 1, 1, 0, -1, -2, -3, -3, -3, -2, -1, 1, 3, 6, 9, 12, 15, 18, 21, 23, 25, 26, 27, 26, 25, 22, 19, 13, 7, -2, -11, -23, -35, -50, -65, -83, -101, -122, -143, -166, -189, -214, -239, -265, -291, -318, -345, -371, -397, -422, -447, -469, -491, -510, -529, -542, -555, -562, -569, -567, -565, -554, -543, -520, -497, -462

Offset: 0

Henry Bottomley, Jun 13 2001

sign

Period of oscillations above and below the axis more than doubles at each cycle.

			a(6) = a(5) - a(2) = -2 - 1 = -3.
a(7) = a(6) - a(3) = -3 - 0 = -3.

Cf. A033485, A062186, A062188.

from itertools import islice
from collections import deque
def A062187_gen(): # generator of terms
    aqueue, f, b, a = deque([1]), True, 0, 1
    yield from (0,1)
    while True:
        a -= b
        yield a
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A061287_list = list(islice(A062187_gen(),40)) # Chai Wah Wu, Jun 08 2022

G.f. A(x) satisfies: A(x) = x * (1 - (1 + x)*A(x^2))/(1 - x). - Ilya Gutkovskiy, May 04 2019

A089178 Triangle T(n,k) (n >= 0, 0 <= k <= 1+log_2(floor(n+1))) read by rows: row 0 = {1}, row 1 = {1 1}; for n >=2, row n = row n-1 + (row floor((n-1)/2) shifted one place right).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 1, 4, 2, 1, 5, 4, 1, 6, 6, 1, 7, 9, 1, 1, 8, 12, 2, 1, 9, 16, 4, 1, 10, 20, 6, 1, 11, 25, 10, 1, 12, 30, 14, 1, 13, 36, 20, 1, 14, 42, 26, 1, 15, 49, 35, 1, 1, 16, 56, 44, 2, 1, 17, 64, 56, 4, 1, 18, 72, 68, 6, 1, 19, 81, 84, 10, 1, 20, 90, 100, 14, 1, 21, 100, 120, 20

Offset: 0

N. J. A. Sloane, Dec 08 2003

			Triangle begins:
1;
1, 1;
1, 2;
1, 3, 1;
1, 4, 2;
1, 5, 4;
1, 6, 6;
1, 7, 9, 1;

Alois P. Heinz, Rows n = 0..1094, flattened
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

Also obtained by dividing rows of A089177 by "1 1".

Row sums give A033485.

T:= proc(n) option remember; `if`(n=0, 1,
      zip((x, y)-> x+y, [T(n-1)], [0, T(floor((n-1)/2))], 0)[])
    end:
seq(T(n), n=0..25);  # Alois P. Heinz, Apr 01 2012

row[0] = {1}; row[n_] := row[n] = PadRight[{row[n-1], Join[{0}, row[Floor[(n-1)/2]]]}] // Total; Table[row[n], {n, 0, 25}] // Flatten (* Jean-François Alcover, Nov 27 2014 *)

G.f.: (1/(1-x))*(1+Sum(y^(k+1)*x^(2^(k+1)-1)/Product(1-x^(2^j), j=0..k), k=0..infinity)).

More terms from Vladeta Jovovic, Dec 10 2003

A089606 Table T(n,k), n>=1 and k>=1; the k-th row is defined by :partial sums of the sequence 1, a(1), .., a(1), a(2), .., a(2), a(3), ..,a(3), a(4), ... each term repeated k times (with a(i)= T(i,k)).

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 8, 3, 2, 1, 16, 5, 3, 2, 1, 32, 7, 4, 3, 2, 1, 64, 10, 6, 4, 3, 2, 1, 128, 13, 8, 5, 4, 3, 2, 1, 256, 18, 10, 7, 5, 4, 3, 2, 1, 512, 23, 13, 9, 6, 5, 4, 3, 2, 1, 1024, 30, 16, 11, 8, 6, 5, 4, 3, 2, 1, 2048, 37, 19, 13, 10, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Philippe Deléham, Jan 03 2004

Row k=1 : 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ...
Row k=2 : 1, 2, 3, 5,  7, 10, 13,  18,  23,  30,   37,   47, ...
Row k=3 : 1, 2, 3, 4,  6,  8, 10,  13,  16,  19,   23,   27, ...
Row k=4 : 1, 2, 3, 4,  5,  7,  9,  11,  13,  16,   19,   22, ...
Row k=5 : 1, 2, 3, 4,  5,  6,  8,  10,  12,  14,   16,   19, ...

Alois P. Heinz, First 200 antidiagonals, flattened

Cf. A000079, A033485, A089649, A089651.

T:= proc(n, k) option remember; `if`(n=1, 1,
      T(n-1, k)+T(floor((n+k-2)/k), k))
    end:
seq(seq(T(1+d-k,k), k=1..d), d=1..12);  # Alois P. Heinz, Feb 24 2023

T(n,1) = A000079(n-1) = 2^(n-1).
T(n,2) = A033485(n).
T(n,3) = A089649(n).
T(n,4) = A089651(n).

A102379 a(n) is the minimal number of nodes in a binary tree of height n.

Original entry on oeis.org

0, 1, 2, 4, 6, 9, 12, 17, 22, 29, 36, 46, 56, 69, 82, 100, 118, 141, 164, 194, 224, 261, 298, 345, 392, 449, 506, 576, 646, 729, 812, 913, 1014, 1133, 1252, 1394, 1536, 1701, 1866, 2061, 2256, 2481, 2706, 2968, 3230, 3529, 3828, 4174, 4520, 4913

Offset: 1

Mitch Harris, Jan 05 2005

nonn

Conjecture: Let b(n) be the number of fixed points of the set of binary partitions of n under Glaisher's function that proves Euler's odd-distinct theorem. Then b(1) = 1 and for n > 1, b(2*n) = b(2*n+1) = 2*a(n). - George Beck, Jul 23 2022

de Bruijn, N. G., On Mahler's partition problem. Nederl. Akad. Wetensch., Proc. 51, (1948) 659-669 = Indagationes Math. 10, 210-220 (1948).
Gonnet, Gaston H.; Olivie, Henk J.; and Wood, Derick, Height-ratio-balanced trees. Comput. J. 26 (1983), no. 2, 106-108.
Mahler, Kurt On a special functional equation. J. London Math. Soc. 15, (1940). 115-123.
Nievergelt, J.; Reingold, E. M., Binary search trees of bounded balance, SIAM J. Comput. 2 (1973), 33-43.

Cf. A000123, A033485, A102378.

Essentially partial sums of A040039.

from functools import cache
@cache
def a(n: int) -> int:
    return a(n - 1) + a(n // 2) + 1 if n > 1 else 0
print([a(n) for n in range(1, 51)])  # Peter Luschny, Jul 24 2022

a(n) = a(n-1) + a(floor(n/2)) + 1, a(1) = 0.
a(n) - a(n-1) = A018819(n+1).
G.f. A(x) satisfies (1-x)*A(x) = 2*(1 + x)*B(x^2), where B(x) is the g.f. of A033485.

A293977 Lexicographically smallest permutation of the nonnegative integers such that a(n) = a(2n) - a(2n-1) for all n >= 1.

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 7, 6, 11, 8, 12, 9, 16, 13, 19, 10, 21, 14, 22, 15, 27, 17, 26, 18, 34, 20, 33, 23, 42, 25, 35, 24, 45, 29, 43, 28, 50, 31, 46, 30, 57, 32, 49, 36, 62, 37, 55, 38, 72, 39, 59, 40, 73, 41, 64, 44, 86, 51, 76, 47, 82, 53, 77, 48, 93, 52, 81, 54, 97, 56, 84, 58

Offset: 0

M. F. Hasler, Oct 27 2017

nonn

A variant of A293976 and A033485.

The definition means that the sequence of differences of pairs of terms, (a(2n)-a(2n-1); n>=1), is equal to the sequence (a(n); n>=1) itself. The term a(0) is just a very natural extension of this permutation of the positive integers to all n >= 0.

Carole Dubois, Table of n, a(n) for n = 0..1244
E. Angelini, Successive weighing scales, post to the SeqFan list, June 14, 2010.
E. Angelini, Weighing scales and sequences.

Cf. A033485, A293976.

A293977_vec(n,A=vector(n+1),U=[0])={for(i=2,n,A[i]&&next;if(bittest(i,0),A[i]=A[i-1]+A[i\2+1],for(k=U[1]+1,oo,setsearch(U,k)&&next;setsearch(U,k+A[i\2+1])&&next; A[i]=k;break)); U=setunion(U,[A[i]]);while(#U>1&&U[2]==U[1]+1,U=U[^1]));A}

A293976 a(2n) = a(2n-1) + a(n) for n >= 1, a(2n+1) = a(2n) + 1, a(0) = 0.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 9, 10, 15, 16, 22, 23, 32, 33, 43, 44, 59, 60, 76, 77, 99, 100, 123, 124, 156, 157, 190, 191, 234, 235, 279, 280, 339, 340, 400, 401, 477, 478, 555, 556, 655, 656, 756, 757, 880, 881, 1005, 1006, 1162, 1163, 1320, 1321, 1511, 1512, 1703

Offset: 0

M. F. Hasler, Oct 27 2017

nonn

A variant of A033485.
Starting with a(1) = 1, the sequence can also be defined as the smallest increasing sequence equal to the sequence of differences between pairs of terms: a(n) = a(2n) - a(2n-1).
See A293977 for a variant which is not monotonic but a permutation of the nonnegative integers.

E. Angelini, Successive weighing scales, post to the SeqFan list, June 14, 2010.
E. Angelini, Weighing scales and sequences.

Cf. A033485, A293977.

A293976_vec(n,A=List(1))=for(i=1,n\2,listput(A,A[#A]+A[i]);listput(A,A[#A]+1));concat(0,Vec(A))

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

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 16, 19, 22, 26, 30, 34, 39, 44, 49, 55, 61, 67, 74, 81, 88, 97, 106, 115, 126, 137, 148, 161, 174, 187, 203, 219, 235, 254, 273, 292, 314, 336, 358, 384, 410, 436, 466, 496, 526, 560, 594, 628, 667, 706, 745, 789, 833, 877

Offset: 1

Jeffrey Shallit, Dec 16 2019

nonn

Also, the number of finite sequences b(1..r) satisfying b(1) = 1 and b(i+1) >= 3*b(i) and b(r) <= n.

			For n = 10 the 11 sequences enumerated are (1), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10), (1,3,9), (1,3,10).

An analog of A033485.

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

Nest[Append[#1, #1[[-1]] + #1[[Floor[#2/3] ]] ] & @@ {#, Length@ # + 1} &, {1, 1}, 57] (* Michael De Vlieger, Dec 16 2019 *)

cp's OEIS Frontend

A075535 a(1)=1, a(n) = Sum_{k=1..n-1} min(a(k), a(n-k)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A022908 The sequence M(n) in A022905.

Views

Author

Keywords

Links

Programs

Mathematica

Python

Formula

A062186 a(n) = a(n-1) - a(floor(n/2)), with a(1)=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

A062187 a(n+1) = a(n) - a(floor(n/2)), with a(0)=0, a(1)=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

A089178 Triangle T(n,k) (n >= 0, 0 <= k <= 1+log_2(floor(n+1))) read by rows: row 0 = {1}, row 1 = {1 1}; for n >=2, row n = row n-1 + (row floor((n-1)/2) shifted one place right).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A089606 Table T(n,k), n>=1 and k>=1; the k-th row is defined by :partial sums of the sequence 1, a(1), .., a(1), a(2), .., a(2), a(3), ..,a(3), a(4), ... each term repeated k times (with a(i)= T(i,k)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A102379 a(n) is the minimal number of nodes in a binary tree of height n.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Python

Formula

A293977 Lexicographically smallest permutation of the nonnegative integers such that a(n) = a(2n) - a(2n-1) for all n >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs