user
The definition of the sequence is colloquially described as:

* Starting with the list [1,1],
* Take the last number in the list so far: 1, I'll call it x.
* Count forward x places from the beginning of the list to find the first number to add (1)
* Count backward x places from the end of the list to find the second number to add (1)
* Add the two indexed numbers from the list and the result becomes the next number in the list (1+1)
* This would then produce [1,1,2] where 2 is the third element of the sequence.

Note that indexing for the description above starts from alternately the left and right ends of the list and starts from an index of *one*.

A less wordy description of the sequence is:

```
   a(1)=a(2)=1
   a(n)=a(a(n-1))+a(n-a(n-1))

```

The sequence begins:

```
   1, 1, 2, 2, 3, 4, 4, 4, 5, ...

```

Interesting features of the sequence are that:

* a(n)/n   tends to   0.5   as   n   grows towards infinity.
* a(n)/n   where   n   is a power of   2   is   0.5
* For   n>4   the maximal value of   a(n)/n   between successive powers of 2 decreases.

a(n) / n   for   n   in   1..256

The sequence is so named because John Conway offered a prize of $10,000 to the first person who could
find the first position,   p   in the sequence where

```
   │a(n)/n│ < 0.55  for all  n > p

```

It was later found that Hofstadter had also done prior work on the sequence.

The 'prize' was won quite quickly by Dr. Colin L. Mallows who proved the properties of the sequence and allowed him to find the value of   n   (which is much smaller than the 3,173,375,556 quoted in the NYT article).

Task

1. Create a routine to generate members of the Hofstadter-Conway $10,000 sequence.
2. Use it to show the maxima of   a(n)/n   between successive powers of two up to   2\*\*20
3. As a stretch goal:   compute the value of   n   that would have won the prize and confirm it is true for   n   up to 2\*\*20

Also see

* Conways Challenge Sequence, Mallows' own account.
* Mathworld Article.
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2018.09

Note that @a is a lazy array, and the Z variants are "zipwith" operators.

```
my $n = 3;
my @a = (0,1,1, -> $p { @a[$p] + @a[$n++ - $p] } ... *);
@a[2**20]; # pre-calculate sequence

my $last55;
for 1..19 -> $power {
    my @range := 2**$power .. 2**($power+1)-1;
    my @ratios = (@a[@range] Z/ @range) Z=> @range;
    my $max = @ratios.max;
    ($last55 = .value if .key >= .55 for @ratios) if $max.key >= .55;
    say $power.fmt('%2d'), @range.min.fmt("%10d"), '..', @range.max.fmt("%-10d"),
        $max.key, ' at ', $max.value;
}
say "Mallows' number would appear to be ", $last55;

```

Output:

```
 1         2..3         0.666666666666667 at 3
 2         4..7         0.666666666666667 at 6
 3         8..15        0.636363636363636 at 11
 4        16..31        0.608695652173913 at 23
 5        32..63        0.590909090909091 at 44
 6        64..127       0.576086956521739 at 92
 7       128..255       0.567415730337079 at 178
 8       256..511       0.559459459459459 at 370
 9       512..1023      0.554937413073713 at 719
10      1024..2047      0.550100874243443 at 1487
11      2048..4095      0.547462892647566 at 2897
12      4096..8191      0.544144747863964 at 5969
13      8192..16383     0.542442708780362 at 11651
14     16384..32767     0.540071097511587 at 22223
15     32768..65535     0.538784020584256 at 45083
16     65536..131071    0.537043656999866 at 89516
17    131072..262143    0.536020067811561 at 181385
18    262144..524287    0.534645431078112 at 353683
19    524288..1048575   0.533779229963368 at 722589
Mallows' number would appear to be 1489
```