==> 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.