A329479 Number of degree n polynomials f with all nonzero coefficients equal to 1 such that f(k) is divisible by 3 for all integers k.

0, 0, 0, 0, 1, 2, 6, 15, 30, 66, 121, 242, 462, 903, 1806, 3570, 7225, 14450, 29070, 58311, 116622, 233586, 466489, 932978, 1864590, 3727815, 7455630, 14908530, 29822521, 59645042, 119301006, 238612935, 477225870, 954473586, 1908903481, 3817806962, 7635526542

Offset: 1

Author

Peter Kagey, Nov 13 2019

Keywords

• nonn

Comments

Equivalently, this counts strings of numbers of length n that start with a 1 and which yield a multiple of 3 when read in any base.

Examples

			For n = 7, the a(7) = 6 (0,1)-polynomials of degree seven such that f(0) = f(1) = f(2) = 0 (mod 3) are
x^7 + x^5 + x^3,
x^7 + x^6 + x^5 + x^4 + x^3 + x^2,
x^7 + x^5 + x,
x^7 + x^3 + x,
x^7 + x^6 + x^5 + x^4 + x^2 + x, and
x^7 + x^6 + x^4 + x^3 + x^2 + x.
		

Links

• Peter Kagey, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A024493, A024495, A329126.

A008776(n) gives the number of polynomials of degree n+3 without the coefficient restriction.

Formula

a(2n) = A024495(n-1) * A024493(n).

a(2n+1) = A024495(n) * A024493(n).

Conjectured recurrence: a(n) = 2a(n-1) + 2a(n-2) - 5a(n-3) - 2a(n-4) + 10a(n-5) - 4a(n-6) - 4a(n-7) + 8a(n-8).