Zio (india) problem i don't know how to solve such problems

[captainvyom_akash]

There is a unique sequence of positive numbers that starts with the number 1 at the
first position and has the following properties.
• Each value in the sequence is greater than or equal to every value that appears
earlier in the sequence.
• If the value at position k in the sequence is m, then the number k appears exactly m times in the sequence.
The first few numbers in this sequence are
Position : 1 2 3 4 5 6 7 8 9 10 11 12 · · · Sequence value : 1 2 2 3 3 4 4 4 5 5 5 6 · · ·
Notice, for instance, that the value at position 4 in the sequence is 3, so 4 itself appears 3 times in the sequence.

What is the value that appears at each of the following positions in this sequence?
(a) 411 (b) 1000 (c) 1245




-------------Akash

 

[daveb]

Well, I can certainly find the answer using an excel spreadsheet, but as for an algorithm...? Still working on it.

 

[Jimmy Snyder]

I altered the wording of the definition without changing its meaning:

$a_k$ is a nondecreasing sequence of integers such that $a_1 = 1$ and has the following property. If the value at position k in the sequence is m, then the number k appears exactly m times in the sequence.

What are the following values?

(a) $a_{411}$
(b) $a_{1000}$
(c) $a_{1245}$

I was unable to come up with a closed form for the solution. The three values required are:


(a) $a_{411}$ = 50[/color]
(b) $a_{1000}$ = 86[/color]
(c) $a_{1245}$ = 98[/color]

I found these by brute force.

 

[davee123]

I altered the wording of the definition without changing its meaning:

$a_k$ is a nondecreasing sequence of integers such that $a_1 = 1$ and has the following property. If the value at position k in the sequence is m, then the number k appears exactly m times in the sequence.

One stipulation: $a_2 = 2$. Otherwise, $a_2$ could be anything.

As for solving it, I couldn't get anything either for the Nth case, or even really an iterative case. Interestingly, I think the problem may be intended to inspire a slight trick on a brute force technique, thanks to the choosing of the number 1245.

If you draw out the sequence, you can predict what a number at a later position will be. Suppose you have f(n) such that f(n) = f(n-1) + $a_n$. We draw a little chart of N, $a_n$, and f(n):

n, $a_n$, f(n)

Hence, you get a little chart, wherein n will be in the series from position f(n-1)+1 to f(n).

1, 1, 1
2, 2, 3
3, 2, 5
4, 3, 8
5, 3, 11
6, 4, 15
7, 4, 19
8, 4, 23
(etc)

Translation:
The number 6 will be between (11+1)th through the 15th position.
The number 7 will be between (15+1)th through the 19th position.
The number 8 will be between (19+1)th through the 23rd position.
Etc.

The interesting thing being that if you write the series itself until you complete the number 20 (at n=98), you discover that 98 is between positions 1227 and 1246 in the series. Since 20 is a pretty round number, it looks like it might have been done this way, seeing as 1245 is one number short of 1246.

DaveE

 

[Jimmy Snyder]

One stipulation: $a_2 = 2$. Otherwise, $a_2$ could be anything.

Not so. If $a_2 = m, m > 2$, then 2 would have to appear m times and so the sequence would not be nondecreasing.

 

[davee123]

Not so. If $a_2 = m, m > 2$, then 2 would have to appear m times and so the sequence would not be nondecreasing.

Oh yeah! (oops) Ok, forget I said that.

DaveE

 

[kant]

1
22 33
444 555
6666 7777
88888 99999...


It seems like a pretty predictable pattern.

 

[davee123]

1
22 33
444 555
6666 7777
88888 99999...

It seems like a pretty predictable pattern.

Not quite-- slight mistake above: there should be four 8's, not 5, which puts them on the previous line of the way you're drawing the pattern. Drawing the pattern the way you're drawing it, you can do something like (base 36 shown):

1
22 33
444 555
6666 7777 8888
99999 AAAAA BBBBB
CCCCCC DDDDDD EEEEEE FFFFFF
GGGGGGG HHHHHHH IIIIIII JJJJJJJ
KKKKKKKK LLLLLLLL MMMMMMMM NNNNNNNN
OOOOOOOOO PPPPPPPPP QQQQQQQQQ RRRRRRRRR SSSSSSSSS
TTTTTTTTTT UUUUUUUUUU VVVVVVVVVV WWWWWWWWWW XXXXXXXXXX

Note that each line contains the number of groups equal to the next number in the sequence. Hence, the 1st line has 1, then 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, etc.

DaveE

 

[kant]

still, the pattern seem simple enough. If only i had the patience...