A294894 Number of divisors d of n such that either d=1 or Stern polynomial B(d,x) is reducible.

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

Offset: 1

Author

Antti Karttunen, Nov 10 2017

Keywords

• nonn

Examples

			For n=25, with divisors [1, 5, 25], both B(5,x) and B(25,x) are irreducible, so only 1 is counted and a(25)=1.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..22001

Crossrefs

Cf. A186891, A283991, A294891, A294892, A294893.

Cf. also A294884, A294904.

Differs from A033273 for the first time at n=25.

Programs

PARI

ps(n) = if(n<2, n, if(n%2, ps(n\2)+ps(n\2+1), 'x*ps(n\2)));
A283991(n) = polisirreducible(ps(n));
A294894(n) = sumdiv(n,d,(0==A283991(d)));

Formula

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

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

a(n) = 1 + A294892(n) - A283991(n).