Golomb sequence

Probability Level 4

Golomb's sequence is a non-decreasing integer sequence where $a_n$ is the number of times that $n$ occurs in the sequence, starting with $a_1 = 1$ , and with the property that for $n > 1$ each $a_n$ is the unique integer which makes it possible to satisfy the condition. The sequence starts off as

$1,2,2,3,3,4,4,4,5,5,5, 6, 6, 6,6, \ldots$

How many times does 50 appear in this sequence?

Image credit: Wikipedia Vic201401

The answer is 13.

1 solution

Kartik Sharma
Jun 8, 2014

This is a Gollomb's sequence

The answer is hidden inside it only.

How many times does a number occur is only determined by going to that number in this sequence. For example, how many times 2 has to come

$1,\quad \boxed { 2 } ,\quad 2$ And hence 2 times

In the same way the sequence will be

1,2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9 and so on

Therefore, at 50th term, it will be 13, so the answer is $\boxed { 13 }$

P.S. or Extra Knowledge - As n $\rightarrow \infty$ , $a(n) \rightarrow { \varphi }^{ 2-\varphi }{ n }^{ \varphi -1 }$

[This is just for knowledge, I would urge someone to make a question on this]

Hey! The picture is so weird. :D

Anuj Shikarkhane - 6 years, 9 months ago

Kartik, nice question :)

Krishna Ar - 6 years, 12 months ago

Hey, thanks but I would urge you to see my other problems please, in particular, Fun with co-efficients. This is because, I want to make it popular(I expected to) and yes, I want one solver...

Kartik Sharma - 6 years, 12 months ago

I can't undersatnd your solution ... How you generated the sequence? Can you please elaborate the logic behind it? Also, I am proposing one solution, kindly review it. Its given that An is number of times n occurs in sequence, So as per given sequence A1 = 1, A2=2, A3=2, A4=3, A5=3, A6=4 .....

Here I can see that you are changing the frequency on even numbers only and frequency of n and n+1 is same. So, as per given pattern, for every n and n+1 the frequency will be (n+2)/2

so if n=0, frequency=1, n=1, frequency=1 n=2, frequency=2, n=3, frequency=2 n=4, frequency=3, n=5, frequency=3 n=6, frequency=4 and so on

So for n=50, frequency = 26 and n=51 frequency = 26

mohd shahid Khan - 6 years, 11 months ago

It is not clear how that sequence is generated. Can you clarify it in the question?

Calvin Lin Staff - 7 years ago

Sir, I have extended the sequence a little and I hope that should mae it clear. And if not, then let me know how can I?

Kartik Sharma - 7 years ago

It's not immediately obvious what the sequence is, so I'm going to add in the definition of Gollomb's sequence.

Calvin Lin Staff - 7 years ago

@Calvin Lin – I too felt the same. Sequence isn't clear.

Shreevathsa CS - 5 years, 2 months ago

@Shreevathsa Cs – The sequence is now properly defined in the problem statement.

Calvin Lin Staff - 5 years, 2 months ago

Golomb sequence

The answer is 13.

1 solution

0 pending reports