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: | Line 1: | ||
{{task}}[[Category:Memoization]] |
{{task}}[[Category:Memoization]] |
||
The definition of the sequence is colloquially described as: |
The definition of the sequence is colloquially described as: |
||
* Starting with the list [1,1], |
* Starting with the list [1,1], |
||
* Take the last number in the list so far: 1, I'll call it x. |
* 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 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) |
* 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) |
* 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. |
* 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''. |
<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: | Line 18: | ||
Interesting features of the sequence are that: |
Interesting features of the sequence are that: |
||
* a(n)/n tends to 0.5 as n grows towards infinity. |
* 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 |
* 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. |
* For n>4 the maximal value of a(n)/n between successive powers of 2 decreases. |
||
⚫ | |||
⚫ | |||
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 |
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 |
find the first position, p in the sequence where |
||
│a(n)/n│ < 0.55 for all n > p |
|||
It was later found that [[wp:Douglas Hofstadter|Hofstadter]] had also done prior work on the sequence. |
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 |
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 (which is much smaller than the 3,173,375,556 quoted in the NYT article). |
||
;Task: |
|||
⚫ | |||
⚫ | |||
⚫ | |||
<br>'''The task is to:''' |
|||
⚫ | |||
⚫ | |||
⚫ | |||
<br> |
<br> |
||
;Also see: |
|||
References: |
|||
* [http://www.jstor.org/stable/2324028 Conways Challenge Sequence], Mallows' own account. |
* [http://www.jstor.org/stable/2324028 Conways Challenge Sequence], Mallows' own account. |
||
* [http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html Mathworld Article]. |
* [http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html Mathworld Article]. |
||
<br> |
<br><br> |
||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |