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

0, 0, 0, 0, 1, 2, 6, 10, 20, 32, 64, 120, 256, 512, 1056, 2080, 4160, 8192, 16384, 32640, 65536, 131072, 262656, 524800, 1049600, 2097152, 4194304, 8386560, 16777216, 33554432, 67117056, 134225920, 268451840, 536870912, 1073741824, 2147450880, 4294967296, 8589934592, 17180000256, 34359869440

Offset: 1

Author

Peter Kagey, Nov 18 2019

Keywords

• nonn

Comments

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

Conjecture: All terms are of the form 2^(n-5), 2^k*(2^(n-k-5) + 1), or 2^k*(2^(n-k-5) - 1) for some value of k.

Examples

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

Links

• Robert Israel, Table of n, a(n) for n = 1..1000
• Robert Israel, Proofs of formulas

Crossrefs

Cf. A329126, A329479.

Programs

Maple

f:= proc(n) local k, r;
     if n <= 4 then return 0 fi;
     r:= n mod 8;
     k:= (n-r)/8;
     if r = 0 then 16^k/8 + 256^k/32
     elif r = 1 then 16^k/4 + 256^k/16
     elif r = 2 then 256^k/8
     elif r = 3 then 256^k/4
     elif r = 4 then -16^k/2 + 256^k/2
     elif r = 5 then 256^k
     elif r = 6 then 2 * 256^k
     else 2 * 16^k + 4 * 256^k
     fi
end proc:
map(f, [$1..50]); # Robert Israel, Oct 29 2023

Formula

From Robert Israel, Oct 29 2023: (Start)

a(8 k) = 16^k/8 + 256^k/32 for k >= 1.

a(8 k + 1) = 16^k/4 + 256^k/16 for k >= 1.

a(8 k + 2) = 256^k/8 for k >= 1.

a(8 k + 3) = 256^k/4 for k >= 1.

a(8 k + 4) = -16^k/2 + 256^k/2.

a(8 k + 5) = 256^k.

a(8 k + 6) = 2 * 256^k.

a(8 k + 7) = 2 * 16^k + 4 * 256^k.

G.f.: x^5 * (1 - 2*x + 2*x^2 - 2*x^3)/((1 - 2*x) * (1 - 2*x^2) * (1 - 2*x + 2*x^2)). (End)

Extensions

More terms from Robert Israel, Oct 29 2023