Finding the root of a basic sequence

Question

The sequence starts with the following:
a1 = 1, a2 = 2, a3 = 5, a4 = 4, a5 = 6,
a6 = 10, a7 = 9, a8 = 8, a9 = 21, a10 = 12,
a11 = 13, a12 = 20, a13 = 33, a14 = 15, a15 = 42,
a16 = 16, a17 = 19, a18 = 63, a19 = 34, a20 = 24, ...
Identify the rule of this sequence and the next five terms.

The same list of numbers, without indices:
1, 2, 5, 4, 6, 10, 9, 8, 21, 12, 13, 20, 33, 15, 42, 16, 19, 63, 34, 24

Hints are spoilered so that people can choose to solve it without seeing them.
Hint 1

Hint 2

Hint 3-1 (continuation of Hint 1)

Hint 3-2 (continuation of Hint 2)

AnilGoyal · Answer

It is very clear that -

Now,

Further,

Next,

Other sequences

From here I got confused and couldn't get it

Nuclear03020704 · Answer

Before I start, consider function $f$ that satisfies $A_x = f(x)$. That is, to find the $x$-th number in the sequence, we can plug in $x$ to $f$.
So we want to find the values of $f(21), f(22), f(23), f(24), f(25)$.
Inspired from hint 2, instead of mapping x to $f(x)$, what if we try to map the relation of $x$ and $f(f(x))$ instead? We get this following pattern.

$x$
$f(x)$
$f(f(x))$
$x$ in binary

$1$
$f(1)=1$
$f(1)=1=1times1$
$1$

$2$
$f(2)=2$
$f(2)=2=1times2$
$10$

$3$
$f(3)=5$
$f(5)=6=2times3$
$11$

$4$
$f(4)=4$
$f(4)=4=1times4$
$100$

$5$
$f(5)=6$
$f(6)=10=2times5$
$101$

$6$
$10$
$12=2times6$
$110$

$7$
$9$
$21=3times7$
$111$

$8$
$8$
$8=1times8$
$1000$

$9$
$21$
$18=2times9$
$1001$

and so on. Based on the provided sequence, it can be said that

That is possibly why $f(f(5))=10=2times5$ but $f(f(7))=21=3times7$.
BONUS:

From rearranging the function we can obtain a new relation
$f(x)=f^{-1}(n_xtimes x)$.
For the values of $x=21,22,23,24,25$, it can be calculated that $n_{21}=3, n_{22}=3, n_{23}=4,n_{24}=2,n_{25}=3$.
Therefore,

Finding $f(24)$ is fun because if we try to construct $x, f(x), f(f(x)), f(f(f(x))), ...$ starting from $x=3$, we get the sequence

So far I can't use $f(22)=f^{-1}(66)$ and $f(25)=f^{-1}(75)$ to my advantage and I'm stuck..
However, I made the connection that the 'root' in title and hint 1 is perhaps meaning 'half-iterate' or 'functional square root', see this Wikipedia page.

Finding the root of a basic sequence

2 Answers

Add your own answers!

Ask a Question

$x$	$f(x)$	$f(f(x))$	$x$ in binary
$1$	$f(1)=1$	$f(1)=1=1times1$	$1$
$2$	$f(2)=2$	$f(2)=2=1times2$	$10$
$3$	$f(3)=5$	$f(5)=6=2times3$	$11$
$4$	$f(4)=4$	$f(4)=4=1times4$	$100$
$5$	$f(5)=6$	$f(6)=10=2times5$	$101$
$6$	$10$	$12=2times6$	$110$
$7$	$9$	$21=3times7$	$111$
$8$	$8$	$8=1times8$	$1000$
$9$	$21$	$18=2times9$	$1001$