OFFSET
1,6
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.
LINKS
Robert Israel, Table of n, a(n) for n = 1..1000
Robert Israel, Proofs of formulas
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)
EXAMPLE
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.
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
CROSSREFS
KEYWORD
nonn
AUTHOR
Peter Kagey, Nov 18 2019
EXTENSIONS
More terms from Robert Israel, Oct 29 2023
STATUS
approved