A319303 a(n) is the value of the node of the Collatz tree encoded by the number n (see Comments for precise definition).

1, 2, 4, 8, 16, 32, 5, 64, 10, 128, 20, 21, 3, 256, 40, 42, 6, 512, 80, 84, 12, 85, 13, 168, 24, 1024, 160, 336, 48, 170, 26, 672, 96, 2048, 320, 1344, 192, 340, 52, 2688, 384, 341, 53, 5376, 768, 680, 104, 10752, 1536, 4096, 640, 21504, 3072, 113, 17, 43008

Offset

0,2

Comments

For any n >= 0: to find the node corresponding to n:

- move to the root of the Collatz tree (that is, to the node with value 1),

- set r = n

- while r > 0

decrement r

if the current node is a branching node different from 4

(that is, the current node has a value v such that v > 4 and v+2 is a multiple of 6)

then

if r is even

then

move to the child corresponding to a halving step

else

move to the child corresponding to a tripling step

end

divide r by 2 (and round down)

else

move to the only child (this child corresponds to a halving step)

end

end

- the value of the ending node corresponds to a(n).

With this procedure, we can uniquely encode with a nonnegative number the position of any node rooted to 1 in the Collatz tree.

If the Collatz conjecture is true, then this sequence contains all positive integers.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..1000

Rémy Sigrist, Illustration of first terms

Index entries for sequences related to 3x+1 (or Collatz) problem

Example

For n = 18, we visit the following nodes:
  r   Node  Is branching node?
  --  ----  ------------------
  18     1  No
  17     2  No
  16     4  No
  15     8  No
  14    16  Yes
   6     5  No
   5    10  Yes
   2    20  No
   1    40  Yes
   0    80  No
Hence, a(18) = 80.

Mathematica

a[n_] := Module[{r=n, v=1}, While[r != 0, r--; If[v>4 && Mod[(v+2), 6] == 0, v = If[Mod[r, 2] == 0, 2v, (v-1)/3]; r = Quotient[r, 2], v = 2v]]; v];
Table[a[n], {n, 0, 55}] (* Jean-François Alcover, Dec 18 2018, translated from PARI *)

Prog

(PARI) a(n) = my (r=n, v=1); while (r, r--; if (v>4 && (v+2)%6==0, v=if (r%2==0, 2*v, (v-1)/3); r \= 2, v = 2*v)); v

Crossrefs

Cf. A322521 (inverse).

Sequence in context: A122169 A114183 A036129 * A088976 A016020 A364628

Adjacent sequences: A319300 A319301 A319302 * A319304 A319305 A319306

Keyword

nonn

Author

Rémy Sigrist, Dec 10 2018

Status

approved