Extend New Binary Sequence ?

[David Wilson]

If you use the recurrence

    [1] a(n) = a(n-1) + a([n/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).

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.

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.

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).

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.

----- Original Message ----- 
  From: Paul D. Hanna 
  To: seqfan at ext.jussieu.fr 
  Sent: Friday, August 31, 2007 7:59 PM
  Subject: Re: Extend New Binary Sequence ?


  Seqfans, 
        To start with the correct offset (=0), the PARI program 
  should have been: 

  A000123(n) = if(n<1, n==0, A000123(n\2) + A000123(n-1)) 

  a(n) = if(n==0,1, A000123( (2^(n+1) + (-1)^n - 3)/6 ) ) 

  I do not know if there is any faster way of programming this ... 
  Perhaps I will find a matrix approach that will be quick? 

  Thanks for any tips or tries in extending this sequence. 
      Paul 

  On Fri, 31 Aug 2007 19:48:11 -0400 Paul D. Hanna <pauldhanna at juno.com> writes:
    The sequence begins:

    1,1,2,4,14,60,450,4964,95982,3037948,

    but I can get no further before my old PARI gets "deep recursion". 


    This is an equivalent definition using PARI:

    a(n) = if(n==0,1, A000123( (2^(n+2) - (-1)^n - 3)/6 ) ) 

    where 
    A000123(n) = if(n<1, n==0, A000123(n\2) + A000123(n-1)) 



------------------------------------------------------------------------------


  No virus found in this incoming message.
  Checked by AVG Free Edition. 
  Version: 7.5.484 / Virus Database: 269.13.1/982 - Release Date: 8/31/2007 5:21 PM
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20070902/94084c26/attachment-0001.htm>