A005984 Related to recurrences over rings.

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• more

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

• 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)

Crossrefs

Cf. A093005.

Programs

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

Extensions

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