|
%I #36 Apr 19 2022 17:46:59
%S 0,2,2,6,10,22,38,82,154,318,614,1250,2462,4962,9842,19766,39378,
%T 78910,157502,315322,630030,1260674,2520098,5041446,10080430,20163322,
%U 40321682,80648326,161286810,322583462,645147158,1290314082,2580588786,5161216950
%N Number of words of length n (n >= 1) over a two-letter alphabet having a minimal period of size n-1.
%H Robert Israel, <a href="/A019310/b019310.txt">Table of n, a(n) for n = 1..3320</a>
%H H. Harborth, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002189852">Endliche 0-1-Folgen mit gleichen Teilblöcken</a>, Journal für Mathematik, 271 (1974) 139-154.
%F a(n) = 2*a(n-1) + (-1)^n * a(ceiling(n/2)) for n >= 3.
%F a(n) = a(n-1) + 2*a(n-2) if n >= 4 even. a(n) = a(n-1) + 2*a(n-2) + 2*a((n-1)/2) if n>=7 == 3 (mod 4). - _Michael Somos_, Jan 23 2014
%e G.f. = 2*x^2 + 2*x^3 + 6*x^4 + 10*x^5 + 22*x^6 + 38*x^7 + 82*x^8 + ...
%e a(4) = 6 because we have: {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 1, 1}, {1, 1, 0, 1}. These are precisely the binary words of length 4 with autocorrelation polynomial equal to 1 + z^3. - _Geoffrey Critzer_, Apr 13 2022
%p f:= proc(n) option remember;
%p 2*procname(n-1)+(-1)^n*procname(ceil(n/2))
%p end proc:
%p f(1):= 0: f(2):= 2:
%p map(f, [$1..100]); # _Robert Israel_, Jul 15 2018
%o (PARI) a(n) = if (n==1, 0, if (n==2, 2, 2*a(n-1) + (-1)^n*a(ceil(n/2)))) \\ _Michel Marcus_, May 25 2013
%Y Cf. A003000, A019311.
%K nonn
%O 1,2
%A _Jeffrey Shallit_
|
