|
|
In sci.math and rec.puzzles, I wrote an article
with Subject: ``conundrum for the holidays" on
December 25 2001 which I quote below.
I wrote:
<Quote>
I've posted output from a computer program on my homepage at
http://www.geocities.com/ezcos/ (very bottom).
There are 8 numbers to a line, and it appears that it's the first few
hundred terms of an infinite series. So the ``series" starts:
3 1 5 3 7 1 9 3
3 1 13 3 15 1 17 11
3 1 21 3 7 1 25 3
3 1 29 3 31 1 33 27 ...
I don't know for a fact that there really is a series; the program
computes finite series of varied length, depending on a parameter K.
The empirical evidence is that, as K increases, the first term
eventually stays fixed, and the same holds for the n'th term
(n fixed, K increasing).
I haven't found a general rule yet. Hence my post. The only way
I know to get the ``series" is from a program that
simulates some Turing machine.
<Unquote>
Note: The 5-state Turing machine discussed is
#4 of Table 1 in the paper of Heiner Marxen and
Jürgen Buntrock ``Attacking the Busy Beaver 5",
Bulletin of the EATCS, Number 40, February 1990, pp. 247-251.
Let s(n) denote the n'th term of the "series", with n starting
at 1, so that s(1) = 3, s(2) = 1, s(3) = 5 and so on.
It appears that s(8n-3) = p2(8n) - 1,
where p2(k) is the largest power of two dividing the
positive integer k.
As an example, the 13th element of the "series",
s(8*2 - 3), is equal to p2(8*2) - 1 = 16 - 1 = 15.
A look at the number in the 2nd row and 5th column in the
large table at the bottom of the web page
< www.geocities.com/ezcos/">http://www.geocities.com/ezcos/ >
shows '15'.
David Bernier
|
|