Hofstadter-Conway $10,000 sequence: Difference between revisions
Content deleted Content added
mNo edit summary |
m added whitespace to the task's preamble. |
||
Line 1:
{{task}}[[Category:Memoization]]
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.
<br>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''.
Line 18:
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.
[[File:Hofstadter conway 10K.gif|center|a(n) / n for n in 1..256]]
▲[[File:Hofstadter conway 10K.gif|center|a(n) / n for n in 1..256]]<br>
The sequence is so named because [[wp:John Horton Conway|John Conway]] [http://www.nytimes.com/1988/08/30/science/intellectual-duel-brash-challenge-swift-response.html offered a prize] of $10,000 to the first person who could
find the first position, p in the sequence where
It was later found that [[wp:Douglas Hofstadter|Hofstadter]] had also done prior work on the sequence.
The 'prize' was won quite quickly by [http://www.research.avayalabs.com/gcm/usa/en-us/people/all/mallows.htm Dr. Colin L. Mallows] who proved the properties of the sequence and allowed him to find the value of n
;Task:
# Create a routine to generate members of the Hofstadter-Conway $10,000 sequence.▼
# Use it to show the maxima of a(n)/n between successive powers of two up to 2**20▼
# As a stretch goal:
▲# Create a routine to generate members of the Hofstadter-Conway $10,000 sequence.
▲# Use it to show the maxima of a(n)/n between successive powers of two up to 2**20
▲# 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
<br>
;Also see:
* [http://www.jstor.org/stable/2324028 Conways Challenge Sequence], Mallows' own account.
* [http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html Mathworld Article].
<br><br>
=={{header|360 Assembly}}==
| |||