A119387 -id:A119387 - cp's OEIS frontend

A373709 Partial sums of A119387.

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

A101279 a(1) = 1; a(2k) = a(k), a(2k+1) = k.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, May 22 2006; definition corrected May 23 2006

nonn

From Jeremy Gardiner, Mar 22 2015: (Start)
For n > 2 write n, n-1 in binary, then align bits from the left and take contiguous matching bits as a binary number.
For example:
n    = 19 10011
n-1  = 18 10010
a(n) =  9 1001
Also arrange the positive integers as a binary tree rooted at 1 as shown:
                                     1
                                     |
                 2................../ \..................3
                 |                                       |
       4......../ \........5                   6......../ \........7
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
   8       9          10      11          12       13         14       15
16 17   18 19      20  21  22  23      24  25   26  27     28  29   30  31
Each branch doubles the number above at the left fork or doubles and adds 1 at the right fork. Then for n > 2, a(n) is the greatest common ancestor of n and n-1, a(n) = gca(n,n-1).
(End)
From David James Sycamore, Mar 07 2023: (Start)
The following identical sequences, {b(n)} and {c(n)}, are the same as a(n+1) for n >= 1.
b(1) = 1, then reverse the conditions in Name: b(2k) = k, b(2k+1) = b(k).
c(1) = 1, then if c(n) is a first occurrence, c(n+1) = c(c(n)), else if c(n) has occurred previously, c(n+1) = n - c(n-1).
These are fractal sequences (b(2m+1) = c(2m+1), m >= 1, recovers the originals). Also {b(n)} and {c(n)} interleave A000027 with the present sequence.
(End)

			If n is a power of 2 then k=1.

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A003602, A025480.

cf. A000027, A000079, A007283, A070939, A119387. - David James Sycamore, Mar 07 2023

a:=array(0..200); a[1]:=1; M:=200; for n from 2 to M do if n mod 2 = 1 then a[n]:=(n-1)/2; else a[n]:=a[n/2]; fi; od: [seq(a[n],n=1..M)];

a[1] = 1; a[n_] := a[n] = If[OddQ@n, (n - 1)/2, a[n/2]]; Array[a, 84] (* Robert G. Wilson v, May 23 2006 *)

a(n)=(n/2^valuation(n,2)-1)/2+if(n==2^valuation(n,2),1,0) /* Ralf Stephan, Aug 21 2013 */

a((n+1)/2) = A028310(n) if n is odd and a(n/2) = a(n) if n is even; thus this is a fractal sequence. - Robert G. Wilson v, May 23 2006; corrected by Clark Kimberling, Jul 07 2007
a(n) = A025480(n) + A036987(n) = (n/2^A007814(n) - 1)/2 + (n == 2^A007814(n)). - Ralf Stephan, Aug 21 2013
If n is a power of 2, A070939(a(n)) = 1, otherwise A070939(a(n)) = A119387(n-1).
Numbers m for which a(m) = 1 are A000079(m) and A007283(m), a(2^m + 1) = 2^(m-1); m >= 1. - David James Sycamore, Mar 07 2023

A285097 a(n) = difference between the positions of two least significant 1-bits in base-2 representation of n, or 0 if there are less than two 1-bits in n (when n is either zero or a power of 2).

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 1, 1, 0, 3, 2, 1, 1, 2, 1, 1, 0, 4, 3, 1, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0, 5, 4, 1, 3, 2, 1, 1, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 1, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0, 6, 5, 1, 4, 2, 1, 1, 3, 3, 2, 1, 1, 2, 1, 1, 2, 4, 3, 1, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 4, 1, 3, 2, 1, 1, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 1, 2, 2, 1, 1, 1

Offset: 0

Antti Karttunen, Apr 20 2017

a(1+n) is the length of the least significant run of 0-bits in n, or 0 if n is one of terms of A000225. - Antti Karttunen, Oct 14 2023

			For n = 3, "11" in binary, the second least significant 1-bit (the second 1-bit from the right) is at position 1 and the rightmost 1-bit is at position 0, thus a(3) = 1-0 = 1.
For n = 4, "100" in binary, there is just one 1-bit present, thus a(4) = 0.
For n = 5, "101" in binary, the second 1-bit from the right is at position 2, and the least significant 1 is at position 0, thus a(5) = 2-0 = 2.
For n = 26, "11010" in binary, the second 1-bit from the right is at position 3, and the least significant 1 is at position 1, thus a(26) = 3-1 = 2.

Antti Karttunen, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

Cf. A000120, A000225, A000265, A007814, A119387, A129760, A285099, A366370.

a007814[n_]:=IntegerExponent[n, 2]; a285099[n_]:=If[DigitCount[n, 2, 1]<2, 0, a007814[BitAnd[n, n - 1]]]; a[n_]:=If[DigitCount[n, 2, 1]<2, 0,a285099[n] - a007814[n]]; Table[a[n], {n, 0, 150}] (* Indranil Ghosh, Apr 20 2017 *)

A285097(n) = if(!n || !bitand(n,n-1), 0, valuation((n>>valuation(n,2))-1, 2)); \\ Antti Karttunen, Oct 14 2023

import math
def a007814(n): return int(math.log(n - (n & n - 1), 2))
def a285099(n): return 0 if bin(n)[2:].count("1") < 2 else a007814(n & (n - 1))
def a(n): return 0 if bin(n)[2:].count("1")<2 else a285099(n) - a007814(n) # Indranil Ghosh, Apr 20 2017

(define (A285097 n) (if (<= (A000120 n) 1) 0 (- (A285099 n) (A007814 n))))

If A000120(n) < 2, a(n) = 0, otherwise a(n) = A285099(n) - A007814(n) = A007814(A129760(n)) - A007814(n).

a(n) = 0 if n is 0 or of the form 2^k, (k>=0), otherwise a(n) = v_2(A000265(n)-1), where v_2(i) = A007814(i). - Ridouane Oudra, Oct 20 2019

A087910 Exponent of the greatest power of 2 dividing the numerator of 2^1/1 + 2^2/2 + 2^3/3 + ... + 2^n/n.

Original entry on oeis.org

1, 2, 2, 5, 8, 5, 5, 13, 9, 10, 10, 12, 12, 12, 12, 22, 17, 18, 18, 21, 22, 21, 21, 27, 25, 26, 26, 27, 27, 27, 27, 40, 33, 34, 34, 37, 39, 37, 37, 48, 41, 42, 42, 44, 44, 44, 44, 54, 49, 50, 50, 53, 54, 53, 53, 58, 57, 59, 62, 58, 58, 58

Offset: 1

Robin Chapman, Oct 17 2003

Problem 9 of the 2002 Sydney University Mathematical Society Problems competition asked for a proof that a(n) tends to infinity with n. While this is immediate from the theory of the 2-adic logarithm, elementary proofs are available.

a(n) tends to infinity with n implies that log(-1) = 0 in the 2-adic field, by setting x = 2 in -log(1-x) = Sum_{k>=1} x^k/k. - Jianing Song, Aug 05 2019

			a(5) = 8 as 2^1/1 + 2^2/2 + 2^3/3 + 2^4/4 + 2^5/5 = 256/15 whose numerator is divisible by 2^8 but not by 2^9.

A. M. Robert, A Course in p-adic Analysis, Springer, 2000; see p. 278.

Robert Israel, Table of n, a(n) for n = 1..5000
Sydney University Mathematical Society Problems Competitions, see Problem 9 of the 2002 competition.

Cf. A108866, A007814, A119387, A000523.

S:= 0:
for n from 1 to 100 do
  S:= S + 2^n/n;
  a[n]:= padic:-ordp(numer(S),2);
od:
seq(a[n],n=1..100); # Robert Israel, Jun 09 2015

s[n_] := -2^(n + 1) LerchPhi[2, 1, n + 1] - I Pi;
a[n_] := IntegerExponent[Numerator[Simplify[s[n]]], 2];
Array[a, 62] (* Peter Luschny, Feb 22 2020 *)

a(n) = valuation(sum(k=1,n,2^k/k), 2) \\ Jianing Song, Feb 22 2020

a(n) = A007814(A108866(n)). - Michel Marcus, Feb 22 2020

Sum_{k=1..n} 2^k/k = (2^n/n)*Sum_{k=0..n-1} 1/binomial(n-1,k), so a(n) >= n - v(n,2) - max_{k=0..n-1} v(binomial(n-1,k),2) = n - A007814(n) - A119387(n) = n - floor(log_2(n)), where v(n,2) is the 2-adic valuation of n. It seems that the equality holds if and only if n = 2^m - 1 for some m. - Jianing Song, Feb 22 2020

A220645 T(n,k): number of binomial coefficients C(n,r), for 0 <= r <= n, divisible by 2^k.

Original entry on oeis.org

1, 2, 0, 3, 1, 0, 4, 0, 0, 0, 5, 3, 2, 0, 0, 6, 2, 0, 0, 0, 0, 7, 3, 1, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 9, 7, 6, 4, 0, 0, 0, 0, 0, 10, 6, 4, 0, 0, 0, 0, 0, 0, 0, 11, 7, 3, 2, 0, 0, 0, 0, 0, 0, 0, 12, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 9, 7, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Michel Marcus, Dec 17 2012

Since the sum of binomial coefficients of the n-th row of Pascal's triangle is 2^n, T(n, k)=0 for k >= n. So only n elements, from k=0 to n-1, will be displayed at row n, giving a triangle instead of a table.

The number A119387(n) gives the position of the last positive number in each row. - T. D. Noe, Dec 18 2012

			Triangle starts:
0: 1
1: 2 0
2: 3 1 0
3: 4 0 0 0
4: 5 3 2 0 0
5: 6 2 0 0 0 0
For n=4, the corresponding Pascal's triangle row is:
1 4 6 4 1,
with 5 numbers divisible by 2^0,
and 3 numbers divisible by 2^1,
and 2 numbers divisible by 2^2,
and 0 numbers divisible by 2^3,
and 0 numbers divisible by 2^4.

T. D. Noe, Rows n = 0..100 of triangle, flattened
F. T. Howard, The number of binomial coefficients divisible by a fixed power of 2, Proc. Amer. Math. Soc. 29 (1971), 236-242

Cf. A000079, A007318.

Flatten[Table[b = Binomial[n, Range[0, n]]; Table[Count[b, ?(Mod[#, 2^k] == 0 &)], {k, 0, n}], {n, 0, 12}]] (* _T. D. Noe, Dec 18 2012 *)

A381810 Array read by downward antidiagonals: A(n,k) is a generalization of odd columns of A125790 defined in Comments for n > 0, k >= 0.

Original entry on oeis.org

2, 4, 4, 6, 16, 6, 8, 36, 20, 10, 10, 64, 42, 84, 14, 12, 100, 72, 286, 100, 20, 14, 144, 110, 680, 322, 120, 26, 16, 196, 156, 1330, 744, 364, 140, 36, 18, 256, 210, 2300, 1430, 816, 406, 656, 46, 20, 324, 272, 3654, 2444, 1540, 888, 3396, 740, 60, 22, 400, 342, 5456, 3850, 2600, 1650, 10816, 3682, 840, 74

Offset: 1

Mikhail Kurkov, May 05 2025

This is generalization in the sense that first column of A125790 is A000123(2^(n-1)) while in this square array column zero is conjecturally A000123(n).
A(n,k) = v_{A001511(n)} where we start with vector v of fixed length L(n) = A070939(n) with elements v_i = A125790(i,2*k+1), pre-calculate A078121 up to L(n)-th row, reserve t as an empty vector of fixed length L(n) and for i=1..A119387(n+1), for j=1..L(n)-i+1 apply t := v (at the beginning of each cycle for i) and also apply v_j := Sum_{k=1..j+1} A078121(j,k-1)*t_k if R(n,L(n)-i) = 1, otherwise v_j := Sum_{k=1..j+1} A078121(j,k-1)*t_k*(-1)^(j+k+1). Here R(n,k) = floor(n/(2^k)) mod 2 is the (k+1)-th bit in the binary expansion of n.
Conjecture: sequence A(n,k) for fixed n is a polynomial of degree A070939(n).

			Array begins:
===========================================================
n\k|  0    1     2      3      4      5       6       7 ...
---+-------------------------------------------------------
1  |  2,   4,    6,     8,    10,    12,     14,     16 ...
2  |  4,  16,   36,    64,   100,   144,    196,    256 ...
3  |  6,  20,   42,    72,   110,   156,    210,    272 ...
4  | 10,  84,  286,   680,  1330,  2300,   3654,   5456 ...
5  | 14, 100,  322,   744,  1430,  2444,   3850,   5712 ...
6  | 20, 120,  364,   816,  1540,  2600,   4060,   5984 ...
7  | 26, 140,  406,   888,  1650,  2756,   4270,   6256 ...
8  | 36, 656, 3396, 10816, 26500, 55056, 102116, 174336 ...
  ...

Cf. A000123, A001511, A007814, A053645, A062383, A070939, A078121, A106400, A119387, A125790, A236206.

upto1(n) = my(v1); v1 = vector(n+1, i, vector(i, j, j==1 || j==i)); for(i=2, n, for(j=1, i-1, v1[i+1][j+1] = sum(k=j-1, i-1, v1[i][k+1]*v1[k+1][j]))); v1
A(n,m) = my(L = logint(n,2), A = valuation(n,2), B = logint(n>>A,2), v1, v2, v3); v1 = upto1(L+2); v2 = vector(L+2, i, vecsum(v1[i])); for(i=1, 2*m, v2 = vector(L+2, i, sum(j=1, i, v1[i][j]*v2[j]))); for(i=1, B, v3 = v2; for(j=1, L-i+1, v2[j+1] = sum(k=1, j+1, v1[j+1][k]*v3[k+1]*if(!bittest(n,L-i+1), (-1)^(j+k+1), 1)))); v2[A+2]

upto1(n) = my(v1); v1 = vector(n+1, i, vector(i, j, j==1 || j==i)); for(i=2, n, for(j=1, i-1, v1[i+1][j+1] = sum(k=j-1, i-1, v1[i][k+1]*v1[k+1][j]))); v1
upto2(n,m) = my(L = logint(n,2), A = valuation(n,2), B = logint(n>>A,2), v1, v2, v3, v4, v5); v1 = upto1(L+2); v2 = vector(L+2, i, 1); v3 = vector(m+1, i, 0); for(s=0, m, for(i=1, min(s+1,2), v2 = vector(L+2, i, sum(j=1, i, v1[i][j]*v2[j]))); v4 = v2; for(i=1, B, v5 = v4; for(j=1, L-i+1, v4[j+1] = sum(k=1, j+1, v1[j+1][k]*v5[k+1]*if(!bittest(n,L-i+1), (-1)^(j+k+1), 1)))); v3[s+1] = v4[A+2]); v3 \\ slightly modified version of the first program, some kind of memoization; generates A(n,k) for k=0..m

A(2^(n-1),k) = A125790(n,2*k+1) for n > 0, k >= 0.
Conjectured formulas: (Start)
A(n,0) = A000123(n) for n > 0.
A(n,k) = Sum_{j=0..k} A000123(A062383(n)*j+n)*A106400(k-j) for n > 0, k >= 0.
If we change v_i = A125790(i,2*k+1) to v_i = A125790(i,2*k) to get similar generalization of even columns, then for resulting array B(n,k) we have B(n,k) = Sum_{j=0..k} A000123(A062383(n)*j+A053645(n))*A106400(k-j) for n > 0, k >= 0.
2*(k+1) divides A(n,k) for n > 0 if (k+1) is a term of A236206.
G.f. for n-th row is f(A070939(n)+1,n) for n > 0 where f(n,k) = (Sum_{(c_0 + c_1 + ... + c_{n-1}) == 2*k (mod 2^n), 0 <= c_i < 2^n, 2^i divides c_i} x^((c_0 + c_1 + ... + c_{n-1} - 2*k)/2^n))/(1-x)^n for n > 0, k >= 0. Similarly, g.f. for n-th row of B(n,k) is f(A070939(n)+1,A053645(n)).
G.f. for n-th row is (Sum_{i=0..L(n)-1} x^i * Sum_{j=0..i} binomial(L(n)+1,j)*A(n,i-j)*(-1)^j)/(1-x)^(L(n)+1) for n > 0 where L(n) = A070939(n).
s(4*n+1) = 1 for n >= 0, s(4*n) = s(4*n+2) = 1 if A010060(n) = 1 for n > 0 where s(n) = A007814(Sum_{k=0..n-1} A(k+1,n-k-1)). (End)

cp's OEIS Frontend

A373709 Partial sums of A119387.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A101279 a(1) = 1; a(2k) = a(k), a(2k+1) = k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A285097 a(n) = difference between the positions of two least significant 1-bits in base-2 representation of n, or 0 if there are less than two 1-bits in n (when n is either zero or a power of 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Scheme

Formula

A087910 Exponent of the greatest power of 2 dividing the numerator of 2^1/1 + 2^2/2 + 2^3/3 + ... + 2^n/n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A220645 T(n,k): number of binomial coefficients C(n,r), for 0 <= r <= n, divisible by 2^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A381810 Array read by downward antidiagonals: A(n,k) is a generalization of odd columns of A125790 defined in Comments for n > 0, k >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

Formula