A326987 Number of nonpowers of 2 dividing n.

0, 0, 1, 0, 1, 2, 1, 0, 2, 2, 1, 3, 1, 2, 3, 0, 1, 4, 1, 3, 3, 2, 1, 4, 2, 2, 3, 3, 1, 6, 1, 0, 3, 2, 3, 6, 1, 2, 3, 4, 1, 6, 1, 3, 5, 2, 1, 5, 2, 4, 3, 3, 1, 6, 3, 4, 3, 2, 1, 9, 1, 2, 5, 0, 3, 6, 1, 3, 3, 6, 1, 8, 1, 2, 5, 3, 3, 6, 1, 5, 4, 2, 1, 9, 3, 2, 3, 4, 1, 10, 3, 3, 3, 2, 3, 6, 1, 4, 5, 6

Offset: 1

Author

Omar E. Pol, Aug 18 2019

Keywords

• nonn
• easy

Comments

In other words: a(n) is the number of divisors of n that are not powers of 2.

a(n) is also the number of odd divisors > 1 of n, multiplied by the number of divisors of n that are powers of 2.

a(n) = 0 iff n is a power of 2.

a(n) = 1 iff n is an odd prime.

From Bernard Schott, Sep 12 2019: (Start)

a(n) = 2 iff n is an even semiprime >= 6 or n is a square of prime >= 9 (Aug 26 2019).

a(n) = 3 iff n is an odd squarefree semiprime, or n is an odd prime multiplied by 4, or n is a cube of odd prime (End).

Examples

			For n = 18 the divisors of 18 are [1, 2, 3, 6, 9, 18]. There are four divisors of 18 that are not powers of 2, they are [3, 6, 9, 18], so a(18) = 4. On the other hand, there are two odd divisors > 1 of 18, they are [3, 9], and there are two divisors of 18 that are powers of 2, they are [1, 2], then we have that 2*2 = 4, so a(18) = 4.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000

Crossrefs

Cf. A000005, A000079, A001227, A001248, A001511, A001620, A057716, A065091, A069283, A100484, A326988 (sum), A326989.

Programs

Magma

sol:=[];  m:=1;  for n in [1..100] do v:=Set(Divisors(n)) diff {2^k:k in [0..Floor(Log(2,n))]};  sol[m]:=#v; m:=m+1; end for; sol; // Marius A. Burtea, Aug 24 2019

Maple

a:= n-> numtheory[tau](n)-padic[ordp](2*n, 2):
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 24 2019

Mathematica

a[n_] := DivisorSigma[0, n] - IntegerExponent[n, 2] - 1; Array[a, 100] (* Amiram Eldar, Aug 31 2019 *)

PARI

ispp2(n) = (n==1) || (isprimepower(n, &p) && (p==2));
a(n) = sumdiv(n, d, ispp2(d) == 0); \\ Michel Marcus, Aug 26 2019

Python

from sympy import divisor_count
def A326987(n): return divisor_count(n)-(n&-n).bit_length() # Chai Wah Wu, Jul 13 2022

Formula

a(n) = A000005(n) - A001511(n).

a(n) = (A001227(n) - 1)*A001511(n).

a(n) = A069283(n)*A001511(n).

Sum_{k=1..n} a(k) ~ n * (log(n) + 2*gamma - 3), where gamma is Euler's constant (A001620). - Amiram Eldar, Jan 18 2024