391 pickover/pickover.17.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
391 pickover/pickover.17.p
Title: Cliff Puzzle 17: Weird Recursive Sequence
From: cliff@watson.ibm.com
If you respond to this puzzle, if possible please send me your name,
address, affiliation, e-mail address, so I can properly credit you if
you provide unique information. PLEASE ALSO directly mail me a copy of
your response in addition to any responding you do in the newsgroup. I
will assume it is OK to describe your answer in any article or
publication I may write in the future, with attribution to you, unless
you state otherwise. Thanks, Cliff Pickover
* * *
Consider the simple yet weird recursive formula
a(n) = a(a(n-1)) + a(n-a(n-1))
The sequences starts with a(1) = 1, and a(2) = 1. The "future" values
at higher values of n depend on past values in intricate recursive ways.
Can you determined the third member of the sequence? At first, this may
seem a little complicated to evaluate, but you can being slowly, by
inserting values for n, as in the following:
a(3) = a(a(2)) + a(3-a(2))
a(3) = a(1) + a(3-1) =
a(3) = 1+1 = 2
Therefore, the 3rd value of the sequence a(3) is 2.
The sequence a(n) seems simple enough: 1, 1, 2, 2, 3, 4, 4, 4, 5, ...
Try computing a few additional numbers. Can you find any interesting
patterns? The prolific mathematician John H Conway presented this
recursive sequence at a recent talk entitled "Some Crazy Sequences." He
noticed that the value a(n)/n approaches 1/2 as the sequence grows and n
becomes larger. Can you find a value, N, above which the sequence the
value of a(n)/n is always within 0.05 of the value 1/2? (In other
words,
.eq vbar a(n)/n -1/2 vbar lt 0.05.
The bars indicate the absolute value.)
A difficult problem? you ask.
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. Manfred Shroeder has
noted that the sequence is "replete with appealing self-similarities
that contain the clue to the problem's solution." Can you find any
self-similarities? As I write this, no-one on the planet has found a
value for the smallest N such that a(n)/n is always within 0.01 of the
value 1/2.
.eq (vbar a(n)/n -1/2 vbar lt 0.01. )
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.
Continue to:
My Books
