OFFSET
1,2
COMMENTS
Also known as the Collatz Problem, Syracuse Algorithm or Hailstone Problem. Let syr(m,n) be the image of n at the m-th step. for m=3, k>=0 we get: syr(3,8k)=k, syr(3,8k+1)=6k+1, syr(3,8k+2)=6k+2, syr(3,8k+3)=36k+16, syr(3,8k+4)=6k+4, syr(3,8k+5)=6k+4, syr(3,8k+6)=6k+5, syr(3,8k+7)=36k+34.
REFERENCES
David Wells, Penguin Dictionary of Curious and Interesting Numbers.
LINKS
G. C. Greubel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Collatz Problem
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,-1).
FORMULA
G.f.: x*(1 + 2*x + 16*x^2 + 4*x^3 + 4*x^4 + 5*x^5 + 34*x^6 + x^7 + 5*x^8 + 4*x^9 + 20*x^10 + 2*x^11 + 2*x^12 + x^13 + 2*x^14)/(1 - x^8)^2.
a(n) = (1/64)*(103*n + 60 + i^n*(36*i - n*(5-60*i)) - i^(2n)*(65*n+28) - i^(3n)(36*i+n*(5+60*i)) - i^(n/2)*(8+5n)*(1 + i^n + i^(2n) + i^(3n))). - Federico Provvedi, Nov 23 2021
EXAMPLE
1->4->2->1; 2->1->4->2; 3->10->5->16; ...
MATHEMATICA
Rest[CoefficientList[Series[(x +2x^2 +16x^3 +4x^4 +4x^5 +5x^6 +34x^7 + x^8 +5x^9 +4x^10 +20x^11 +2x^12 +2x^13 +x^14 +2x^15)/(1-x^8)^2, {x, 0, 80}], x]] (* G. C. Greubel, Oct 16 2018 *)
PROG
(PARI) x='x+O('x^80); Vec(x*(1 +2*x +16*x^2 +4*x^3 +4*x^4 +5*x^5 +34*x^6 +x^7 +5*x^8 +4*x^9 +20*x^10 +2*x^11 +2*x^12 +x^13 +2*x^14)/(1-x^8)^2) \\ G. C. Greubel, Oct 16 2018
(Magma) m:=80; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!(x*(1 +2*x +16*x^2 +4*x^3 +4*x^4 +5*x^5 +34*x^6 +x^7 +5*x^8 +4*x^9 +20*x^10 +2*x^11 +2*x^12 +x^13 +2*x^14)/(1-x^8)^2)); // G. C. Greubel, Oct 16 2018
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Bruce Corrigan (scentman(AT)myfamily.com), Oct 18 2002
STATUS
approved