Introduction (may be ignored)

Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the fourth challenge in this series (links to the first, second and third challenge).

In this challenge, we will explore not one permutation of the natural numbers, but an entire world of permutations!

In 2000, Clark Kimberling posed a problem in the 26^th issue of Crux Mathematicorum, a scientific journal of mathematics published by the Canadian Mathematical Society. The problem was:

$text{Sequence }a = begin{cases}
a_1 = 1\
a_n = lfloor frac{a_{n-1}}{2} rfloortext{ if }lfloor frac{a_{n-1}}{2} rfloor notin {0, a_1, ... , a_{n-1}}\
a_n = 3 a_{n-1}text{ otherwise}
end{cases}$

Does every positive integer occur exactly once in this sequence?

In 2004, Mateusz Kwasnicki provided positive proof in the same journal and in 2008, he published a more formal and (compared to the original question) a more general proof. He formulated the sequence with parameters $p$ and $q$:

$begin{cases}
a_1 = 1\
a_n = lfloor frac{a_{n-1}}{q} rfloortext{ if }lfloor frac{a_{n-1}}{q} rfloor notin {0, a_1, ... , a_{n-1}}\
a_n = p a_{n-1}text{ otherwise}
end{cases}$

He proved that for any $p, q>1$ such that $log_p(q)$ is irrational, the sequence is a permutation of the natural numbers. Since there are an infinite number of $p$ and $q$ values for which this is true, this is truly an entire world of permutations of the natural numbers. We will stick with the original $(p, q)=(3, 2)$, and for these paramters, the sequence can be found as A050000 in the OEIS. Its first 20 elements are:

1, 3, 9, 4, 2, 6, 18, 54, 27, 13, 39, 19, 57, 28, 14, 7, 21, 10, 5, 15

Since this is a "pure sequence" challenge, the task is to output $a(n)$ for a given $n$ as input, where $a(n)$ is A050000.

Task

Given an integer input $n$, output $a(n)$ in integer format, where:

$begin{cases}
a(1) = 1\
a(n) = lfloor frac{a(n-1)}{2} rfloortext{ if }lfloor frac{a(n-1)}{2} rfloor notin {0, a_1, ... , a(n-1)}\
a(n) = 3 a(n-1)text{ otherwise}
end{cases}$

Note: 1-based indexing is assumed here; you may use 0-based indexing, so $a(0) = 1; a(1) = 3$, etc. Please mention this in your answer if you choose to use this.

Test cases

Input | Output

---------------

1     |  1

5     |  2

20    |  15

50    |  165

78    |  207

123   |  94

1234  |  3537

3000  |  2245

9999  |  4065

29890 |  149853

Rules

• Input and output are integers (your program should at least support input and output in the range of 1 up to 32767)


• Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.


• Default I/O rules apply.


• 
  Default loopholes are forbidden.


• This is code-golf, so the shortest answers in bytes wins

JavaScript (ES6),  55  51 bytes

Saved 1 byte thanks to @EmbodimentofIgnorance

n=>eval("for(o=[p=2];n--;o[p]=1)p=o[q=p>>1]?3*p:q")

Try it online!

Jelly, 21 bytes

Ø.;0ị×3$:2$:2eɗ?Ɗ$⁸¡Ṫ

Try it online!

A monadic link that takes zero-indexed $n$ as the argument and returns $a(n)$.

Jelly, 15 bytes

µ×3żHḞḢḟȯ1Ṫ;µ¡Ḣ

A full program accepting the integer, n (1-based), from STDIN which prints the result.

Try it online!

How?

µ×3żHḞḢḟȯ1Ṫ;µ¡Ḣ - Main Link: no arguments (implicit left argument = 0)

µ           µ¡  - repeat this monadic chain STDIN times (starting with x=0)

                -                   e.g. x = ...  0      [1,0]            [9,3,1,0]

 ×3             -   multiply by 3                 0      [3,0]            [27,9,3,0]

    H           -   halve                         0      [1.5,0]          [4.5,1.5,0.5,0]

   ż            -   zip together                  [0,0]  [[3,1.5],[0,0]]  [[27,4.5],[9,1.5],[3,0.5],[0,0]]

     Ḟ          -   floor                         [0,0]  [[3,1],[0,0]]    [[27,4],[9,1],[3,0],[0,0]]

      Ḣ         -   head                          0      [3,1]            [27,4]

       ḟ        -   filter discard if in x             [3]              [27,4]

        ȯ1      -   logical OR with 1             1      [3]              [27,4]

          Ṫ     -   tail                          1      3                4

           ;    -   concatenate with x            [1,0]  [3,1,0]          [4,9,3,1,0]

              Ḣ - head                            1      3                4

                - implicit print

Perl 6, 51 bytes

{(1,3,{first *∉@_,@_[*-1]+>1,3*@_[*-1]}...*)[$_]}

Try it online!

Returns the 0-indexed element in the sequence. You can change this to 1-indexed by changing the starting elements to 0,1 instead of 1,3

Explanation:

{                                               }  # Anonymous code block

 (                                     ...*)[$_]   # Index into the infinite sequence

  1,3                                              # That starts with 1,3

     ,{                               }            # And each element is

       first                                       # The first of

                  @_[*-1]+>1                         # The previous element bitshifted one

                            ,3*@_[*-1]               # Triple the previous element

             *∉@_,                                 # That hasn't appeared in the sequence

Wolfram Language (Mathematica), 63 bytes

(L=Last)@Nest[{##,If[FreeQ[#,x=⌊L@#/2⌋],x,3L@#]}&,{0,1},#]&

Try it online!

This is 0-indexed

(In TIO I added -1 in every test case)

C++ (gcc), 189 bytes

#include <vector>

#include <algorithm>

int a(int n){std::vector<int>s={1};for(int i=0;i<n;++i){int p=s[i]/2;s.push_back(p&&std::find(s.begin(),s.end(),p)==s.end()?p:3*s[i]);}return s[n-1];}

Try it online!

Computes the sequence up to n, then returns the desired element. Slow for larger indices.