8
$\begingroup$

Will this sequence ever have a 6 in it?

9, 1, 1, 1, 10, 3, 1, 1, 10, 5, 1, 1, 10, 1, 5, 2, 1, 1, 10, 1, 1, 1, 5, 4, 1, 1, 10, 3, 1, 1, 5, 1, 1, 1, 5, 2, 1, 1, 10, 5, 1, 1, 5, 3, 1, 1, 5, 4, 1, ...

Daily hint #1:

The title gives away a lot, but as always, we are looking for a proof, which turns out to be surprisingly elusive. In fact, I just found a hole in my own proof, too. Oops. Well, at least the answer is still the same :-)

Daily hint #2:

@phenomist has already correctly identified the sequence, and the role of the first number in it.

It turns out that if you choose a different starting number, you get a different sequence, and sometimes, a different answer altogether! For example, here's what happens if you start with a 14:

14, 1, 10, 1, 1, 1, 5, 1, 1, 1, 10, 3, 1, 1, 5, 3, 1, 1, 10, 5, 1, 1, 5, 5, 1, 1, 10, 1, 5, 2, 1, 2, 5, 2, 1, 1, 10, 1, 1, 1, 5, 5, 1, 1, 5, 4, 1, 1, 10, 3, 1, 2, 5, 2, 1, 1, 5, 1, 1, 1, 5, 2, 1, 1, 10, 6, ...

Daily hint #3:

I was planning to put my code for generating these sequences on tio.run for today's hint, but alas, I've used a CPAN module that's not available there. In case you have perl5 installed, and have the means to install the missing module (Math::Roman), here's the code on pastebin.

Also, there's another hint embedded in the code itself: it outputs a newline after every occurrence of a "10". That might prove helpful :-)

Final hint: (edited to make it even hintier; the bounty is running out of time)

Here's the start of the sequence with a lot of extra formatting:

 *: 9, 
 A: 1, 1, 1, 10,
 B: 3, 1, 1, 10,
 C: 5, 1, 1, 10,
 D: 1, 5, 2, 1, 1, 10,
 A: 1, 1, 1, 5, 4, 1, 1, 10,
 B: 3, 1, 1, 5, 1, 1, 1, 5, 2, 1, 1, 10,
 C: 5, 1, 1, 5, 3, 1, 1, 5, 4, 1, 1, 10,
 D: 1, 5, 2, 1, 1, 5, 5, 1, 1, 5, 1, 1, 1, 5, 2, 1, 1, 10,
 A: 1, 1, 1, 5, 4, 1, 2, 5, 2, 1, 1, 5, 3, 1, 1, 5, 4, 1, 1, 10,
 B: 3, 1, 1, 5, 1, 1, 1, 5, 3, 1, 1, 5, 4, 1, 1, 5, 5, 1, 1, 5, 1, 1, 1, 5, 2, 1, 1, 10,
 C: 5, 1, 1, 5, 3, 1, 1, 5, 5, 1, 1, 5, 1, 1, 1, 5, 2, 1, 2, 5, 2, 1, 1, 5, 3, 1, 1, 5, 4, 1, 1, 10,
 D: 1, 5, 2, 1, 1, 5, 5, 1, 2, 5, 2, 1, 1, 5, 3, 1, 1, 5, 5, 1, 1, 5, 4, 1, 1, 5, 5, 1, 1, 5, 1, 1, 1, 5, 2, 1, 1, 10,
 A: 1, 1, 1, 5, 4, 1, 2, 5, 3, 1, 1, 5, 4, 1, 1, 5, 5, 1, 2, 5, 2, 1, 1, 5, 1, 1, 1, 5, 2, 1, 2, 5, 2, 1, 1, 5, 3, 1, 1, 5, 4, 1, 1, 10,
 B: 3, 1, 1, 5, 1, 1, 1, 5, 3, 1, 1, 5, 5, 1, 1, 5, 1, 1, 1, 5, 2, 1, 2, 5, 3, 1, 1, 5, 4, 1, 1, 5, 3, 1, 1, 5, 5, 1, 1, 5, 4, 1, 1, 5, 5, 1, 1, 5, 1, 1, 1, 5, 2, 1, 1, 10,
 C: 5, 1, 1, 5, 3, 1, 1, 5, 5, 1, 2, 5, 2, 1, 1, 5, 3, 1, 1, 5, 5, 1, 1, 5, 5, 1, 1, 5, 1, 1, 1, 5, 2, 1, 1, 5, 5, 1, 2, 5, 2, 1, 1, 5, 1, 1, 1, 5, 2, 1, 2, 5, 2, 1, 1, 5, 3, 1, 1, 5, 4, 1, 1, 10,
 D: 1, 5, 2, 1, 1, 5, 5, 1, 2, 5, 3, 1, 1, 5, 4, 1, 1, 5, 5, 1, 2, 5, 2, 1, 2, 5, 2, 1, 1, 5, 3, 1, 1, 5, 4, 1, 2, 5, 3, 1, 1, 5, 4, 1, 1, 5, 3, 1, 1, 5, 5, 1, 1, 5, 4, 1, 1, 5, 5, 1, 1, 5, 1, 1, 1, 5, 2, 1, 1, 10
 

$\endgroup$
  • 3
    $\begingroup$ I could only make a guess if I assume the title is correct! :) Guess I'll look further... $\endgroup$ – SteveV Jul 7 at 19:05
10
$\begingroup$

First, we should determine what the sequence is.

The title provides a big clue - IX suggests Roman numerals (indeed, the sequence starts 9 which is IX in Roman numerals). Moreover, the second part - "Say" suggests the look and say sequence.
Indeed, if we reparse everything into Roman numerals we get the following:
IX, I, I, I, X, III, I, I, X, V, I, ...
Ignoring the IX which is the "seed" of the sequence, taking every subsequent pair of numbers gives a run-length enumeration of every symbol: the sequence starts with 1 I, 1 X, 3 I, 1 X, 5 I, etc.
Therefore, this seems like a reasonable definition of the sequence.

Now, does a 6 ever appear in this sequence?

Every other character must be a single-lettered Roman numeral, i.e. 1, 5, 10, (50, 100, 500, and 1000 are probably not going to show up). So 6 cannot be part of those elements. The only way that it can appear is in the quantity section.
Since the largest number of consecutive number of symbols in a single Roman numeral is 3 (III, VIII, etc.)... wait hold on can't IIII show up in clock faces? Ok ok fine let's recheck.

Quick detour

Fortunately 4 shows up in the sequence. Kind of late, but it'll have to do.
The surroundings are X, I, I, I, V, IV(?), I, I, X. Fortunately X can't be spontaneously formed, so this will described by the next set of X: 1 X, 3 I, 1 V, 1 I, 1 V, 2 I, 1 X. Ok good, 4 = IV, confirmed.

Back to the show

The largest number of consecutive symbols within a single Roman numeral is 3. This rules out ever forming another 10 outside of the original: the absolute maximum quantity we can come up with is 7: something like III, I, III, (V/X)...
This shows that we can't have two X's in a "period", let alone in a row, so in order to get to 6 we must have [II, I], [III, V] or [III, I], [II, V].
Can we ever have two V's next to each other? There are two cases: either there are [V, V] or [?, V], [V, ?]. Consider the earliest instance of such. The former implies that there was an earlier run of 5 V's, which implies an earlier [V, V] (and also, two consecutive [?, V], not possible). (This shows that there can't ever be 3 V's.) The latter implies [III, I], [II, V] <= [?, (V/X)], [I, I], [I, V], [V, I]. (If it was [II, V] then there was an earlier V, V.)
This is preceded by (V/X)IVIIIII. This must be [I, X], [I, V], [III, I], [I, V] (avoiding [II, V/X]). This is preceded by XVIIIV which must be [I, X], [V, I], [II, V] or [I, X], [VI, I], [I, V] both which violate the earliest instance provision.
Therefore we may conclude that a 6 does not appear in this sequence.

$\endgroup$
  • $\begingroup$ Nice job in identifying the sequence! As for the proof, I'm with you all the way up to the sentence with '<=' in the third paragraph from the bottom. There my train of thought gets derailed when the subject suddenly jumps from "the first 5, 5" to "the first 6". (Either that, or there is one extra 'I' in the left side of the pattern of "The latter implies".) Could you please clarify that part, since now I can only read the parens after that as "the first 6 must be the granddaughter of the first 5, 5", which doesn't seem to follow from anything. $\endgroup$ – Bass Jul 8 at 14:59
  • $\begingroup$ Even though I cannot fully understand this proof, there's a particular reason I don't think it can be correct: it has to do with the importance of the seed. I'll post the reason as tomorrow's hint, if it's still needed at that time. $\endgroup$ – Bass Jul 8 at 22:17
  • $\begingroup$ @Bass While my proof does rely on the seed a small bit, I personally don't think the proof is invalid (just maybe my proof is less general than you had hoped for) Lack of clarity is a fair objection though, I'll try to make each of my implied steps more explicit. $\endgroup$ – phenomist Jul 9 at 3:20
  • 1
    $\begingroup$ I went ahead and posted today's hint a bit early; the problem is not being less general than needed, it's with being a bit too general: Unless I'm badly mistaken (definitely a possibility here!), your answer also proves the non-existence of the sequence given in the second hint. (In case it's too long to verify, here's a shorter example: 17, 1, 10, 1, 5, 3, 1, 1, 10, 1, 1, 1, 5, 5, 1, 1, 10, 3, 1, 2, 5, 2, 1, 1, 10, 6, ..) $\endgroup$ – Bass Jul 9 at 14:18
  • $\begingroup$ Great counter example, Bass. $\endgroup$ – justhalf Jul 9 at 14:21
3
+100
$\begingroup$

I’m going to start out with

@Phenomist’s claim that “in order to get to 6 we must have [II, I], [III, V] or [III, I], [II, V].”. I think that they are right, given @Bass’ Perl code.

Now, @Bass’ Perl code

seems to convert the seed number to a string containing the Roman numerals first, then identifying runs as Phenomist has mentioned, but also inserting new lines every time an X (10) appears. (Not sure about this code decrypting, I’ve never used Perl!) The importance of the seed is therefore in the first line: 9 -> ‘IX’ -> 1 ‘I’ , 1 ‘X’ -> 1, 1, 1, 10 (\n). A curious thing happens, though, when you use a number bigger than 10: the program has been built to break off at every instance of X, but in this case the X comes early: using @Bass’ 14 example, 14 -> ‘XIV’ -> 1 ‘X’, 1 ‘I’, 1 ‘V’ -> 1, 10 (\n), then on the second line 1, 1, 1, 5 from the seed joins the standard 1, 10 at the end. In fact, for 9 <= n <= 19, each and every line should end with 1, 10 because there’s only ever maximum one X that shows up per line.

So at least

We see how important the seed is now: it generates that first (and up to that second) line. Let’s consider those cases again: in order to get [III, I], [II, V], we’d need to see ...[I, V/X], [I, I], [I, V], [V, I]. In order to get that we’d need [I, X], [I, V], [III, I], [I, X] or something similar. This is possible given the right seed — if a seed starts with X, everything after it will move to the second line along with another iteration of 1, 10. It appears that this is possible but only if you start with a seed that has X at the front of the numbers in order to get that wraparound effect. Since 9 = IX doesn’t have an X at the start, it doesn’t get that wraparound effect, and so you get the cyclical patterning found in A, B, C, D in the final hint above.

Therefore

It’s possible to have 6’s, but only if the seed begins with an X. Since 9 does not, no 6 will appear.

$\endgroup$
  • $\begingroup$ I gave you the bounty since you were the only one to react to this question in any way after I posted the bounty. "It appears" isn't quite the level of proof I was looking for, though :-) $\endgroup$ – Bass Jul 16 at 7:59
  • $\begingroup$ Thanks, @Bass — I spent a while thinking about it yesterday morning. I think it has something to do with the fact that wraparounds lead to breakage of that ABCD pattern you created, and under the ABCD pattern all numbers must be less than or equal to five.....but no formal proof was forthcoming! Will continue to think on it... $\endgroup$ – El-Guest Jul 16 at 11:47
  • $\begingroup$ Excellent work as always, @El-Guest. $\endgroup$ – Cubemaster Jul 16 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.