A185000 Trajectory of x+1 under the map (see A185544) defined in the Comments.

11, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111, 1101, 11100, 1110, 111

Offset

1,1

Comments

We work in the ring GF(2)[x]. The map is f->f/x if f(0)=0, otherwise f->((x^2+1)f+1)/x. We represent polynomials by their vector of coefficients, high powers first. See A185544.

References

J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see page 99.

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for sequences related to 3x+1 (or Collatz) problem

Index entries for linear recurrences with constant coefficients, signature (0,0,0,1).

Formula

From Colin Barker, Aug 23 2018: (Start)

G.f.: x*(11 + 111*x + 1101*x^2 + 11100*x^3 + 1099*x^4) / ((1 - x)*(1 + x)*(1 + x^2)).

a(n) = a(n-4) for n>5.

(End)

Example

The trajectory is x^2+x+1, x^3+x^2+1, x^4+x^3+x^2, x^3+x^2+x, x^2+x+1, x^3+x^2+1, x^4+x^3+x^2, x^3+x^2+x, x^2+x+1, x^3+x^2+1, ..., with period 4.

Maple

# Extract coefficient vector polynomial (decreasing powers):
coeflistD:=proc(f) local d, i, t1, t2, t3, t4;
if f=0 then RETURN([0]); else
d:=degree(f);
t1:=subs(x=1/x, f);
t2:=sort(expand(x^d*t1));
t3:=seriestolist(series(t2, x, d+2));
t4:=nops(t3);
if t4<d+1 then for i from t4+1 to d+1 do t3:=[op(t3), 0]; od: fi;
RETURN(t3);
fi;
end;
# Define map f:
f:=a->if subs(x=0, a) = 0 then expand(simplify(a/x)) mod 2;
else t1:=((x^2+1)*a+1)/x;  expand(t1) mod 2; fi;
# Get trajectory (as both polynomials and coefficient vectors):
T:=proc(n, M) global f, coeflistD; local t1, i, s1; t1:=[n];
for i from 1 to M-1 do t1:=[op(t1), f(t1[nops(t1)])]; od: lprint(t1);
s1:=[]; for i from 1 to M do s1:=[op(s1), coeflistD(t1[i])]; od: lprint(s1);
end;
T(x+1, 12);

Mathematica

Join[{11}, LinearRecurrence[{0, 0, 0, 1}, {111, 1101, 11100, 1110}, 50]] (* Jean-François Alcover, Mar 10 2023 *)

Prog

(PARI) Vec(x*(11 + 111*x + 1101*x^2 + 11100*x^3 + 1099*x^4) / ((1 - x)*(1 + x)*(1 + x^2)) + O(x^50)) \\ Colin Barker, Aug 23 2018

Crossrefs

Cf. A185544.

Sequence in context: A284024 A283175 A284274 * A283585 A283703 A284399

Adjacent sequences: A184997 A184998 A184999 * A185001 A185002 A185003

Keyword

nonn

Author

N. J. A. Sloane, Feb 05 2011

Status

approved