A082404 Triangle in which n-th row gives trajectory of n under the map x -> x/2 if x is even, x -> x-1 if x is odd, stopping when we reach 1.

1, 2, 1, 3, 2, 1, 4, 2, 1, 5, 4, 2, 1, 6, 3, 2, 1, 7, 6, 3, 2, 1, 8, 4, 2, 1, 9, 8, 4, 2, 1, 10, 5, 4, 2, 1, 11, 10, 5, 4, 2, 1, 12, 6, 3, 2, 1, 13, 12, 6, 3, 2, 1, 14, 7, 6, 3, 2, 1, 15, 14, 7, 6, 3, 2, 1, 16, 8, 4, 2, 1, 17, 16, 8, 4, 2, 1

Offset: 1

Author

Cino Hilliard, Apr 14 2003

Keywords

• easy
• nonn
• tabf

Comments

If you write down 0 when dividing by 2, 1 when subtracting 1, the trajectory gives the binary expansion of n.

The length of the n-th row of the triangle is A056792(n). - Nathaniel Johnston, Apr 21 2011

Examples

			Triangle begins:
  1;
  2, 1;
  3, 2, 1;
  4, 2, 1,
  5, 4, 2, 1;
  6, 3, 2, 1;
  7, 6, 3, 2, 1;
  8, 4, 2, 1;
  9, 8, 4, 2, 1;
  ...
		

Links

• Nathaniel Johnston, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A056792, A080825.

Programs

Maple

A082404 := proc(n,k) option remember: if(k = 1)then return n:elif(A082404(n,k-1) mod 2 = 0)then return A082404(n,k-1)/2: else return A082404(n,k-1)-1: fi: end:
for n from 1 to 20 do k:=1: while A082404(n,k)>=1 do printf("%d, ",A082404(n,k)); k:=k+1: od:printf("\n");od: # Nathaniel Johnston, Apr 21 2011

Formula

T(n, 1) = n, T(n, 2) = A029578(n).

Extensions

More terms and changed offset from Nathaniel Johnston, Apr 21 2011