A294884 Number of divisors of n that are not irreducible when their binary expansion is interpreted as polynomial over GF(2).

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

Offset: 1

Author

Antti Karttunen, Nov 09 2017

Keywords

• nonn

Comments

One more than the number of terms of A091242 that divide n: +1 is for divisor 1, which is also included in the count.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..21845
• Index entries for sequences related to polynomials in ring GF(2)[X]

Crossrefs

Cf. A000005, A091225, A091242, A294882, A294883.

Cf. also A234741, A234742, A294894.

Programs

PARI

A294884(n) = sumdiv(n,d,!polisirreducible(Mod(1, 2)*Pol(binary(d))));

Formula

a(n) = Sum_{d|n} (1-A091225(d)).

a(n) + A294883(n) = A000005(n).

For n > 1, a(n) = 1 + A294882(n) - A091225(n).