## Self-Describing Numbers and Sequence!

One of my friends Usman Ahmad, asked me to find the next row in

1

1 1

2 1

1 2 1 1

1 1 1 2 2 1

…

…

which I solved after a bit of effort, but it was actually fun to reach the solution.

Solution goes here as, the next row is "3 1 2 2 1 1" and the next one is "1 3 1 1 2 2 2 1". Such a series is called Self-Describing sequence. And it is very simple to generate. Start from '1' and then next number simply describes it, mean one '1' = 1 1, now next number in the series will be two '1''s as 2 1. Next number describes it as one '2' and one '1' = 1 2 1 1 and hence next number is one '1', one '2' and two '1's so 1 1 1 2 2 1 and so on. So it's a bit different series and nice one to come across. Such numbers also exist in some base systems which are actually self describing, For example, in base 10, the number 6210001000 is self-descriptive because it has six 0s, two 1s, one 2, one 6, and no 3s, 4s, 5s, 7s, 8s or 9s.

I, Haroon

a1=1

a2=2

a3=2

a4=3

a5=3

a6=4

a7=4

a8=4

a9=5

so every no. is repeated a(n) times.

find a(n) in order log(n) time.

order n(log n) is achievable for me

do anyone know how to get O(log n) algorithm or any algo better than O(n(log n))

T(n) = k if k(k-1)/2 < n <= k(k+1)/2

You can do a binary search to find k

I read the problem wrong

what would be the algorithm for 6 digits. I’ve been sitting by my table for 2 hours and I could not figure it out.

We have closed form, better than a log(n) algo in this situation.

[;a(n)=\lceil \frac{\sqrt{1+8n}-1}{2}\rceil;]