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
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
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Feb 05 2011
STATUS
approved