login
Number of nonpowers of 2 dividing n.
6

%I #71 Jan 18 2024 01:40:06

%S 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,

%T 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,

%U 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

%N Number of nonpowers of 2 dividing n.

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

%C 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.

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

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

%C From _Bernard Schott_, Sep 12 2019: (Start)

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

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

%H Alois P. Heinz, <a href="/A326987/b326987.txt">Table of n, a(n) for n = 1..20000</a>

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

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

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

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

%e 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.

%p a:= n-> numtheory[tau](n)-padic[ordp](2*n, 2):

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Aug 24 2019

%t a[n_] := DivisorSigma[0, n] - IntegerExponent[n, 2] - 1; Array[a, 100] (* _Amiram Eldar_, Aug 31 2019 *)

%o (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

%o (PARI) ispp2(n) = (n==1) || (isprimepower(n, &p) && (p==2));

%o a(n) = sumdiv(n, d, ispp2(d) == 0); \\ _Michel Marcus_, Aug 26 2019

%o (Python)

%o from sympy import divisor_count

%o def A326987(n): return divisor_count(n)-(n&-n).bit_length() # _Chai Wah Wu_, Jul 13 2022

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

%K nonn,easy

%O 1,6

%A _Omar E. Pol_, Aug 18 2019