==> pickover/pickover.17.s <==
-------------------------

In article <1992Nov06.160358.101157@watson.ibm.com> you write:
: Title: Cliff Puzzle 17: Weird Recursive Sequence
: Consider the simple yet weird recursive formula
: a(n) = a(a(n-1)) + a(n-a(n-1))

The first 32 terms, and the ratio a(n)/n for each is as follows...

n   a(n)     a(n)/n
1   1        1.0
2   1        1.0
3   2        .666
4   2        .5
5   3        .6
6   4        .666
7   4        .5714
8   4        .5
9   5        .5555
10  6        .6
11  7        .6363
12  7        .5833
13  8        .6153
14  8        .5714
15  8        .5333
16  8        .5
17  9        .5294
18  10       .5555
19  11       .5789
20  12       .6
21  12       .5714
22  13       .5909
23  14       .6086
24  14       .5833
25  15       .6
26  15       .5769
27  15       .5555
28  16       .5714
29  16       .5517
30  16       .5333
31  16       .5161
32  16       .5
33  17 .... and so and....

off the top, we can see that on the 2^k (k a pos. int) terms, the
ratio goes to .5

between each of these, the ratio goes up and then drops back to .5
(ignoring the variances due to integer arithmatic)

the value of n at the maximum in each jump is halfway between the two
2^k points.  The value of a(n) at those points seems to be
2^(k-1) - f(k), where f(k) is some function that I cannot determine
without more computing power.... *sniff*

Therefore, we must find a value of x such that...
(2^(x-1)-f(x))/2^x - .5 <.05 (or whatever)
or
f(x)/2^x < .05

and then N would be .5*(2^x-2^(x-1))

if I could see the next terms up to 128, I might be able to calculate it...


--
Michael Neylon   aka Masem the Great and Almighty Thermodynamics GOD!
      //         | Senior, Chemical Engineering, Univ. of Toledo
  \\ // Only the |   Summer Intern, NASA Lewis Research Center
\  \X/   AMIGA!  |         mneylon@jupiter.cse.utoledo.edu           /
 --------+ How do YOU spell 'potato'?  How 'bout 'lousy'? +----------
    "Me and Spike are big Malcolm 10 supporters." - J.S.,P.L.C.L
-------------------------

In article <1992Nov06.160358.101157@watson.ibm.com> you write:

>John Conway offered $10,000 to the person to find the s-m-a-l-l-e-s-t
>such N. A month after Conway made the offer, Colin Mallows of AT&T
>solved the $10,000 question:  N = 3,173,375,556.

As I pointed out in my posting, this is incorrect, and differs from
Mallows' correct answer published in his article. But a bit of
investigation shows that the above N is hardly a random guess, either.
Conway's sequence is best understood by analyzing it on "levels",
where the   k'th level is the set of integers between  2^k  and 2^(k+1).
It turns out that Mallows' correct answer, 6083008742, lies on level 32,
and the largest candidate answer on level 31 is  N=3173375556, the
number quoted above.

Where did you see the above value of N given as the answer to Conway's
question?

-tal    kubo@math.harvard.edu

p.s.  As I found out when I edited my posted response to your message,
      you either use lines longer than 80 characters in your postings,
      or else your editor appends extra linefeeds to each line.  Since
      both conditions could be problematic for a lot of people who read
      your messages on rec.puzzles, you might want to correct this
      condition.