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

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.

Links

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

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

Example

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.

Crossrefs

Cf. A024493, A024495, A329126.

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

Sequence in context: A289102 A289402 A289458 * A355057 A236111 A230455

Adjacent sequences: A329476 A329477 A329478 * A329480 A329481 A329482

Keyword

nonn

Author

Peter Kagey, Nov 13 2019

Status

approved