Extend New Binary Sequence ?

Wed Sep 5 01:48:48 CEST 2007

David Wilson wrote:

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

I don't know if there's a faster recurrence involving only a(k), but
by introducing a related function of 2 variables we can compute a(n)
in O(log(n)^3) operations.  (I'm curious to see the "programmer-clever"
tricks for this.)

For n>=0, let f(n) be the number of partitions of n into powers of 2, so
that a(n) = f(2n) = f(2n+1).  For 0<=k<=e, let g(e,k) be the number of
partitions of 2^e with parts in the set {1,2,4,...,2^k}.

Suppose that  n = 2^e m,  where m is odd.  Consider a typical binary
partition of n:

    n = 2^a(0) + 2^a(1) + ... + 2^a(r)                                  (0)

where  0 <= a(0) <= a(1) <= ... <= a(r).  I claim that one of the partial
sums

    s(i) = 2^a(0) + ... + 2^a(i)                                        (1)

(0 <= i <= r) is equal to 2^e.  If not, then we have

    s(i-1) < 2^e < s(i) = s(i-1) + 2^a(i)                               (2)

for some i.  But then

    n = s(r) = s(i-1) + 2^a(i) + ... + 2^a(r) == s(i-1) (mod 2^a(i))    (3)

If  a(i) > e  then

    s(i-1) == n == 2^e (mod 2^(e+1))                                    (4)

which contradicts  0 <= s(i-1) < 2^e.  So  a(i) <= e  and

    s(i-1) == n == 0 (mod 2^a(i))                                       (5)

Hence  2^e  is a multiple of 2^a(i), but it is strictly between a(i-1) and
a(i), which are two consecutive multiples of  2^a(i).  That's impossible,
so assumption (2) is false.

So every binary partition of n can be split into two parts:

    2^e = 2^a(0) + ... + 2^a(i)                                         (6)

and

    n - 2^e = 2^a(i+1) + ... + 2^a(r)                                   (7)

Given the value of a(i), say a(i)=k, there are  g(e,k)-g(e,k-1)
possibilities for the partition in (6).  (Define g(e,-1)=0 to make
this work for k=0.)  Dividing (7) by 2^k, we see that there are
f((n - 2^e)/2^k) = f(2^(e-k) (m-1))  possibilities for the partition in
(7).  It follows that

    f(n)  =      SUM     (g(e,k) - g(e,k-1)) f(2^(e-k) (m-1))           (8)
             0 <= k <= e

Now we need a recurrence for g(e,k).  An argument similar to the one above
shows that a partition of 2^e, if it has more than one part, can be split
into two partitions of 2^(e-1); this leads to this recurrence:

    g(e,k)  =      SUM     (g(e-1,r) - g(e-1,r-1)) g(e-1-r,k-r)         (9)
               0 <= r <= k

for  0 <= k < e,  and

    g(e,e)  =  1 + g(e,e-1)                                             (10)

Here's a short table of values of g(e,k), computed using (9) and (10):

 \ k 0    1    2       3       4       5       6       7       8
e \-------------------------------------------------------------
0 |  1       
1 |  1    2    
2 |  1    3     4       
3 |  1    5     9     10      
4 |  1    9    25     35      36      
5 |  1   17    81    165     201     202     
6 |  1   33   289    969    1625    1827    1828    
7 |  1   65  1089   6545   17361   25509   27337   27338   
8 |  1  129  4225  47905  222241  497097  664665  692003  692004  

Note that the values along the diagonal are f(1), f(2), f(2^2), f(2^3), ...
So computing f of a power of 2 is easy.  Other values of f can be
obtained using equation (8) above; typically computing f(n) requires
O(log(n)^2) previous values of f, in addition to O(log(n)^2) values of
g, and takes O(log(n)^3) operations.

I missed the beginning of this discussion, so I don't know the
significance of  A000123( (2^(n+1) + (-1)^n - 3)/6 ),  but here are some
values of it:

0   1
1   2
2   4
3   14
4   60
5   450
6   4964
7   95982
8   3037948
9   170005730
10  16522010532
11  2882717916878
12  902450057292988
13  514768747418386946
14  537142988843543963620
15  1033976171696917695108270
16  3688322935382700002945333884
17  24514290054855626308893309022498
18  304801526292655801235227790576374820
19  7118057806591130565341301223201553053838
20  313259388933361321062892077969687559682278460
21  26062000616057795214066097831489188710729238725186
22  4110314988488084452256619909138315265238808174186210404
23  1232011347867422753097623155438444291235913527367600775244398
24  703443704442715976354754937644920300954525944513753257422978632188
25  766728692007699092343031760182847052574421909903729669942757487137772898

Here's Mathematica code for all of this:

e2[n_]:=
(* Maximum exponent e such that 2^e divides n.  (n>=1) *)
If[OddQ[n], 0, 1+e2[n/2]];

f[0]=1;
f[n_]:=f[n]=
(* Number of binary partitions of n.  (n>=0) *)
Module[{e,m},
  e=e2[n];
  m=n/2^e;
  Sum[(g[e,k]-g[e,k-1]) f[2^(e-k) (m-1)], {k,0,e}]
];

g[e_,k_]:=g[e,k]=
(* Number of partitions of 2^e with parts in {1,2,4,...,2^k} (-1 <= k <= e) *)
Module[{},      
  Which[
    k<0,        0,
    k==0,       1,
    k==e,       g[e,e-1]+1,
    True,       Sum[(g[e-1,r]-g[e-1,r-1]) g[e-1-r,k-r], {r,0,k}] ] ];

a[n_]:=
(* Sequence A000123, number of binary partitions of 2n.  (n>=0) *)
f[2n];

h[n_]:=a[(2^(n+2)-(-1)^n-3)/6];

Dean Hickerson
dean at math.ucdavis.edu