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
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
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Dec 10 2018
STATUS
approved