A005984 Related to recurrences over rings. (Formerly M1323)

1, 2, 5, 6, 10, 14, 21, 22, 27, 32, 42, 48, 59, 70, 85

Offset

1,2

Comments

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

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=1..15.

T. Kløve, Linear recurring sequences in Boolean rings, Math. Scand., 33 (1973), 5-12.

T. Kløve, Linear recurring sequences in Boolean rings, Math. Scand., 33 (1973), 5-12. (Annotated scanned copy)

Prog

(PARI)
lambda(m) = {return (floor(log(m)/log(2))); }
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); }
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); }
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); }
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); }
\\ Michel Marcus, Mar 03 2013

Crossrefs

Cf. A093005.

Sequence in context: A281379 A348565 A316946 * A172186 A355942 A178761

Adjacent sequences: A005981 A005982 A005983 * A005985 A005986 A005987

Keyword

nonn,more

Author

N. J. A. Sloane

Extensions

a(15) from Sean A. Irvine, Nov 05 2016

Status

approved