 # 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: