<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.6000.16525" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bottomMargin=0 bgColor=#ffffff leftMargin=3 topMargin=0 rightMargin=3>
<DIV><FONT face=Arial size=2>If you use the recurrence</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2> [1] a(n) = a(n-1) +
a([n/2])</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>to compute A000123(n), you must at some point
compute a(n-1), then a(n-2), etc, all the way down to 0. This means that
any algorithm based on this recurrence (including those based on the generating
function of A000123, which is essential equivalent) takes O(n) time to compute
a(n). The only way to avoid this is to use a better formula or recurrence (such
as a duplication formula).</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Unfortunately, in the case of A000123, I don't
think we have such a formula. A000123 is a partition-like sequence, and we know
from Ramanjan's formula for the partition function that an explicit formula is
complex and difficult to obtain, and I don't think this has been done for
A000123, given that the sequence says that even the asymptotics are unknown. Nor
do I believe that A000123 has a more efficient recurrence (e.g, requiring less
than O(n) evaluations of a). I do, of course, brook correction on these
points.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>So we are stuck with making the best of [1], ergo
stuck using O(n) time to compute a(n), which sadly limits how far Paul can
extend his sequence in his lifetime. However, as I shall explain, a
straightforward implementation imposes O(n) space as well, which is much more
crippling, since his available computer memory will exhaust far before the
computer itself.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>If we implement [1] using a straightforward
recursion, we eventually have to put a(0) through a(n-1) on the stack to compute
a(n), this will consume O(n) memory (actually O(log n), since each stored a(k)
takes up at least O(log k) space). Mathematician-clever tricks can be used to
reduce space by a constant factor, but it takes programmer-clever tricks to
smack down that O(n).</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>I will describe a program as soon as I have the
spare time. It will allow you to compute a(0), a(1), a(2), ... in order, using
O(log n) additions to compute each successive a(n). It will be somewhat slower
than storing all the a(k) values, but it will store only O(log n) values of
a(k), so that you will be able to run it for as long as you like (live) without
fear of memory overflow.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT><FONT face=Arial size=2></FONT> </DIV>
<DIV>----- Original Message ----- </DIV>
<BLOCKQUOTE
style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px">
<DIV
style="BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: black"><B>From:</B>
<A title=pauldhanna@juno.com href="mailto:pauldhanna@juno.com">Paul D.
Hanna</A> </DIV>
<DIV style="FONT: 10pt arial"><B>To:</B> <A title=seqfan@ext.jussieu.fr
href="mailto:seqfan@ext.jussieu.fr">seqfan@ext.jussieu.fr</A> </DIV>
<DIV style="FONT: 10pt arial"><B>Sent:</B> Friday, August 31, 2007 7:59
PM</DIV>
<DIV style="FONT: 10pt arial"><B>Subject:</B> Re: Extend New Binary Sequence
?</DIV>
<DIV><BR></DIV>
<DIV>Seqfans, </DIV>
<DIV> To start with the correct offset
(=0), the PARI program </DIV>
<DIV>should have been: </DIV>
<DIV> </DIV>
<DIV>A000123(n) = if(n<1, n==0, A000123(n\2) + A000123(n-1)) </DIV>
<DIV> </DIV>
<DIV>
<DIV>a(n) = if(n==0,1, A000123( (2^(n+1) + (-1)^n - 3)/6 ) ) </DIV>
<DIV> </DIV>
<DIV>I do not know if there is any faster way of programming this ... </DIV>
<DIV>Perhaps I will find a matrix approach that will be quick?
</DIV>
<DIV> </DIV>
<DIV>Thanks for any tips or tries in extending this sequence. </DIV>
<DIV> Paul </DIV></DIV>
<DIV> </DIV>
<DIV>On Fri, 31 Aug 2007 19:48:11 -0400 Paul D. Hanna <<A
href="mailto:pauldhanna@juno.com">pauldhanna@juno.com</A>> writes:</DIV>
<BLOCKQUOTE dir=ltr
style="PADDING-LEFT: 10px; MARGIN-LEFT: 10px; BORDER-LEFT: #000000 2px solid">
<DIV>
<DIV>The sequence begins:</DIV>
<DIV> </DIV>
<DIV>1,1,2,4,14,60,450,4964,95982,3037948,</DIV>
<DIV> </DIV>
<DIV>but I can get no further before my old PARI gets "deep recursion".
</DIV>
<DIV> </DIV></DIV>
<DIV> </DIV>
<DIV>This is an equivalent definition using PARI:</DIV>
<DIV> </DIV>
<DIV>a(n) = if(n==0,1, A000123( (2^(n+2) - (-1)^n - 3)/6 ) ) </DIV>
<DIV> </DIV>
<DIV>where </DIV>
<DIV>A000123(n) = if(n<1, n==0, A000123(n\2) + A000123(n-1)) </DIV>
<DIV> </DIV></BLOCKQUOTE>
<P>
<HR>
<P></P>No virus found in this incoming message.<BR>Checked by AVG Free
Edition. <BR>Version: 7.5.484 / Virus Database: 269.13.1/982 - Release Date:
8/31/2007 5:21 PM<BR></BLOCKQUOTE></BODY></HTML>