A127886 Steps saved by choice in "3x+1" iteration.

0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 88, 8, 0, 0, 75, 0, 8, 0, 0, 8, 8, 0, 8, 0, 88, 0, 8, 0, 0, 0, 75, 0, 8, 8, 0, 0, 0, 88, 88, 8, 8, 0, 8, 0, 0, 75, 75, 0, 8, 8, 0, 0, 0, 0, 75, 8

Offset: 1

Author

David Applegate and N. J. A. Sloane, Feb 04 2007

Keywords

• nonn

Comments

Normal "3x+1" iteration requires x->x/2 if x is even. a(n) is the number of iterations that can be saved by also allowing x->3x+1 if x is even.

Examples

			a(9) = 8 because for 9 the traditional 3x+1 iteration follows the 19-step path:
9 -> 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
while allowing x->3x+1 for even x gives the 11-step path:
9 -> 28 -> 85 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..1000 (computed from the b-files of A006577 and A127885)

Crossrefs

Cf. A006577, A127885, A127887 (gives the indices of the nonzero entries).

Programs

Mathematica

Table[Length@ NestWhileList[If[OddQ@ #, 3 # + 1, #/2] &, n, # > 1 &] - Length@ NestWhileList[Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, FreeQ[#, 1] &], {n, 126}] (* Michael De Vlieger, Aug 20 2017 *)

Formula

a(n) = A006577(n) - A127885(n).