==> pickover/pickover.09.s <== ------------------------- Subject: Re: Cliff Puzzle 9: 3-Atoms and Growth (PARTIAL SPOILER) Newsgroups: rec.puzzles References: <1992Oct20.184304.37364@watson.ibm.com> In article <1992Oct20.184304.37364@watson.ibm.com>, Cliff Pickover writes: > Start with 3 digits: 1, 2, and 3. > Each succeding row repeats the previous three rows, in order > as you can see from the following diagram. > 1 > 2 > 3 > 123 > 1. What is the sum of digits in the 100th row? This one's easy. You basically have a Tribonacci sequence with the initial conditions S_1 = 1, S_2 = 2, S_3 = 3 and S_n = S_{n-1} + S_{n-2} + S_{n-3} for n>3. Thus, it's possible to find a closed form of the type c_1*r_1^n + c_2*r_2^n + c_3*r_3^n. Indeed, letting T_i be the standard Tribonnaci sequence which has initial values T_1 = 1, T_2 = 1, T_3 = 1 we can play a little game by noting the T's go 1 1 1 3 5, and so by linearity S_i = ( T_i + T_{i+2} )/2, hence S_100 = ( T_100 + T_102 )/2. ------------------------- Dear Mr. Pickover, I found your "123" problem interesting. Here's the answers that I came up with. (Note: my personal info that you requested that I include is at the end of the document.) > * * * >Start with 3 digits: 1, 2, and 3. >Each succeding row repeats the previous three rows, in order, >as you can see from the following diagram. >1 >2 >3 >123 >23123 >312323123 >12323123312323123 >2312331232312312323123312323123 >1. What is the sum of digits in the 100th row? Define an arithmetic series as follows: (Note: Read a_1 as "a sub 1" and a_(n-1) as "a sub n-1". I have to do this because I can't use subscripts here.) a_1 = 1 a_2 = 2 a_3 = 3 a_n = a_(n-3) + a_(n-2) + a_(n-1); n>=4 The sum of each line is the sum of it's parts, so therefore, the sum of each row is the sum of the previous three rows' sums. a_30 = 45152016 (I wrote a simple basic program to calculate it.) >2. Get rid of all the twos. Here I've replaced each of them with a "." >.31.3 >31.3.31.3 >1.3.31.331.3.31.3 >.31.331.3.31.31.3.31.331.3.31.3 >In the last row of this diagram, there are three different species: 31, >331 and 3. How many different species are there in row 30? First, let me show that no "new" species will develop, other than those seen in the sample few lines above: First, notice that there are four unique species above: "1","3","31","331". Next, notice that the first species on a line goes in cycles of 3. (Remember how we're building successive rows. The first row repeated on a line is the row three back. Hence the repeating pattern.) Also notice that the ends of the rows do not change, this time because the last row represented on the current row is the row directly previous (and hence, it ends the same.) Because we are building successive rows via concatination, then only locations within new rows where "new" species may be found ("new" meaning not seen in any previous rows) is where the ends of two rows meet in the new row. Since we know that the "end" of each row is limited to ".3" and the "beginnings" of each row cycle through "31", "1", ".", the only possible combinations we can make are "331", "31", and "3". Since we alreadly have seen these, it is now obvious that we will create no more new species. Next, let me show what species we WILL see: The species "3" is on the end of every line. Therefore it will be in row 30. The species "31" and the species "331" are both imbedded in a row previous to row 30. Therefore they will be in row 30, because the "middle parts" of each row are duplicated down the list, not modified. The species "1" only shows up every third row. It happens to occur on rows such that (Row #) mod 3 = 1. Because 30 mod 3=0, the species "1" will NOT occur in row 30. Hence, we have the three species "3","31","331" occuring in row 30. >3. When the sequence first hits a three, it now undergoes an enzymatic >cleavage, and the digits on the right of the 3 are swapped with the >digits on the left. >1 >2 >3 >123 >23123 now becomes 12323 >312312323 now becomes 123123233 >Now answer the question posed in question 2. I'm not taking the time to work this one out entirely. It appears that this algorithm forces 1's out in front all of the time, and keeps appending 3's on the end of the row. Hence, you'll see a proliferation of species such as "3331","33331","333331", etc. It also appears that in row 30, you will have all the species from "3" , "31", "331","3331", "33331", etc up to "33333333333333333333333331". Now, I haven't doublechecked my work here... I've been up all night, and am too tired to double check my conjecture here. But, I believe that I am right, or at least on the right track. I hope these answers help you. I have two questions in return: "Are you the 'pickover' responsible for many of the Fractint fractal types?" and "Were my answers above even close?" I apologize if my answers seemed a little rough & non-formal at points. I hope you understand my explanation above. Thanks for the mental workout. I hope that this helps you, once again. Hope to hear from you soon! -- Joseph Zbiciak im14u2c@camelot.bradley.edu Here's that personal data to requested that I include: I am Joseph Zbiciak, an Electrical/Computer Engineering Major at Bradley University, Peoria, IL. My current address is as follows: Room 121, Heitz Hall 912 N Elmwood, Peoria, IL 61606 My e-mail address is im14u2c@camelot.bradley.edu. Other info: Year in school: Freshman, DOB: 08/29/75 Academic standing: good Favorite toy: his computer Favorite hobby: spelunking through the internet looking for tidbits like this question here. If you need any more information, let me know. Note: I did not post this on the nn yet. Feel free to for me, however. Thanks! -- ------------------------- |> 3.When the sequence first hits a three, it now undergoes an enzymatic |> cleavage, and the digits on the right of the 3 are swapped with the |> digits on the left. |> |> 1 |> 2 |> 3 |> 123 |> 23123 now becomes 12323 |> 312312323 now becomes 123123233 >From how I understand the descriptive rule I get: 1 2 3 123 becomes 312 23123 becomes 12332 331223123 becomes 312231233 >From your example it seems that the trailing 3 is not regarded as a 'first' 3 (123 is not changed), nor is it regarded as a digit to be swapped (as in the two other examples). Is this how the rule should be interpreted? And ... Keep up the good work, these are really good puzzles!! -- stein.kulseth@nta.no (Norwegian Telecom Research) 'When murders are committed by mathematics, they can be solved by mathematics. Most of them aren't, and this one wasn't' - Nick Charles (Dashiell Hammett's "The Thin Man") ------------------------- Dear Dr. Pickover, I found your "123" problem interesting. Here's the answers that I came up with. (Note: my personal info that you requested that I include is at the end of the document.) > * * * >Start with 3 digits: 1, 2, and 3. >Each succeding row repeats the previous three rows, in order, >as you can see from the following diagram. >1 >2 >3 >123 >23123 >312323123 >12323123312323123 >2312331232312312323123312323123 >1. What is the sum of digits in the 100th row? Define an arithmetic series as follows: (Note: Read a_1 as "a sub 1" and a_(n-1) as "a sub n-1". I have to do this because I can't use subscripts here.) a_1 = 1 a_2 = 2 a_3 = 3 a_n = a_(n-3) + a_(n-2) + a_(n-1); n>=4 The sum of each line is the sum of it's parts, so therefore, the sum of each row is the sum of the previous three rows' sums. a_30 = 45152016 (I wrote a simple basic program to calculate it.) >2. Get rid of all the twos. Here I've replaced each of them with a "." >.31.3 >31.3.31.3 >1.3.31.331.3.31.3 >.31.331.3.31.31.3.31.331.3.31.3 >In the last row of this diagram, there are three different species: 31, >331 and 3. How many different species are there in row 30? First, let me show that no "new" species will develop, other than those seen in the sample few lines above: First, notice that there are four unique species above: "1","3","31","331". Next, notice that the first species on a line goes in cycles of 3. (Remember how we're building successive rows. The first row repeated on a line is the row three back. Hence the repeating pattern.) Also notice that the ends of the rows do not change, this time because the last row represented on the current row is the row directly previous (and hence, it ends the same.) Because we are building successive rows via concatination, then only locations within new rows where "new" species may be found ("new" meaning not seen in any previous rows) is where the ends of two rows meet in the new row. Since we know that the "end" of each row is limited to ".3" and the "beginnings" of each row cycle through "31", "1", ".", the only possible combinations we can make are "331", "31", and "3". Since we alreadly have seen these, it is now obvious that we will create no more new species. Next, let me show what species we WILL see: The species "3" is on the end of every line. Therefore it will be in row 30. The species "31" and the species "331" are both imbedded in a row previous to row 30. Therefore they will be in row 30, because the "middle parts" of each row are duplicated down the list, not modified. The species "1" only shows up every third row. It happens to occur on rows such that (Row #) mod 3 = 1. Because 30 mod 3=0, the species "1" will NOT occur in row 30. Hence, we have the three species "3","31","331" occuring in row 30. >3. When the sequence first hits a three, it now undergoes an enzymatic >cleavage, and the digits on the right of the 3 are swapped with the >digits on the left. >1 >2 >3 >123 >23123 now becomes 12323 >312312323 now becomes 123123233 >Now answer the question posed in question 2. I'm not taking the time to work this one out entirely. It appears that this algorithm forces 1's out in front all of the time, and keeps appending 3's on the end of the row. Hence, you'll see a proliferation of species such as "3331","33331","333331", etc. It also appears that in row 30, you will have all the species from "3" , "31", "331","3331", "33331", etc up to "33333333333333333333333331". Now, I haven't doublechecked my work here... I've been up all night, and am too tired to double check my conjecture here. But, I believe that I am right, or at least on the right track. Thanks for the mental workout. I anxiously await more such puzzles! Hope to hear from you soon! -- Joseph Zbiciak im14u2c@camelot.bradley.edu Here's that personal data to requested that I include: I am Joseph Zbiciak, an Electrical/Computer Engineering Major at Bradley University, Peoria, IL. My current address is as follows: Room 121, Heitz Hall B 912 N Elmwood, Peoria, IL 61606 My e-mail address is im14u2c@camelot.bradley.edu. Other info: Year in school: Freshman, DOB: 08/29/75 Academic standing: good Favorite toy: his computer Favorite hobby: spelunking through the internet looking for tidbits like this question here.