Here's a stumper from one of my students. I haven't figured out the answer yet, but she told me the pattern isn't mathematical, so the numbers must have some other meaning here. Figure out the next row of numbers in this pattern:
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
[This message was edited by silenteuphony on 10-02-02 at 12:41 AM.]
Posts: 265 | Location: Denver, Colorado, USA | Registered: 06-04-02
This is a visual and language problem. Each line "says" the order of the numbers of the last.
The first row reads 1. The second SAYS one 1 11 The third SAYS two 1s 21 The fourth SAYS one 2, one 1 1211 The fifth SAYS one 1, one 2, two 1s 111221 The sixth SAYS three 1s, two 2s, one 1 312211
etc.
The next row is 13211311123113112211
Posts: 1363 | Location: Lowell, MA, USA | Registered: 06-03-02
Good job, WK! I see now what she meant by non-mathematical, since numbers are used both quantitatively (as numerical values) and semantically (as repeated symbols). This sequence has some interesting properties. First of all, every row is always at least as long as the preceding one. Secondly, every row always consists entirely of 1's, 2's, and 3's; there will never be any other digits.
Let's call this sequence an, and I'll designate the first row a0. So we have
a0 = 1 a1 = 11 a2 = 21 a3 = 1211 a4 = 111221 etc.
Now I'll define another sequence bn as the length (number of digits) of an for n ³ 1. So we have
b1 = 2 b2 = 2 b3 = 4 b4 = 6 etc.
As I already observed, bn is always non-decreasing; it is always even as well. Here are some open questions about an and bn:
1) In the post before this, WiteoutKing mentioned a similar sequence that loops, or remains constant, after the 14th row. Does an ever do this? Or in mathematical terms, does an have a limit as n → ∞ ? (I strongly suspect the answer is no.)
2) We already know bn is non-decreasing (each term is as large as the previous one). Does bn ever become strictly increasing (each term is larger than the previous one)? In other words, is there some k such that bn+1 > bn when n > k? (I suspect the answer is yes.) If so, what is k?
3) Finally, is there a general formula for bn? (I'm fairly certain there isn't.) If not, can you find a function that approximates it for large n?
There! In the finest tradition of silenteuphony posts, I've managed to take a fairly easy problem, and complicate it beyond all recognition. The reason I answered no for questions 1 and 3 is because an exhibits chaotic behavior reminiscent of fractals or cellular automata. This chaos doesn't lend itself to predictable patterns, spawning a sequence that "has a mind of its own."
One explanation for this chaos arising from a sequence with such a simple recursive algorithm is the fact that the algorithm is self-referential. That is, the sequence refers to itself in a way that goes beyond simple mathematics. Within each row, a number can represent a symbol to be counted, or it can represent an actual numeric value resulting from counting a number in the previous row. So unlike most mathematical sequences, this sequence isn't just based on the previous row; it also describes the previous row.
Thus, we have the sequence "looking back at itself" in increasing levels of complexity, as each row describes the pattern of the previous row, which in turn describes the pattern of the previous row, ad infinitum. Douglas Hofstadter, in his Pulitzer Prize-winning book Gödel, Escher, Bach: An Eternal Golden Braid, observes that self-referential systems often develop lifelike complexity and chaotic, seemingly spontaneous behavior. So perhaps in this innocuous sequence we actually have a mathematical version of a cellular automaton or simulated life (thus the title of this thread).
This message has been edited. Last edited by: silenteuphony,
Posts: 265 | Location: Denver, Colorado, USA | Registered: 06-04-02
Although this isn't a proof, it looks like the sequence steadily increases after the 4th term. So, tentatively, in answer to question 2, k does exist, and it equals 4. The existence of k also implies that the answer to question 1 is no, there is no limit for an , just as I guessed.
Finally, in answer to question 3, there is no general formula for bn , but for large n, the sequence does approach Cλn, where C is a constant, and λ ≈ 1.303577269.
Using the largest given value of bn , b48 = 686646, and solving for C, we get C ≈ 2.0425. Plugging this back into the equation, we get the approximation function
bn ≈ 2.0425 × 1.303577269 n
This function estimates bn with an error of 0.5% at n = 20, 0.06% at n = 30, 0.007% at n = 40, and 0.001% at n = 48. Given higher terms for bn , we could solve more accurately for C and approximate it even better for higher values of n.
This message has been edited. Last edited by: silenteuphony,
Posts: 265 | Location: Denver, Colorado, USA | Registered: 06-04-02
bn can actually be expressed as a linear combination of the previous 71 terms, which corresponds to a characteristic polonomial of order 71. l is the unique positive real root of this polynomial. (God only knows how they found it.) This polynomial is listed in the Mathworld link if you're curious. According to linear recurrence theory,
bn = B1r1n + B2r2n + B3r3n + ¼
where the r's are the roots of the characteristic polynomial (including the complex roots). I'm not sure how the complex roots would affect the function, but any real roots with absolute value less than 1 would approach 0 as n approaches infinity, since you're taking them to the nth power.
This means that if there's only one real root with absolute value greater than 1, which we'll call l (sound familiar?), then the function would approach Cln as n approaches infinity and the other terms approach 0. However, for smaller n, these missing terms would significantly improve this estimation function.
The Mathworld site states that l is the unique positive real root of the polynomial. This suggests that there may be one or more negative real roots missing from the estimation function, with absolute values less than one, so that their value would become insignificant as n approaches infinity, and the estimation function would still be accurate for very large n.
The upshot of all this is that we can probably get a significantly more accurate estimation function (the estimation function already given is increasingly inaccurate for n < 20), especially for the smaller n's used in our example terms, by using the general form
bn » C1ln + C2rn
where C1 and C2 are both constants, and r is a number between 0 and -1. We have more than enough example terms of the sequence to solve for C1, C2, and r. So, this is still an open problem until I or another highly motivated (bored) enthusiast comes up with a better estimation function.
[This message was edited by silenteuphony on 10-03-02 at 12:20 AM.]
Posts: 265 | Location: Denver, Colorado, USA | Registered: 06-04-02
What I meant for the "counting" loop was that each line counts the number of numbers in the last, with the largest number first:
1 COUNTS one 1 -> 11 COUNTS two 1s -> 21 COUNTS one 2, one 1 -> 1211 COUNTS one 2, three 1s -> 1231 COUNTS one 3, one 2, two 1s -> 131221 COUNTS one 3, two 2s, three 1s -> 132231 COUNTS two 3s, two 2s, two 1s -> 232221 COUNTS one 3, four 2s, one 1 -> 134211 COUNTS one 4, one 3, one 2, three 1s -> 14131231 COUNTS one 4, two 3, one 2, four 1s -> 14231241 COUNTS two 4s, one 3, two 2s, three 1s -> 24132231 COUNTS one 4, two 3s, three 2s, two 1s -> 14233221 COUNTS one 4, two 3s, three 2s, two 1s -> 14233221
Posts: 1363 | Location: Lowell, MA, USA | Registered: 06-03-02
I tried to refine the estimation function as I suggested in my previous post, but the sequence is just too complicated. There could be more than one real root between 0 and -1, plus I'm not sure how the complex roots affect the function for small n.
By the way, my original answer to question 3 was wrong. There is a general formula for the sequence, but the links listed above don't mention it, so presumably nobody's found it yet. This isn't too surprising, since they would have to completely solve a 71st degree polynomial. It's amazing enough they managed to find one real root.
We can assume that all the roots besides l, including the complex ones, have absolute value less than 1, which means their nth power approaches 0 as n approaches infinity. Thus, the general formula approaches the estimation function Cln as n approaches infinity, but the estimation function isn't very accurate for small n.
At any rate, even though bn does have a general formula, its parent sequence an is certainly complex enough to seem to have a life of its own, and it never stops growing.
So the similarity to cellular automata still holds. You can even start with different "seeds" (different digits or digit cominations besides "1") and get different sequences with similar behavior. These grow in a similar fashion and their length functions bn have the same characteristic polynomial with the same estimation function Cln (only the constant C changes).
Posts: 265 | Location: Denver, Colorado, USA | Registered: 06-04-02
