|
%I #86 Oct 29 2023 22:00:39
%S 0,0,0,0,1,2,6,10,20,32,64,120,256,512,1056,2080,4160,8192,16384,
%T 32640,65536,131072,262656,524800,1049600,2097152,4194304,8386560,
%U 16777216,33554432,67117056,134225920,268451840,536870912,1073741824,2147450880,4294967296,8589934592,17180000256,34359869440
%N 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.
%C 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.
%C 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.
%H Robert Israel, <a href="/A309846/b309846.txt">Table of n, a(n) for n = 1..1000</a>
%H Robert Israel, <a href="/A309846/a309846.pdf">Proofs of formulas</a>
%F From _Robert Israel_, Oct 29 2023: (Start)
%F a(8 k) = 16^k/8 + 256^k/32 for k >= 1.
%F a(8 k + 1) = 16^k/4 + 256^k/16 for k >= 1.
%F a(8 k + 2) = 256^k/8 for k >= 1.
%F a(8 k + 3) = 256^k/4 for k >= 1.
%F a(8 k + 4) = -16^k/2 + 256^k/2.
%F a(8 k + 5) = 256^k.
%F a(8 k + 6) = 2 * 256^k.
%F a(8 k + 7) = 2 * 16^k + 4 * 256^k.
%F 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)
%e 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
%e x^7 + x^6 + x^5 + x^4,
%e x^7 + x^6 + x^4 + x^3,
%e x^7 + x^6 + x^5 + x^2,
%e x^7 + x^5 + x^4 + x^2,
%e x^7 + x^6 + x^3 + x^2, and
%e x^7 + x^4 + x^3 + x^2.
%p f:= proc(n) local k, r;
%p if n <= 4 then return 0 fi;
%p r:= n mod 8;
%p k:= (n-r)/8;
%p if r = 0 then 16^k/8 + 256^k/32
%p elif r = 1 then 16^k/4 + 256^k/16
%p elif r = 2 then 256^k/8
%p elif r = 3 then 256^k/4
%p elif r = 4 then -16^k/2 + 256^k/2
%p elif r = 5 then 256^k
%p elif r = 6 then 2 * 256^k
%p else 2 * 16^k + 4 * 256^k
%p fi
%p end proc:
%p map(f, [$1..50]); # _Robert Israel_, Oct 29 2023
%Y Cf. A329126, A329479.
%K nonn
%O 1,6
%A _Peter Kagey_, Nov 18 2019
%E More terms from _Robert Israel_, Oct 29 2023
| 