A001855 -id:A001855 - cp's OEIS frontend

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

1, 4, 8, 12, 17, 22, 27, 32, 38, 44, 50, 56, 62, 68, 74, 80, 87, 94, 101, 108, 115, 122, 129, 136, 143, 150, 157, 164, 171, 178, 185, 192, 200, 208, 216, 224, 232, 240, 248, 256, 264, 272, 280, 288, 296, 304, 312, 320, 328, 336, 344, 352, 360, 368, 376, 384, 392, 400, 408

Offset: 1

N. J. A. Sloane, Jun 05 2002

nonn

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Haomin Li, Computing a Basis for an Integer Lattice, Master's Thesis, Univ. of Waterloo (Ontario, Canada 2022).
M. A. Nyblom, Some curious sequences involving floor and ceiling functions, Am. Math. Monthly 109 (#6, 200), 559-564, Th. 3.1.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A123753.

A033156 := proc(n) option remember; if n=1 then 1 else A033156(n-1)+floor(A033156(n-1)/(n-1))+2; fi; end;

a[n_] := n (2 + IntegerLength[n, 2]) - 2^IntegerLength[n, 2];
Table[a[n], {n, 1, 59}] (* Peter Luschny, Dec 02 2017 *)
nxt[{n_,a_}]:={n+1,a+Floor[a/n]+2}; NestList[nxt,{1,1},60][[All,2]] (* Harvey P. Dale, Nov 03 2020 *)

def A033156(n):
    s, i, z = 2*n-1, n-1, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A033156(n) for n in range(1, 60)]) # Peter Luschny, Nov 30 2017

def A033156(n): return n*(2+(m:=(n-1).bit_length()))-(1<Chai Wah Wu, Mar 29 2023

a(n) = n*(floor(log_2 n) + 3) - 2^((floor (log_2 n)) + 1).
a(n) = n + a(floor(n/2)) + a(ceiling(n/2)) = n + min{a(k) + a(n-k):0 < k < n} = n + A003314(n). - Henry Bottomley, Jul 03 2002
A001855(n) + 2n-1. a(n) = b(n)+1 with b(0)=0, b(2n) = b(n) + b(n-1) + 2n + 2, b(2n+1) = 2b(n) + 2n + 3. - Ralf Stephan, Oct 24 2003
a(n) = A123753(n-1) + n - 1. - Peter Luschny, Nov 30 2017

A301336 a(n) = total number of 1's minus total number of 0's in binary expansions of 0, ..., n.

Original entry on oeis.org

-1, 0, 0, 2, 1, 2, 3, 6, 4, 4, 4, 6, 6, 8, 10, 14, 11, 10, 9, 10, 9, 10, 11, 14, 13, 14, 15, 18, 19, 22, 25, 30, 26, 24, 22, 22, 20, 20, 20, 22, 20, 20, 20, 22, 22, 24, 26, 30, 28, 28, 28, 30, 30, 32, 34, 38, 38, 40, 42, 46, 48, 52, 56, 62, 57, 54, 51, 50, 47, 46, 45, 46, 43, 42, 41, 42

Offset: 0

Ilya Gutkovskiy, Mar 28 2018

			+---+-----+---+---+---+---+------------+
| n | bin.|1's|sum|0's|sum|    a(n)    |
+---+-----+---+---+---+---+------------+
| 0 |   0 | 0 | 0 | 1 | 1 | 0 - 1 =-1  |
| 1 |   1 | 1 | 1 | 0 | 1 | 1 - 1 = 0  |
| 2 |  10 | 1 | 2 | 1 | 2 | 2 - 2 = 0  |
| 3 |  11 | 2 | 4 | 0 | 2 | 4 - 2 = 2  |
| 4 | 100 | 1 | 5 | 2 | 4 | 5 - 4 = 1  |
| 5 | 101 | 2 | 7 | 1 | 5 | 7 - 5 = 2  |
| 6 | 110 | 2 | 9 | 1 | 6 | 9 - 6 = 3  |
+---+-----+---+---+---+---+------------+
bin. - n written in base 2;
1's - number of 1's in binary expansion of n;
0's - number of 0's in binary expansion of n;
sum - total number of 1's (or 0's) in binary expansions of 0, ..., n.

Index entries for sequences related to binary expansion of n

Cf. A000079, A000120, A000295, A000788, A001855, A023416, A037861, A059015, A083652, A145037, A268289, A301896.

a:= proc(n) option remember; `if`(n=0, -1,
      a(n-1)+add(2*i-1, i=Bits[Split](n)))
    end:
seq(a(n), n=0..75);  # Alois P. Heinz, Nov 11 2024

Accumulate[DigitCount[Range[0, 75], 2, 1] - DigitCount[Range[0, 75], 2, 0]]

def A301336(n):
    return sum(2*bin(i).count('1')-len(bin(i))+2 for i in range(n+1)) # Chai Wah Wu, Sep 03 2020

def A301336(n): return (n+1)*((n.bit_count()<<1)-(t:=(n+1).bit_length()))+(1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))-2 # Chai Wah Wu, Nov 11 2024

G.f.: -1/(1 - x) + (1/(1 - x)^2)*Sum_{k>=0} x^(2^k)*(1 - x^(2^k))/(1 + x^(2^k)).
a(n) = A000788(n) - A059015(n).
a(n) = A268289(n) - 1.
a(A000079(n)) = A000295(n).

A307030 Number of permutations of [n] with overlapping adjacent runs.

Original entry on oeis.org

1, 1, 3, 11, 49, 263, 1653, 11877, 95991, 862047, 8516221, 91782159, 1071601285, 13473914281, 181517350571, 2608383775171, 39824825088809, 643813226048935, 10986188094959045, 197337931571468445, 3721889002400665951, 73539326922210382215, 1519081379788242418149, 32743555520207058219615, 735189675389014372317381

Offset: 1

Cyril Banderier, Mar 20 2019

nonn

The one-line notation of any permutation p has a unique factorization into runs p = B1,B2,...,Bk, where each Bi is a run (a sequence of increasing values), and the first element of B(i+1) is smaller than the last element of Bi. If the permutation p is such that each pair of adjacent runs Bi, B(i+1) have an overlapping range, that is the intervals [min(Bi),max(Bi)] and [min(B(i+1)),max(B(i+1))] have a nonempty intersection, then we say that p has overlapping runs.

a(n) is also the number of permutations of size n transformed by a pop-stack sorting (see Links below).

			For n = 3 the a(3) = 3 permutations with overlapping runs are 123, 132, 213.

Bjarki Ágúst Guðmundsson, Table of n, a(n) for n = 1..450
Andrei Asinowski, Cyril Banderier, Sara Billey, Benjamin Hackl and Svante Linusson, Pop-stack sorting and its image: Permutations with overlapping runs (2019), preprint.
Anders Claesson, Bjarki Ágúst Guðmundsson and Jay Pantone, Counting pop-stacked permutations in polynomial time, arXiv:1908.08910 [math.CO], 2019.
Colin Defant and Nathan Williams, Semidistrim Lattices, arXiv:2111.08122 [math.CO], 2021.

Cf. A001855, A008292.

Row sums of A309993.

Added more terms (from the Claesson/Guðmundsson/Pantone reference), Joerg Arndt, Aug 26 2019

Definition corrected by Bjarki Ágúst Guðmundsson, Aug 26 2019

A373709 Partial sums of A119387.

Original entry on oeis.org

0, 0, 1, 1, 3, 4, 6, 6, 9, 11, 14, 15, 18, 20, 23, 23, 27, 30, 34, 36, 40, 43, 47, 48, 52, 55, 59, 61, 65, 68, 72, 72, 77, 81, 86, 89, 94, 98, 103, 105, 110, 114, 119, 122, 127, 131, 136, 137, 142, 146, 151, 154, 159, 163, 168, 170, 175, 179, 184, 187, 192

Offset: 0

Antoine Mathys, Jun 14 2024

Antoine Mathys, Table of n, a(n) for n = 0..9999
Project Euler, Problem 704 - Factors of Two in Binomial Coefficients.

Cf. A000120, A001855, A005187, A070939, A119387.

a:= proc(n) option remember; `if`(n<0, 0,
      a(n-1)+ilog2(n+1)-padic[ordp](n+1, 2))
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Jun 23 2024

Accumulate[Table[BitLength[k] - 1 - IntegerExponent[k, 2], {k, 100}]] (* Paolo Xausa, Oct 01 2024 *)

bit_width(n)=logint(n,2)+1;
a(n)=my(d=bit_width(n+1),p=hammingweight(n+1));(n+2)*d-2*n-2^d+p-1;

a(n) = Sum_{m = 0..n} A119387(m).
a(n) = (n+2)*d - 2*n - 2^d + p - 1, with d = bit_width(n+1) = A070939(n+1) and p = popcount(n+1) = A000120(n+1).
a(n) = A001855(n+2) - A005187(n+1).

A267367 Decimal representation of the middle column of the "Rule 126" elementary cellular automaton starting with a single ON (black) cell.

Original entry on oeis.org

1, 3, 6, 13, 26, 52, 104, 209, 418, 836, 1672, 3344, 6688, 13376, 26752, 53505, 107010, 214020, 428040, 856080, 1712160, 3424320, 6848640, 13697280, 27394560, 54789120, 109578240, 219156480, 438312960, 876625920, 1753251840, 3506503681, 7013007362

Offset: 0

Robert Price, Jan 13 2016

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

Robert Price, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
Eric Weisstein's World of Mathematics, Rule 126
S. Wolfram, A New Kind of Science
Index entries for sequences related to cellular automata
Index to Elementary Cellular Automata

Cf. A267366 (binary), A001855, A071035, A267365.

A267367 := proc(n) local i, s, z; s := 0; i := n; z := 1;
while 0 <= i do s := s+2^i; i := i-z; z := z+z od; s end:
seq(A267367(n), n=0..32); # Peter Luschny, Dec 02 2017

rule=126; rows=20; ca=CellularAutomaton[rule,{{1},0},rows-1,{All,All}]; (* Start with single black cell *) catri=Table[Take[ca[[k]],{rows-k+1,rows+k-1}],{k,1,rows}]; (* Truncated list of each row *) mc=Table[catri[[k]][[k]],{k,1,rows}]; (* Keep only middle cell from each row *) Table[FromDigits[Take[mc,k],2],{k,1,rows}]  (* Binary Representation of Middle Column *)

def A267367(n):
    i, s, z = n, 0, 1
    while 0 <= i: s += 1<A267367(n) for n in range(33)]) # Peter Luschny, Dec 02 2017

A319954 Infinite word over {0,1,2} formed from list of binary words of lengths 0, 1, 2, etc., including empty word, each prefixed by a 2.

Original entry on oeis.org

2, 2, 0, 2, 1, 2, 0, 0, 2, 0, 1, 2, 1, 0, 2, 1, 1, 2, 0, 0, 0, 2, 0, 0, 1, 2, 0, 1, 0, 2, 0, 1, 1, 2, 1, 0, 0, 2, 1, 0, 1, 2, 1, 1, 0, 2, 1, 1, 1, 2, 0, 0, 0, 0, 2, 0, 0, 0, 1, 2, 0, 0, 1, 0, 2, 0, 0, 1, 1, 2, 0, 1, 0, 0, 2, 0, 1, 0, 1, 2, 0, 1, 1, 0, 2, 0, 1

Offset: 0

N. J. A. Sloane, Oct 04 2018

			The word written without commas:
220212002012102112000200120102011210021012110211120000200012001020011...

Rémy Sigrist, Table of n, a(n) for n = 0..25000
Carl Pomerance, John Michael Robson, and Jeffrey Shallit, Automaticity II: Descriptional complexity in the unary case, Theoretical computer science 180.1-2 (1997): 181-201.

Cf. A001855, A030302, A214339, A319953.

k=0; for (n=0, oo, b=binary(n+1); b[1]++; for (i=1, #b, print1 (b[i] ", "); if (k++==87, quit))) \\ Rémy Sigrist, Oct 04 2018

a(n) = A030302(n+1) + [n belongs to A001855] (where [] is an Iverson bracket). - Rémy Sigrist, Oct 04 2018

Data corrected and extended by Rémy Sigrist, Oct 04 2018

A350567 a(n) is the maximum number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Original entry on oeis.org

1, 4, 6, 10, 13, 17, 20, 25, 29, 34, 38, 43, 47, 52

Offset: 2

Hugo Pfoertner, Jan 09 2022

There are six places in the Algol 60 procedure mergesort where the keys are compared. The sequence shows the maxima of the counts of these comparisons, determined over all n! possible orders of the records.

a(16) >= 56.

D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.4 Sorting by Merging, Pages 164-166. Addison-Wesley, Reading, MA, 1998.

A. D. Woodall, An internal sorting procedure using a two-way merge, Algorithm 45, The Computer Journal, Volume 13, Number 1, February 1970, Algorithms Supplement, pp. 110-111.

A350568 provides the corresponding average numbers and a comparison table.

Cf. A001768, A001855, A350569.

A350568 a(n)/n! is the average number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Original entry on oeis.org

2, 19, 130, 992, 8145, 73665, 725630, 7840280, 92297011, 1176802235, 16129154724, 236335661166, 3685509077329, 60981635041557

Offset: 2

Hugo Pfoertner, Jan 09 2022

There are six places in the Algol 60 procedure mergesort where the keys are compared. The sequence is the sum of the counts of these comparisons, taken over all n! possible orders of the records.
The following table shows the maximum and average number of key comparisons.
.
   n  Worst case
   |  A350567(n)
   |   |  Average
   |   |  a(n)/n!
   |   |    |    Average/
   |   |    |   (n*log(n))
   2   1   1.000  0.721
   3   4   3.167  0.961
   4   6   5.417  0.977
   5  10   8.267  1.027
   6  13  11.313  1.052
   7  17  14.616  1.073
   8  20  17.997  1.082
   9  25  21.606  1.093
  10  29  25.435  1.105
  11  34  29.481  1.118
  12  38  33.672  1.129
  13  43  37.953  1.138
  14  47  42.276  1.144
  15  52  46.634  1.148

D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.4 Sorting by Merging, Pages 164-166. Addison-Wesley, Reading, MA, 1998.

A. D. Woodall, An internal sorting procedure using a two-way merge, Algorithm 45, The Computer Journal, Volume 13, Number 1, February 1970, Algorithms Supplement, pp. 110-111.

Cf. A001768, A001855, A350567, A350569.

A123535 Recurrence from values at floor of a third and two-thirds.

Original entry on oeis.org

1, 4, 8, 16, 17, 26, 32, 33, 43, 58, 59, 61, 73, 74, 90, 101, 102, 105, 124, 125, 127, 145, 146, 158, 170, 171, 175, 210, 211, 213, 217, 218, 237, 241, 242, 255, 280, 281, 283, 289, 290, 326, 344, 345, 348, 364, 365, 367, 388, 389, 394, 399, 400, 414, 459, 460

Offset: 0

Jonathan Vos Post, Nov 11 2006

Roughly analogous to maximal number of comparisons for sorting n elements by binary insertion (A001855).

			a(0) = 1 by definition.
a(1) = a(floor(1/3)) + a(floor(2/3)) + 1 + 1 = a(0) + a(0) + 2 = 4.
a(2) = a(floor(2/3)) + a(floor(4/3)) + 2 + 1 = a(0) + a(1) + 3 = 8.
a(3) = a(floor(3/3)) + a(floor(6/3)) + 3 + 1 = a(1) + a(2) + 4 = 16.
a(4) = a(floor(4/3)) + a(floor(8/3)) + 4 + 1 = a(1) + a(2) + 5 = 17.
a(5) = a(floor(5/3)) + a(floor(10/3)) + 5 + 1 = a(1) + a(3) + 6 = 26.
a(6) = a(floor(6/3)) + a(floor(12/3)) + 6 + 1 = a(2) + a(4) + 7 = 32.

Paolo Xausa, Table of n, a(n) for n = 0..10000
Wikipedia, Akra-Bazzi method.

Cf. A001768, A001855, A029837, A003071, A000337, A030190, A030308, A061168.

A123535 := proc(n) options remember ; if n = 0 then RETURN(1) ; else RETURN(A123535(floor(n/3))+A123535(floor(2*n/3))+n+1) ; fi ; end: for n from 0 to 100 do printf("%d,",A123535(n)) ; od : # R. J. Mathar, Jan 13 2007

a[0] = 1; a[n_] := a[n] = a[Floor[n/3]] + a[Floor[2*n/3]] + n + 1;
Array[a, 100, 0] (* Paolo Xausa, Jun 27 2024 *)

a(0) = 1, for n>0: a(n) = a(floor(n/3)) + a(floor(2n/3)) + n + 1.

Corrected and extended by R. J. Mathar, Jan 13 2007

a(0)=1 prepended by Paolo Xausa, Jun 27 2024

A130067 Binomial coefficients binomial(m,2^k) where m>=1 and 1<=2^k<=m.

Original entry on oeis.org

1, 2, 1, 3, 3, 4, 6, 1, 5, 10, 5, 6, 15, 15, 7, 21, 35, 8, 28, 70, 1, 9, 36, 126, 9, 10, 45, 210, 45, 11, 55, 330, 165, 12, 66, 495, 495, 13, 78, 715, 1287, 14, 91, 1001, 3003, 15, 105, 1365, 6435, 16, 120, 1820, 12870, 1, 17, 136, 2380, 24310, 17, 18, 153, 3060, 43758

Offset: 1

Hieronymus Fischer, May 05 2007, Sep 10 2007

nonn

Provided m and k are given, the sequence index n is n=A001855(m)+k+1. Ordered by m as rows and k as columns the sequence forms a sort of a logarithmically distorted triangle. a(n) is odd if and only if A030308(n)=1.

			a(6)=4 since n=6 gives m=4, k=0 and so binomial(4,2^0)=4.
a(20)=70 since n=20 gives m=8, k=2 and so binomial(8,2^2)=70.

Cf. A130068, A065040, A001855, A030308.

a(n)=binomial(m,2^k), where m=max(j|A001855(j)A001855(m).

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

A301336 a(n) = total number of 1's minus total number of 0's in binary expansions of 0, ..., n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

A307030 Number of permutations of [n] with overlapping adjacent runs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A373709 Partial sums of A119387.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A267367 Decimal representation of the middle column of the "Rule 126" elementary cellular automaton starting with a single ON (black) cell.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

A319954 Infinite word over {0,1,2} formed from list of binary words of lengths 0, 1, 2, etc., including empty word, each prefixed by a 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A350567 a(n) is the maximum number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A350568 a(n)/n! is the average number of key comparisons required to perform an indirect sort of n records with distinct keys using a two-way merge (A. D. Woodall's mergesort).

Views

Author

Keywords