# Finding the root of a basic sequence

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

Indices are important. There are two important keywords in the title besides "sequence".

Hint 2

a26 through a30 are 27, 78, 29, 84, 31. Still, your task is to find the rule and the values for a21 through a25.

Hint 3-1 (continuation of Hint 1)

One of the two important keywords mentioned in Hint 1 is "root". What is the notation for a function $$f$$ applied twice to $$x$$? How does it relate to the word "root"?

Hint 3-2 (continuation of Hint 2)

AnilGoyal's answer is on the right track. Additionally, a21 = 18, a36 = 378, and a63 = 36.

• I am a first timer here. How should I post answer? directly here or through some other method I mean hidden like your spoiler? Apr 16 at 9:06
• shouldn't a19 be 51 instead of 34? Apr 16 at 9:13
• @AnilGoyal No, a19 is 34. Apr 16 at 9:31
• Can you please recheck it once again. My logic goes exactly upto a17 and it fails at a17? I may surely be wrong but please recheck it once. Apr 18 at 3:26
• @AnilGoyal I checked the values again and they are all correct under my rule. Added a few more terms under "Hint 2". I do think you've got pretty good progress though. Apr 19 at 0:32

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=1\times1$$ $$1$$
$$2$$ $$f(2)=2$$ $$f(2)=2=1\times2$$ $$10$$
$$3$$ $$f(3)=5$$ $$f(5)=6=2\times3$$ $$11$$
$$4$$ $$f(4)=4$$ $$f(4)=4=1\times4$$ $$100$$
$$5$$ $$f(5)=6$$ $$f(6)=10=2\times5$$ $$101$$
$$6$$ $$10$$ $$12=2\times6$$ $$110$$
$$7$$ $$9$$ $$21=3\times7$$ $$111$$
$$8$$ $$8$$ $$8=1\times8$$ $$1000$$
$$9$$ $$21$$ $$18=2\times9$$ $$1001$$

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

$$f(f(x)) = n_x \times x$$ where $$n_x$$ is the number of 1s that appear when $$x$$ is represented in binary.

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

BONUS:

By constructing the table, we have found that $$f(21) = 18$$ (row 9). It is exactly as stated in hint 3-2.

From rearranging the function we can obtain a new relation

$$f(x)=f^{-1}(n_x\times 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,

$$f(23) = f^{-1}(78)$$. Because we know from hint 3-1 that $$f(27)=78$$, we know that $$f^{-1}(78)$$ is $$27$$. Thus, $$f(23)=27.$$

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

$$3,5,6,10,12,20,24,40$$. So we can know that the value of $$f(24)$$ is $$40$$.

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.

• The rule is mostly correct, and the meaning of "root" is also correct. The reasoning for $f(21)$ and the value of $f(24)$ are correct, but $f(23)$ is not, because $n_{23} × 23 = 92 ≠ 78$. "basic" was referring to "base". You just need a small addition to the rule to define a single sequence. Apr 19 at 23:17
• @Bubbler Uh yeah that one was my bad. Thanks for catching the error! Apr 20 at 1:20

It is very clear that -

If $$i$$ is power of 2, it is $$A_i$$ indeed. Thus $$A_2$$ = 2, $$A_4$$ = 4, and so on..

Now,

$$A_1$$ takes first of the remaining values which is $$1$$. The sequence cannot be taken any further and hence stops.

Further,

$$A_3$$ gets next available value $$5$$ (some logic seems I am missing here). This value is used to calculate next $$A$$ with index $$5$$ which will be double of previous index. Thus, $$A_5 = 3*2 = 6$$, $$A_6 = 5*2 = 10$$, $$A(10) = 6*2 = 12$$, $$A(12) = 10*2 = 20$$, $$A(20) = 12*2 = 24$$ which reveals our fourth desired number as $$A(24) = 20*2 = 40$$

Next,

remaining of our index is 7 thus $$A_7$$ gets next available value i.e. $$9$$ here. So $$A_7 = 9$$. Similarly, $$A_9 = 7(previous index) * 3 (again I cannot figured it out why?) = 21$$. thus, $$A(21) = 9*3 = 27$$.

Other sequences

$$A(11) = 13$$, $$A(13) = 33$$, $$A(33) = 39$$.... $$A(14) = 15$$, $$A(15) = 42$$, $$A(42) = 45$$.... $$A(17) = 19$$ why not 18?...

From here I got confused and couldn't get it

• You're on the right track. To help you identify the rules behind the multiplier, I added three more terms (to specifically help you with the fourth spoiler block) under Hint 3-2. Apr 19 at 7:49