A076536 Image of n at the third step in the 3x+1 Problem: syr(3,n).

1, 2, 16, 4, 4, 5, 34, 1, 7, 8, 52, 10, 10, 11, 70, 2, 13, 14, 88, 16, 16, 17, 106, 3, 19, 20, 124, 22, 22, 23, 142, 4, 25, 26, 160, 28, 28, 29, 178, 5, 31, 32, 196, 34, 34, 35, 214, 6, 37, 38, 232, 40, 40, 41, 250, 7, 43, 44, 268, 46, 46, 47, 286, 8, 49, 50, 304, 52, 52, 53

Offset: 1

Author

Bruce Corrigan (scentman(AT)myfamily.com), Oct 18 2002

Keywords

• easy
• nonn

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.

Examples

			1->4->2->1; 2->1->4->2; 3->10->5->16; ...
		

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 sequences related to 3x+1 (or 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).

Crossrefs

Cf. A006370 (n at step 1), A075884 (n at step 2).

Column k=3 of A347270.

Programs

Magma

m:=80; R:=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

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

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

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