A080100 -id:A080100 - cp's OEIS frontend

A351886 a(n) is the number of k < n such that a(k) AND n = 0 (where AND denotes the bitwise AND operator).

0, 1, 2, 1, 4, 2, 3, 1, 8, 4, 6, 3, 8, 3, 4, 1, 16, 9, 11, 6, 14, 5, 8, 4, 17, 9, 10, 5, 10, 3, 5, 1, 32, 16, 21, 10, 24, 12, 15, 7, 26, 11, 17, 7, 16, 6, 11, 4, 39, 19, 20, 10, 24, 10, 11, 4, 26, 12, 15, 7, 12, 3, 6, 1, 64, 34, 34, 20, 41, 21, 21, 10, 45, 21

Offset: 0

Rémy Sigrist, Feb 23 2022

The definition is recursive: a(n) depends on prior terms (a(0), ..., a(n-1)); a(0) = 0 corresponds to an empty sum.

			The first terms, alongside the corresponding k's, are:
  n   a(n)  k's
  --  ----  -------------------------
   0     0  {}
   1     1  {0}
   2     2  {0, 1}
   3     1  {0}
   4     4  {0, 1, 2, 3}
   5     2  {0, 2}
   6     3  {0, 1, 3}
   7     1  {0}
   8     8  {0, 1, 2, 3, 4, 5, 6, 7}
   9     4  {0, 2, 4, 5}
  10     6  {0, 1, 3, 4, 7, 9}
  11     3  {0, 4, 9}
  12     8  {0, 1, 2, 3, 5, 6, 7, 11}

Rémy Sigrist, Table of n, a(n) for n = 0..10000

Cf. A080100, A088167, A350677, A351887.

a:= proc(n) option remember; add(
     `if`(Bits[And](n, a(j))=0, 1, 0), j=0..n-1)
    end:
seq(a(n), n=0..80);  # Alois P. Heinz, Feb 28 2022

for (n=1, #a=vector(75), print1 (a[n]=sum(k=1, n-1, bitand(a[k], n-1)==0)", "))

a = []
[a.append(sum(a[k] & n == 0 for k in range(n))) for n in range(74)]
print(a) # Michael S. Branicky, Feb 24 2022

a(2^k) = 2^k.

A372331 The number of infinitary divisors of the smallest number k such that k*n is a number whose number of divisors is a power of 2 (A036537).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 4, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 4, 4, 1, 1, 2, 1, 1, 1

Offset: 1

Amiram Eldar, Apr 28 2024

First differs from A370077 and A370080 at n = 32.
The number of divisors d of n that are infinitarily relatively prime to n (see A064379), i.e., d have no common infinitary divisors with n.
Equivalently, the number of divisors d of n such that for each prime divisor p of d, bitand(v_p(n), v_p(d)) = 0, where v_p(k) is the highest power of p that divides k. Note that for infinitary divisors d of n (A077609), bitand(v_p(n), v_p(d)) = v_p(d).

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A036537, A037445, A064379, A077609, A080100, A372328.

Cf. A370077, A370080.

f[p_, e_] := 2^DigitCount[e, 2, 0]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = vecprod(apply(x -> 2^(logint(x, 2) + 1 - hammingweight(x)), factor(n)[, 2]));

a(n) = A037445(A372328(n)).
Multiplicative with a(p^e) = 2^A023416(e) = A080100(e).
a(n) = 1 if and only if n is in A036537.
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Product_{p prime} (1 + Sum_{k>=1} A080100(k)/p^k) = 1.51209151045338102469... .

A115378 a(n) = number of positive integers k < n such that n XOR k = (n+k).

Original entry on oeis.org

0, 1, 0, 3, 1, 1, 0, 7, 3, 3, 1, 3, 1, 1, 0, 15, 7, 7, 3, 7, 3, 3, 1, 7, 3, 3, 1, 3, 1, 1, 0, 31, 15, 15, 7, 15, 7, 7, 3, 15, 7, 7, 3, 7, 3, 3, 1, 15, 7, 7, 3, 7, 3, 3, 1, 7, 3, 3, 1, 3, 1, 1, 0, 63, 31, 31, 15, 31, 15, 15, 7, 31, 15, 15, 7, 15, 7, 7, 3, 31, 15, 15, 7, 15, 7, 7, 3, 15, 7, 7, 3, 7, 3

Offset: 1

Paul D. Hanna, Jan 21 2006

nonn

The number of positive integers k < n such that n XOR k = (n-k) is A038573(n).

Cf. A080791, A080100, A038573.

a(n)=sum(k=1,n,if(bitxor(n,k)==(n+k),1,0))

a(n) = -1 + 2^(number of 0's in binary expansion of n). a(n) = 2^A080791(n) - 1 = A080100(n) - 1.

A166556 Triangle read by rows, A000012 * A047999.

Original entry on oeis.org

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

Offset: 0

Gary W. Adamson, Oct 17 2009

			First few rows of the triangle =
   1;
   2, 1;
   3, 1, 1;
   4, 2, 2, 1;
   5, 2, 2, 1, 1;
   6, 3, 2, 1, 2, 1;
   7, 3, 3, 1, 3, 1, 1;
   8, 4, 4, 2, 4, 2, 2, 1;
   9, 4, 4, 2, 4, 2, 2, 1, 1;
  10, 5, 4, 2, 4, 2, 2, 1, 2, 1;
  11, 5, 5, 2, 4, 2, 2, 1, 3, 1, 1;
  12, 6, 6, 3, 4, 2, 2, 1, 4, 2, 2, 1;
  13, 6, 6, 3, 5, 2, 2, 1, 5, 2, 2, 1, 1;
  ...

G. C. Greubel, Rows n = 0..100 of the triangle, flattened

Cf. A000027, A004524, A004526, A047999, A080100.

Sums include: A006046 (row), A007729 (diagonal).

A166556:= func< n,k | (&+[(Binomial(j,k) mod 2): j in [k..n]]) >;
[A166556(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Dec 02 2024

A166556 := proc(n,k)
    local j;
    add(A047999(j,k),j=k..n) ;
end proc: # R. J. Mathar, Jul 21 2016

A166556[n_, k_]:= Sum[Mod[Binomial[j,k], 2], {j,k,n}];
Table[A166556[n,k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Dec 02 2024 *)

def A166556(n,k): return sum(binomial(j,k)%2 for j in range(k,n+1))
print(flatten([[A166556(n,k) for k in range(n+1)] for n in range(13)])) # G. C. Greubel, Dec 02 2024

Triangle read by rows, A000012 * A047999; where A000012 = an infinite lower triangular matrix with all 1's: [1; 1,1; 1,1,1;..]; and A047999 = Sierpinski's gasket.
The operation takes partial sums of Sierpinski's gasket terms, by columns.
From G. C. Greubel, Dec 02 2024: (Start)
T(n, k) = Sum_{j=k..n} (binomial(j,k) mod 2).
T(n, 0) = A000027(n+1).
T(n, 1) = A004526(n+1).
T(n, 2) = A004524(n+1).
T(2*n, n) = A080100(n).
Sum_{k=0..n} T(n, k) = A006046(n+1).
Sum_{k=0..n} (-1)^k*T(n, k) = A006046(floor(n/2)+1).
Sum_{k=0..floor(n/2)} T(n-k, k) = A007729(n). (End)

A268514 a(0)=0; thereafter a(2n+1)=3a(n)+1, a(2n)=2a(n)+a(n-1)+1.

Original entry on oeis.org

0, 1, 3, 4, 8, 10, 12, 13, 21, 25, 29, 31, 35, 37, 39, 40, 56, 64, 72, 76, 84, 88, 92, 94, 102, 106, 110, 112, 116, 118, 120, 121, 153, 169, 185, 193, 209, 217, 225, 229, 245, 253, 261, 265, 273, 277, 281, 283, 299, 307, 315, 319, 327, 331, 335, 337

Offset: 0

N. J. A. Sloane, Feb 07 2016

nonn

Colin Barker, Table of n, a(n) for n = 0..1000

Cf. A064194, A023416 (no. of 0's in n).

First differences are (essentially) A080100.

a(n) = sum(i=1, n, b=binary(i); 2^(#b-norml2(b))) \\ Colin Barker, Feb 08 2016

a(n) = Sum{i=1..n} 2^{number of 0's in binary expansion of i}.

a(n) = (A064194(n+1)-1)/2.

A298372 a(n), in decimal base, is the number of numbers k >= 0 with no more digits than n such that k + n can be computed without carry.

Original entry on oeis.org

1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 90, 81, 72, 63, 54, 45, 36, 27, 18, 9, 80, 72, 64, 56, 48, 40, 32, 24, 16, 8, 70, 63, 56, 49, 42, 35, 28, 21, 14, 7, 60, 54, 48, 42, 36, 30, 24, 18, 12, 6, 50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 40, 36, 32, 28, 24, 20, 16, 12, 8

Offset: 0

Rémy Sigrist, Jan 18 2018

We consider here that 0 has no digit, and hence a(0) = 1.

The corresponding sequence for the binary base is A080100.

			a(42) = (10 - 4) * (10 - 2) = 48.

Rémy Sigrist, Table of n, a(n) for n = 0..9999

Cf. A080100, A100910.

a(n, {base=10}) = my (d=digits(n, base)); prod(i=1, #d, base-d[i])

a(0) = 1.
a(10 * k + d) = a(k) * (10 - d) when 10 * k + d > 0 and 0 <= d < 10.
a(n) = Product_{ d = 0..9 } (10 - d)^A100910(n, d) for any n > 0.

A335587 a(n) is the sum of the numbers k such that 0 <= k <= n and n AND k = 0 (where AND denotes the bitwise AND operator).

Original entry on oeis.org

0, 0, 1, 0, 6, 2, 1, 0, 28, 12, 10, 4, 6, 2, 1, 0, 120, 56, 52, 24, 44, 20, 18, 8, 28, 12, 10, 4, 6, 2, 1, 0, 496, 240, 232, 112, 216, 104, 100, 48, 184, 88, 84, 40, 76, 36, 34, 16, 120, 56, 52, 24, 44, 20, 18, 8, 28, 12, 10, 4, 6, 2, 1, 0, 2016, 992, 976, 480

Offset: 0

Rémy Sigrist, Apr 21 2021

All terms can be written as m * 2^A000120(m) for some m >= 0.

			For n = 4:
- 4 AND 0 = 0,
- 4 AND 1 = 0,
- 4 AND 2 = 0,
- 4 AND 3 = 0,
- 4 AND 4 = 4,
- so a(4) = 0 + 1 + 2 + 3 = 6.

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Rémy Sigrist, Colored logarithmic scatterplot of the sequence for n < 2^16 (where the color is function of A080791(n))
Index entries for sequences related to binary expansion of n

Cf. A000120, A004198 (bitwise AND), A006516, A035327, A080100, A080791.

a(n) = sum(k=0, n, if (bitand(n, k)==0, k, 0))

a(n) = my (w=#binary(n)); ( (2^w-1-n) * 2^(w-hammingweight(n)) ) \ 2

a(n) = A035327(n) * A080100(n) / 2 for any n > 0.
a(2*n+1) = 2*a(n).
a(2^k-1) = 0 for any k >= 0.
a(2^k) = A006516(k) for any k >= 0.

A353292 a(n) is the number of positive integers k <= n that have at least one common 1-bit with n.

Original entry on oeis.org

0, 1, 1, 3, 1, 4, 5, 7, 1, 6, 7, 10, 9, 12, 13, 15, 1, 10, 11, 16, 13, 18, 19, 22, 17, 22, 23, 26, 25, 28, 29, 31, 1, 18, 19, 28, 21, 30, 31, 36, 25, 34, 35, 40, 37, 42, 43, 46, 33, 42, 43, 48, 45, 50, 51, 54, 49, 54, 55, 58, 57, 60, 61, 63, 1, 34, 35, 52, 37

Offset: 0

Rémy Sigrist, Apr 09 2022

See A353293 for the corresponding k's.

			For n = 10:
- we have:
      k   10 AND k
      --  --------
       1         0
       2         2
       3         2
       4         0
       5         0
       6         2
       7         2
       8         8
       9         8
      10        10
- so a(10) = #{2, 3, 6, 7, 8, 9, 10} = 7.

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

Cf. A062050, A080100, A088512, A115378, A353293.

a(n) = { my (h=hammingweight(n), w=#binary(n)); n-2^(w-1)+1 + (2^(h-1)-1)*2^(w-h) }

a(n) = n - A115378(n) for any n > 0.
a(n) = A062050(n) + A088512(n) * A080100(n) for any n > 0.
a(2^k) = 1 for any k >= 0.
a(2^k - 1) = 2^k - 1 for any k >= 0.

A219218 G.f. satisfies: A(x) = Sum_{n>=0} [A(x)^(2n) (mod 3)]x^n, where A(x)^(2*n) (mod 3) reduces all coefficients modulo 3 to {0,1,2}.

Original entry on oeis.org

1, 1, 3, 3, 1, 6, 9, 3, 3, 9, 3, 6, 3, 1, 15, 18, 6, 6, 27, 9, 12, 9, 3, 9, 9, 3, 3, 27, 9, 18, 9, 3, 18, 18, 6, 6, 9, 3, 6, 3, 1, 42, 45, 15, 15, 54, 18, 24, 18, 6, 18, 18, 6, 6, 81, 27, 36, 27, 9, 36, 36, 12, 12, 27, 9, 12, 9, 3, 27, 27, 9, 9, 27, 9, 12, 9, 3, 9, 9, 3, 3, 81, 27, 54

Offset: 0

Paul D. Hanna, Nov 14 2012

nonn

Paul D. Hanna, Table of n, a(n) for n = 0..500

Cf. A080100.

{A=1;for(i=1,122,A=Ser(sum(n=0,#A-1,Vec(1+x^n*A^(2*n) +x*O(x^#A))%3))-#A);Vec(A+O(x^122))}

a(n) == A001764(n) (mod 3), where A001764(n) = binomial(3*n,n)/(2*n+1).
G.f.: A(x) == G(x) (mod 3), where G(x) = 1 +x*G(x)^3 is the g.f. of A001764.
Define trisections by: A(x) = A0(x^3) + x*A1(x^3) + x^2*A2(x^3), then
A0(x) = 3*A(x) - 2,
A1(x) = A(x),
A2(x^3) = (2+A(x) - (3+x)*A(x^3))/x^2.

A309057 a(0) = 1; a(2n) = 3a(n), a(2*n+1) = a(n).

Original entry on oeis.org

1, 1, 3, 1, 9, 3, 3, 1, 27, 9, 9, 3, 9, 3, 3, 1, 81, 27, 27, 9, 27, 9, 9, 3, 27, 9, 9, 3, 9, 3, 3, 1, 243, 81, 81, 27, 81, 27, 27, 9, 81, 27, 27, 9, 27, 9, 9, 3, 81, 27, 27, 9, 27, 9, 9, 3, 27, 9, 9, 3, 9, 3, 3, 1, 729, 243, 243, 81, 243, 81, 81, 27, 243, 81, 81, 27, 81, 27, 27, 9, 243

Offset: 0

Ilya Gutkovskiy, Jul 10 2019

nonn

Cf. A000225 (positions of 1's), A000244, A023416, A048883, A080100, A080791, A309074.

a[0] = 1; a[n_] := If[EvenQ[n], 3 a[n/2], a[(n - 1)/2]]; Table[a[n], {n, 0, 80}]
nmax = 80; A[] = 1; Do[A[x] = (3 + x) A[x^2] - 2 + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]
Join[{1}, Table[3^Count[IntegerDigits[n, 2], 0], {n, 1, 80}]]

G.f. A(x) satisfies: A(x) = (3 + x) * A(x^2) - 2.

a(0) = 1; for n > 0, a(n) = 3^(number of 0's in binary representation of n).

cp's OEIS Frontend

A351886 a(n) is the number of k < n such that a(k) AND n = 0 (where AND denotes the bitwise AND operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

A372331 The number of infinitary divisors of the smallest number k such that k*n is a number whose number of divisors is a power of 2 (A036537).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A115378 a(n) = number of positive integers k < n such that n XOR k = (n+k).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A166556 Triangle read by rows, A000012 * A047999.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Python

Formula

A268514 a(0)=0; thereafter a(2n+1)=3*a(n)+1, a(2n)=2*a(n)+a(n-1)+1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A298372 a(n), in decimal base, is the number of numbers k >= 0 with no more digits than n such that k + n can be computed without carry.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A335587 a(n) is the sum of the numbers k such that 0 <= k <= n and n AND k = 0 (where AND denotes the bitwise AND operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A353292 a(n) is the number of positive integers k <= n that have at least one common 1-bit with n.

A268514 a(0)=0; thereafter a(2n+1)=3a(n)+1, a(2n)=2a(n)+a(n-1)+1.

A219218 G.f. satisfies: A(x) = Sum_{n>=0} [A(x)^(2n) (mod 3)]x^n, where A(x)^(2*n) (mod 3) reduces all coefficients modulo 3 to {0,1,2}.

A309057 a(0) = 1; a(2n) = 3a(n), a(2*n+1) = a(n).