Conference rusure::math

    What's the series:
    
    	1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, ...?
    
    John

    RE: .1

    Are the next few numbers in the series as follows?

	..., 7, 7, 8, 9, 10, 11, 11, ...

    Re .2:  no, it's
    
       	1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, ...
    
    John

    This series may be impossible to guess, although it's fairly easy
    to describe the method of its generation.  A longer look at the
    series is:
    
       	1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12,
    	12, 13, 14, 14, 15, 15, 15, 16, 16, 16, 16, 16, 17, 18, 19, ...
    
    and I have provided Peter with the method.
    
    John

     I would appreciate being "provided with the method,"
     too.
     
     Dan
     
     P.S.  The first differences, 0 1 0 1 1 0 0 1 1 1 0 1 ...
     as a binary fraction come out to 0.350859....  Am I on
     the right track? :-)

>Question:  Of what possible use is the following series of numbers:  1, 1, 2,
>2, 3, 4, 4, 4, 5, 6, 7, 7, ...?

>Conway gave a lecture describing this series, pointing out that the nth term in
>the series approached one-half n.  He challenged anyone in the audience to find 
>when the numbers in the series grew sufficiently close to one-half n.  Mallows
    
    What, pray tell, is going on here?  As I (mis-)understand .0, Conway
    sort of goes up to a chalkboard, writes down a dozen numbers, observes
    that the numbers increase rather slowly, then challenges his audience
    to determine the rest of the sequence.
    
    That makes no sense.  Something else must have gone on besides that.
    
      John
    
    p.s., Dan, I had the same idea as you -- at first it looked like
    the binary expansion for 1/e, but didn't grow fast enough.

    I'm afraid that the series is impossible to figure out.  It's:
    
    	a  = 1
         1
    
    	a  = 1
    	 2
    
    	for n > 2, let k = a    and a  = a  + a
    			    n-1      n    k    n-k
    
    John

     Thanks.  By the way, what does it mean to say that "the
     nth term in the series approached one-half n" when n
     is odd and every element in the series is a positive
     integer?  For odd n, it must be the case that
     
               |      n |    1
               | a  - - | >= -
               |  n   2 |    2
     
     That's not "approaching within epsilon" (except for very
     large epsilon! :-)
     
     Are we expected to show something like
                                           
              | a       |
              |  n    1 |
              | --  - - | -> 0
              | n     2 |
     
     instead?
     
     Dan
        

Newsgroups: sci.math
Path: decwrl!ucbvax!agate!cartan.berkeley.edu!chernoff
Subject: sequence problem
Posted: 4 Sep 88 06:35:15 GMT
Organization: Math Dept., UC Berkeley
 
 
This is related to the ``Conway sequence" discussed in the
New York Times science section on Tuesday, August 30.
 
Define a sequence  a_n  as follows:
 
  a_1 = a_2 = a_3 = 1, and, for n >= 4 ,
 
    a_n = a_k + a_{n-k} 
 
where   k = a_{n-1} .
 
The first few terms of the sequence are 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5.
 
 
Show that  (a_n)/n  -->  (3 - sqrt(5))/2   as  n -->  infinity.
 
# Paul R. Chernoff                       chernoff@cartan.berkeley.edu   #
# Department of Mathematics              ucbvax!cartan!chernoff         #
# University of California                                              #
# Berkeley, CA  94720                                                   #

Suppose (a_n)/n --> b as n --> infinity.

Then (roughly, for large n),
    
    a_n = b * n

    a_n = a_k + a_{n-k} 
 
	= a_(a_(n-1)) + a_(n-a_(n-1))

	= a_(b * (n-1)) + a_( n - b * (n-1) )

	= b * b * (n-1) + b * ( n - b * (n-1) )

	= b^2 * (n-1) + b * n - b^2 * (n-1)

	= b * n

Thus, it's reasonable to conclude that a_(n)/n approaches *some* constant
as n -> infinity.

Define e_(n) = a_(n) - b * n; it's an error estimate.

    a_n = b * n + e_(n)

    a_n = a_k + a_{n-k}
 
	= a_(a_(n-1)) + a_(n-a_(n-1))

	= a_(b * (n-1) + e_(n-1)) + a_( n - b * (n-1) - e_(n-1) )

	= b * (b * (n-1) + e_(n-1)) + e_(b * (n-1) + e_(n-1)) +
	  b * (n - b * (n-1) - e_(n-1)) + e_(n - b * (n-1) - e_(n-1))

	= b^2*(n-1) + b*e_(n-1) + e_(b*(n-1)+e_(n-1)) +
	  b*n - b^2*(n-1) - b*e_(n-1) + e_(n-b*(n-1)-e_(n-1))
	
	= b*n + e_(b*(n-1)+e_(n-1)) + e_(n-b*(n-1)-e_(n-1))

So,

    e_(n) = e_(b*(n-1)+e_(n-1)) + e_(n-b*(n-1)-e_(n-1))

	  = e_( a_(n-1) ) + e_( n - a_(n-1) )

We'd like to show that e_(n)/n -> 0 as n -> infinity.  This would show
that a_(n)/n approaches a limit.

>     Are we expected to show something like
>                                           
>              | a       |
>              |  n    1 |
>              | --  - - | -> 0
>              | n     2 |
>     
>     instead?
     
Dan:		Absolutely right.		John

     More from USENET:
     
Newsgroups: sci.math
Path: decwrl!labrea!rutgers!mailrus!cornell!batcomputer!itsgw!imagine!pawl22.pawl.rpi.edu!entropy
Subject: More Conway-sequence questions
Posted: 5 Sep 88 22:08:52 GMT
Organization: 
 
As described in a recent New York Times article, Conway invented this sequence:
 
a_1 = a_2 = 1
 
n>2:  a_n = a_{a_(n-1)} + a_{n-[a_(n-1)]}
 
The sequence begins  1 1 2 2 3 4 4 4 5 6 ...
 
As with the Fibonacci sequence, we get interesting results if we start
differently.  For example:
 
a_1 = a_2 = a_3 = 1
n>3:  a_n = a_{a_(n-1)} + a_{n-[a_(n-1)]}
 
yields               1 1 1 2 2 3 3 3 4 5 5 5 5 6 7 ...
 
Can we say anything interesting about Conway's-sequence-when-started-
with-n-1's?
 
Note that if a_n > n then the definition is no good.  For example, if we start
with 2 2 we get
     2 2 4 (bang)     
 
The previous sequence continued for one element before blowing up.  What
is the longest a Conway sequence can last before blowing up?

     Aha!  This USENET reply has a partial answer to one of
     the previously mentioned "Conway sequences."
     
     Dan
     
     Don't peek unless you really want to:
     
Newsgroups: sci.math
Path: decwrl!labrea!rutgers!njin!princeton!phoenix!mjlarsen
Subject: Re: sequence problem
Posted: 6 Sep 88 15:08:02 GMT
Organization: Princeton University, NJ
 
In article <13879@agate.BERKELEY.EDU> chernoff@cartan.berkeley.edu () writes:
>
>Define a sequence  a_n  as follows:
>
>  a_1 = a_2 = a_3 = 1, and, for n >= 4 ,
>
>    a_n = a_k + a_{n-k} 
>
>where   k = a_{n-1} .
>
>Show that  (a_n)/n  -->  (3 - sqrt(5))/2   as  n -->  infinity.
 
This is a surprisingly subtle question.  The convergence is extremely
slow, and the proof I am about to sketch does not obviously generalize
to different initial sequences.
 
First prove (by induction, everything is induction in this problem) that
a_{n+1} - a_n is always 0 or 1.  Then prove that
 
		a_{F(n+2)} = F(n), for all n > 2,
 
where F(n) denotes the nth Fibonacci number.  This, of course, proves
the desired result for a certain *subsequence* of the (a_n)/n.  Finally,
suppose the full sequence fails to converge.  Setting
phi = (1 + sqrt(5))/2, the sets
 
		S(e) = {n : |(a_n)/n - 1/phi^2| > e}
 
are infinite for e > 0 sufficiently small.  Let f be the supremum of the
set of e for which S(e) is infinite.  Set
 
		X = lim(e -> f, lim inf(n in S(e),{log(n)/log(phi)})),
 
where {x} = x - [x] is the fractional part function.  It is not
difficult to see that any given value of X leads to a contradiction.
Roughly speaking, there is a kind of regression to the mean.  In order
for a_n / n to be, say, unusually small, both a_k / k and a_{n-k} / (n-k)
must be so.  This, of course, is true only if "unusually" means "near the
limit f".  If F(r) < a_k < F(r+1) < a_{n-k} < F(r+2), phi^X is the limit of the
smallest admissible value of a_k / F(r) or a_{n-k} / F(r+1).  But a_k
and a_{n-k} won't achieve the value phi^X at the same time; the very
fact that a_n is unusually small implies that a_k / F(r) is much larger
than a_{n-k} / F(r+1).  (Of course, this has to be checked.)  For 
a_{n-k} / F(r+1) to reach phi^X, we must wait for n-k / F(r+1),
and hence n / F(r+2), to reach some larger value.  Contradiction.
 
Philsophically, this result is a kind of mixing theorem.  The value
of a_n / n is a weighted average of the values a_k / k and 
a_{n-k} / (n-k).  Of course, everything depends on the original values:
a_1 / 1 = 1, a_2 / 2 = 1/2, and a_3 / 3 = 1/3.  Everything will consist
of averages of these three numbers.  The question is whether they mix
smoothly or whether there are regions which never get mixed together.
The argument sketched above shows that eventually enough mixing occurs
that a limit is reached.
 
						-Michael Larsen

     The USENET reply here refers to the reply in .13.
     
Newsgroups: sci.math
Path: decwrl!purdue!bu-cs!bloom-beacon!gatech!rutgers!njin!princeton!phoenix!mjlarsen
Subject: Re: More Conway-sequence questions
Posted: 8 Sep 88 14:55:05 GMT
Organization: Princeton University, NJ
 
In article <1128@imagine.PAWL.RPI.EDU> entropy@pawl22.pawl.rpi.edu (Mark-Jason Dominus) writes:
>As described in a recent New York Times article, Conway invented this sequence:
>
>a_1 = a_2 = 1
>
>n>2:  a_n = a_{a_(n-1)} + a_{n-[a_(n-1)]}
>
>Can we say anything interesting about Conway's-sequence-when-started-
>with-n-1's?
 
Yes, the methods described in my last posting on the Conway problem can
almost certainly be modified to prove the following conjecture:
 
Let a_k denote the kth term of the Conway sequence starting with n 1's.
Let \phi be the unique positive root of the polynomial
 
			x^{n - 1} + x - 1 = 0.
 
Then
 
		\lim_{k\to\infty} a_k / k = \phi^{n - 1}.
 
In particular, n = 2 (resp. 3) gives the limiting value 1/2
(resp. (3 - \sqrt{5})/2) due to Conway (resp. Chernoff).
 
						-Michael Larsen

Newsgroups: sci.math
Path: decwrl!labrea!rutgers!bellcore!faline!thumper!ulysses!andante!alice!clm
Subject: Re: sequence problem
Posted: 8 Sep 88 14:06:02 GMT
Organization: AT&T Bell Laboratories, Murray Hill NJ
 
Here is a variant of Conway's sequence (1,1,2,2,3,4,4,4,5,..., 
generated by a(n)=a(a(n-1))+a(n-a(n-1)) for n>=3) which seems
to be much more difficult to handle.  Start with 1,1 and then 
for n>=3
        b(n)=b(b(n-2))+b(n-b(n-2)).
I have computed b(n) through n=6144 and it is very irregular.
Perhaps b(n)/n -> about .69.  No prize is offered!
 
-- 
 
   Colin Mallows   clm@research.att.com (AT&T Bell Labs, Murray Hill NJ)

923.14> to be much more difficult to handle.  Start with 1,1 and then 
923.14> for n>=3
923.14>         b(n)=b(b(n-2))+b(n-b(n-2)).
923.14> I have computed b(n) through n=6144 and it is very irregular.
923.14> Perhaps b(n)/n -> about .69.  No prize is offered!
---------
928.3>  When 0 < x <= 1/e, 1 > f(x) >= (1/e)^(1/e) = e^(-e^-1) = 0.692200627....
---------
    What are the odds the sequence in .14 converges to the minimum of x^x?
    Anybody want to carry out 923.14 for huge n and see if it exceeds .6922?

      John

>923.14>         b(n)=b(b(n-2))+b(n-b(n-2)).
>923.14> I have computed b(n) through n=6144 and it is very irregular.
>923.14> Perhaps b(n)/n -> about .69.  No prize is offered!
>---------
>928.3>  When 0 < x <= 1/e, 1 > f(x) >= (1/e)^(1/e) = e^(-e^-1) = 0.692200627....
>---------
>    Anybody want to carry out 923.14 for huge n and see if it exceeds .6922?

It does not appear to converge to that value. b(n)/n does flop around a lot;
the *average* over the first 100,000 values of n, though, is ~ .689578.

b(4)/4 = b(8)/8 = .75, the maximum. b(5)/5 = .6, the minimum.

b(n)/n = .700000 for n = 10,20,40,50,60,90,110,130,160,190, and 350 and for
no other values of n<100,000. 

Lynn 

     ln 2 = 0.693... is also "nearby".
     
     Dan

     I ended up with:
     
           n         b(n)
        -------     ------
         999990     687796
         999991     687797
         999992     687798
         999993     687798
         999994     687798
         999995     687799
         999996     687799
         999997     687799
         999998     687799
         999999     687800
        1000000     687801
     
     Dan