cp's OEIS Frontend

A005984 Related to recurrences over rings.

%I A005984 M1323 #46 Oct 17 2022 01:45:51
%S A005984 1,2,5,6,10,14,21,22,27,32,42,48,59,70,85
%N A005984 Related to recurrences over rings.
%C A005984 In his paper, Kløve wants to find, in a Boolean ring, the least integer P(r) such that, for any linear recurring sequence {x(n)} of order r, we have x(n+P(r)) = x(n), for all n >= 0. First, he proves that P(r) = 2^v(r)* lcm_{j=1..r} (2^j - 1), where v(r) = floor(log_2(r)) when 1 <= r < 6 and r <= 2^v(r) < 2*r*floor((r+1)/2) for r >= 1. Then, a(n) is defined to be sigma(1-2^r,1,1), being the exact power of X+1 dividing a recursively defined polynomial g(m,X), that is shown to be an upper bound to v(r). He proves also that a(n) <= A093005(n). - _Michel Marcus_, Mar 02 2013
%D A005984 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005984 T. Kløve, <a href="https://doi.org/10.7146/math.scand.a-11464">Linear recurring sequences in Boolean rings</a>, Math. Scand., 33 (1973), 5-12.
%H A005984 T. Kløve, <a href="/A005984/a005984.pdf">Linear recurring sequences in Boolean rings</a>, Math. Scand., 33 (1973), 5-12. (Annotated scanned copy)
%o A005984 (PARI)
%o A005984 lambda(m) = {return (floor(log(m)/log(2)));}
%o A005984 D(m) = {local(vb, vbl, j); vb = binary(m); vbl = length(vb); vj = []; for (j=1, lambda(m)+1, if (vb[j] == 1, vj = concat(vj, vbl - j + 1););); return (vj);}
%o A005984 Q(m) = {local(i, xp, vb); xp = lambda(m)+1; q = 1; vb = binary(m); for (i=1, length(vb), q += (vb[i]*Mod(1,2))*x^xp; xp--;); return (q);}
%o A005984 G(n, vG) = {local(vn, vs, vp, vec, i, vi); if (vG[n] != 0, return (vG)); vn = binary(n); vs = sum(i=1, length(vn), vn[i]); if (vs == 1, vG[n] = Q(n); return (vG); ); vp = 1; vec = D(n); for (i=1, length(vec), vi = n-2^(vec[i]-1); vG = G(vi, vG); vp = lcm(vp, vG[vi]);); vG[n] = vp*Q(n); return (vG);}
%o A005984 a(r) = {n = 2^r-1; vG = vector(n); vG = G(n, vG); g = vG[n]; phi = Mod(1,2)*(x + 1); dphi = phi; np = 1; while (1, if (type(g/dphi) != "t_POL", break;); dphi *= phi; np++;); return (np-1);}
%o A005984 \\ _Michel Marcus_, Mar 03 2013
%Y A005984 Cf. A093005.
%K A005984 nonn,more
%O A005984 1,2
%A A005984 _N. J. A. Sloane_
%E A005984 a(15) from _Sean A. Irvine_, Nov 05 2016