Title: Cliff Puzzle 9: 3-Atoms and Growth From: cliff@watson.ibm.com

-------------------------

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.