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,4

Links

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

Formula

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

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

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

Example

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.

Prog

(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)));

Crossrefs

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

Cf. also A294884, A294904.

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

Sequence in context: A194548 A274009 A069157 * A076526 A351417 A226378

Adjacent sequences: A294891 A294892 A294893 * A294895 A294896 A294897

Keyword

nonn

Author

Antti Karttunen, Nov 10 2017

Status

approved