Home > Problem Solving/Puzzles > Self-Describing Numbers and Sequence!

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

About these ads
  1. alok kumar rai
    August 17, 2008 at 8:46 am | #1

    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.

  2. dheeru
    August 23, 2008 at 11:50 am | #2

    order n(log n) is achievable for me

  3. dheeru
    August 23, 2008 at 11:52 am | #3

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

  4. Akhil Ravidas
    December 19, 2008 at 8:23 pm | #4

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

    You can do a binary search to find k

  5. Akhil Ravidas
    December 19, 2008 at 8:32 pm | #5

    I read the problem wrong

  6. June 4, 2010 at 3:17 am | #6

    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.

  7. talegari
    November 2, 2010 at 9:10 pm | #7

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

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

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: