A130068 Maximal power of 2 dividing the binomial coefficient binomial(m, 2^k) where m >= 1 and 1 <= 2^k <= m.
0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 3, 2, 1, 0, 0, 2, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 2, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 3, 2, 1, 0, 0, 3, 2, 1, 0, 1, 0, 2, 1, 0, 0, 0, 2, 1, 0, 2, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 3, 2, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0
Offset: 1
Examples
a(6)=2 since 2^2 divides binomial(4,2^0)=4 and 2^3 is not a factor (here n=6 gives m=4, k=0). a(20)=1 since 2^1 divides binomial(8,2^2)=70 and 2^2 is not a factor (here n=20 gives m=8, k=2).
Formula
a(n)=g(m)-g(m-2^k) where g(x)=sum(floor(x/2^i), kA001855(j)A001855(m). Also true: a(n)=sum(product(1-b(i), k<=i
A279539 Sum of ceilings of natural logs of first n integers.
0, 1, 3, 5, 7, 9, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 114, 118, 122, 126, 130, 134, 138, 142, 146, 150, 154, 158, 162, 166, 170, 174, 178, 182, 186, 191, 196, 201, 206, 211, 216, 221, 226, 231, 236, 241, 246, 251, 256, 261, 266, 271, 276, 281, 286
Offset: 1
Keywords
Links
- Paolo Xausa, Table of n, a(n) for n = 1..10000
Programs
-
Mathematica
Accumulate[Ceiling[Log[Range[100]]]] (* Paolo Xausa, Jun 28 2024 *)
-
PARI
a(n) = sum(i=1, n, ceil(log(i))) \\ Felix Fröhlich, Dec 14 2016
A295513 a(n) = n*bil(n) - 2^bil(n) where bil(0) = 0 and bil(n) = floor(log_2(n)) + 1 for n>0.
-1, -1, 0, 2, 4, 7, 10, 13, 16, 20, 24, 28, 32, 36, 40, 44, 48, 53, 58, 63, 68, 73, 78, 83, 88, 93, 98, 103, 108, 113, 118, 123, 128, 134, 140, 146, 152, 158, 164, 170, 176, 182, 188, 194, 200, 206, 212, 218, 224, 230, 236, 242, 248, 254, 260, 266, 272, 278
Offset: 0
Keywords
Links
- 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.
Programs
-
Maple
A295513 := proc(n) local i, s, z; s := -1; i := n-1; z := 1; while 0 <= i do s := s+i; i := i-z; z := z+z od; s end: seq(A295513(n), n=0..57);
-
Mathematica
a[n_] := n IntegerLength[n, 2] - 2^IntegerLength[n, 2]; Table[a[n], {n, 0, 58}] -
Python
def A295513(n): return n*(m:=(n-1).bit_length())-(1<
A356254 Given n balls, all of which are initially in the first of n numbered boxes, a(n) is the number of steps required to get one ball in each box when a step consists of moving to the next box every second ball from the highest-numbered box that has more than one ball.
0, 1, 3, 5, 9, 13, 18, 23, 31, 39, 47, 56, 67, 78, 91, 103, 119, 135, 150, 167, 185, 203, 223, 243, 266, 289, 313, 337, 364, 391, 420, 447, 479, 511, 541, 574, 607, 640, 675, 711, 749, 787, 826, 865, 907, 949, 993, 1036, 1083, 1130, 1177, 1225, 1275, 1325, 1377
Offset: 1
Keywords
Comments
Examples
For n = 5, the number of balls in each box at each step is as follows:
.
| Boxes
Step | #1 #2 #3 #4 #5
-----+-------------------
0 | 5
1 | 3 2
2 | 3 1 1
3 | 2 2 1
4 | 2 1 2
5 | 2 1 1 1
6 | 1 2 1 1
7 | 1 1 2 1
8 | 1 1 1 2
9 | 1 1 1 1 1
.
Thus, a(5) = 9.
Links
- Peter J. Taylor, Recurrence for the number of steps required to get one ball in each box, answer to question on Mathoverflow.
Programs
-
PARI
a(n)=my(A, B, v); v=vector(n, i, 0); v[1]=n; A=0; while(v[n]==0, B=n; while(v[B]<2, B--); v[B+1]+=v[B]\2; v[B]-=v[B]\2; A++); A
Formula
If n = 2^k, then a(n) = (n/2)*(n + 1 - k) - 1. - Jon E. Schoenfield, Oct 17 2022
Define s(n) = floor(n/2) - 1 + s(floor(n/2)) + A181132(ceiling(n/2) - 2) for n > 3, 0 otherwise. Then a(n) = n*(n-1)/2 - s(n). - Jon E. Schoenfield, Oct 18 2022
Comments