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