Hofstadter-Conway $10,000 sequence: Difference between revisions

← Older editNewer edit →
Content deleted Content added
KenS (talk | contribs)
799 edits
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.
* &nbsp; a(n)/n &nbsp; tends to &nbsp; 0.5 &nbsp; as &nbsp; n &nbsp; grows towards infinity.
* a(n)/n where n is a power of 2 is 0.5
* &nbsp; a(n)/n &nbsp; where &nbsp; n &nbsp; is a power of &nbsp; 2 &nbsp; is &nbsp; 0.5
* For n>4 the maximal value of a(n)/n between successive powers of 2 decreases.
* &nbsp; For &nbsp; n>4 &nbsp; the maximal value of &nbsp; a(n)/n &nbsp; between successive powers of 2 decreases.

⚫
[[File:Hofstadter conway 10K.gif|center|a(n) / n &nbsp; for &nbsp; n &nbsp; in &nbsp; 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
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, &nbsp; p &nbsp; in the sequence where
|a(n)/n| < 0.55 for all n > p.
│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. (Which is much smaller than the 3,173,375,556. quoted in the NYT article)
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 &nbsp; n &nbsp; (which is much smaller than the 3,173,375,556 quoted in the NYT article).


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


<br>'''The task is to:'''
⚫
# 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>
<br>
;Also see:
References:
* [http://www.jstor.org/stable/2324028 Conways Challenge Sequence], Mallows' own account.
* &nbsp; [http://www.jstor.org/stable/2324028 Conways Challenge Sequence], Mallows' own account.
* [http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html Mathworld Article].
* &nbsp; [http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html Mathworld Article].
<br>
<br><br>


=={{header|360 Assembly}}==
=={{header|360 Assembly}}==
Retrieved from "https://rosettacode.org/wiki/Hofstadter-Conway_$10,000_sequence"