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,2

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

Links

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

Formula

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

Example

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;
  ...

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

Crossrefs

Cf. A056792, A080825.

Sequence in context: A246700 A375478 A073932 * A334725 A120885 A234575

Adjacent sequences: A082401 A082402 A082403 * A082405 A082406 A082407

Keyword

easy,nonn,tabf

Author

Cino Hilliard, Apr 14 2003

Extensions

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

Status

approved