Tough Puzzle: The Parrot Sequence - crack it!

[The_Big_K]

Puzzle Taken from Mind and Visual Puzzles! -

The parrot sequence

Gaston owns a clever parrot called Paco which can describe out loud numbers read from a piece of paper displayed in front of him. One day

Gaston tried this funny experiment: he wrote the digit 1 on a sheet and showed it to Paco, who answered “one 1”. Gaston wrote down the parrot’s answer “one 1” or ‘11’ on a new sheet and showed it to Paco, who readily answered “two 1’s”. Again, Gaston wrote down his reply “two 1’s” or ‘21’ on another sheet and showed it to Paco, who replied “one 2, one 1” or ‘1211’... Gaston continued this experiment until he obtained a long sequence of numbers 1, 11, 21, 1211, 111221, 312211, etc... in which each next term is obtained by describing the previous term.

Can you say how many sheets of paper Gaston will need until:

a) the string of digits 333 appears, or
b) the digit 4 occurs in the sequence?

Can you also confirm that the last digit of any term of the parrot sequence is always 1?

[The_Big_K]

No Takers? Too tough for the CEans?

[mahul]

1) 333 will never appear. this is because for 333 to appear, we would need 333 in the previous sequence too( we got to have 3 three's for three consecutive three's to appear. let us consider the previous sequence was x333y. this can be like x 3's and 3 3's or 3 3's and 3 y's. either way we need to have 3 3's in the previous sequence). reasoning in this way this can only happen if we start off with 3 three's which we did not(we started with 1). hence 333 can never appear.

2) 4 can never appear either. for that we would need xxxx in the previous sequence( where x is any digit). let us consider that the sequence was yxxxxz. this can be like y x's, x x's, x z's or x x's , x x's. in the first case it would rather be spelt as (x+y) x's and in the latter as 2x x's. thus a four can also never appear. in fact the max no that can appear is 3.


3) yes the last digit will always be 1. in fact the last digit will be the always be the no we started with. this can be proved again by contradiction. let the last two digits be xy(where y != 1 and x is any no). now this is actually x y's. since x !=0 , then the previous sequence would also end with a y. and the same would repeat till the first sequence. thus the last digit is always the digit we started with, in this case 1.

proved.
correct _k??

[vissin]

Hmm... I'd like to have a parrot that can count and that has such good hold on English grammar.

[mdronsubbs]

the digits 333 never appears because the whole digits end with 1's and 2's....for 333 to appear the prev digits shud also be the same ..so its not at all possible

[skamthe81]

Good one.....................big_K.............

give us dome more

[xheavenlyx]

Mahul's explanation is good

Can anyone write a psudo code for this? like give 15 sequences. or 30 sequences etc?

I tore my hair out while trying to write it in Python...good one! give moreee!

[mahul]

I think I got you, but still I would like to confirm. Are you asking us to write a code that generates the parrot sequence?? Maybe take the initial input would be provided by the user?

[xheavenlyx]

Yes that. And hell, it can be difficult for new programmers like me. I havent used C for so long. Presently i am on Python.

Actually, just today I wrote the draft code for the parrot seq.

Next step is to take any input and keep writing till <x> sequences are complete.

Yea, so try to write the code. This can be a competition too. We can have coding competitions In the end we can upload these files on celab.tk for ppl to download and test. Code will be reveled LATER.

[bayazidahmed]

break the number, count (by parsing) and display