[seqfan] Re: Number of partitions of n into 4 nonzero squares

[Max Alekseyev]

A correct efficient formula:

for n>0,
A025428(n) = ( A063730(n) + 6*A213024(n) + 3*A063725(n/2) +
8*A092573(n) + 6*A010052(n/4) ) / 24

Here, if an argument is non-integer, the corresponding value is 0.

Each of the sequences in the r.h.s. are efficiently computable.
However, they concern representations as sum of squares of positive
integers. They can be further reduced to representations as sum of
squares of integers (that are easier to count analytically) as
follows:

A025428(n) =
(
( A000118(n) - 4*A005875(n) + 6*A004018(n) - 4*A000122(n) + A000007(n) ) / 16
+ 6 * ( A014455(n) - 2*A033715(n) - A004018(n) + A000122(n/2) +
2*A000122(n) - A000007(n) ) / 8
+ 3 * ( A004018(n/2) - 2*A000122(n/2) + A000007(n) ) / 4
+ 8 * ( A033716(n) - A000122(n) - A000122(n/3) + A000007(n) ) / 4
+ 6 * (A000122(n/4) - A000007(n)) / 2
) / 24
=
(
A000118(n) - 4*A005875(n) - 6*A004018(n) - 12*A000122(n) - 15*A000007(n)
+ 12*A014455(n) - 24*A033715(n) - 12*A000122(n/2)
+ 12*A004018(n/2) + 32*A033716(n) - 32*A000122(n/3) + 48*A000122(n/4)
) / 384.

Regards,
Max

On Fri, Sep 28, 2012 at 4:20 PM, Max Alekseyev <maxale at gmail.com> wrote:
> I apologize, I did not realize that the given formula for *ordered*
> representations, not for *unordered* ones counted by A025428.
> Btw, functions  r_k(n) are present in the OEIS:
>
> r_0(n) = A000007(n)
> r_1(n) = A000122(n)
> r_2(n) = A004018(n)
> r_3(n) = A005875(n)
> r_4(n) = A000118(n)
>
> I'll check how to get unordered representations out of them.
>
> Regards,
> Max
>
> On Fri, Sep 28, 2012 at 3:50 PM, Max Alekseyev <maxale at gmail.com> wrote:
>> Correction: in the formula for A025428, we have k=4:
>> A025428(n) = \sum_{t=0}^4, (-1)^t * binomial(4,t) * r_t(n)
>>
>> On Fri, Sep 28, 2012 at 3:48 PM, Max Alekseyev <maxale at gmail.com> wrote:
>>> See formulae in http://mathworld.wolfram.com/SumofSquaresFunction.html
>>> In particular,
>>> r_k(0) = 1 for any k>=0.
>>> and for n>0:
>>> r_0(n) = 0,
>>> r_1(n) = 2*issquare(n),
>>> r_2(n) = formula (18),
>>> r_3(n) = formula (35),
>>> r_4(n) = formula (39).
>>>
>>> Now,
>>> A025428(n) = \sum_{t=0}^4, (-1)^(k-t) * binomial(k,t) * r_t(n)
>>>
>>> I have implementation of this formula in PARI/GP, if anybody is interested.
>>>
>>> Regards,
>>> Max
>>>
>>> On Fri, Sep 28, 2012 at 3:31 PM, Charles Greathouse
>>> <charles.greathouse at case.edu> wrote:
>>>> I was looking at A025428 recently, and noticed that while new programs
>>>> have been added which are more efficient than the original, they still
>>>> take a long time to run* since they don't take advantage of any number
>>>> theory like Jacobi's theorem. Can anyone give an efficient formula
>>>> here? It should be more "tricky" than "hard", removing the
>>>> double-counting of negatives and taking out the 0s.
>>>>
>>>> Actually my motivation was A216374, for which a formula has been
>>>> proposed which is presumably a special case of the yet-unwritten
>>>> formula for A025428.
>>>>
>>>> * n^(1.5 + o(1)) when it should be n^o(1).
>>>>
>>>> Charles Greathouse
>>>> Analyst/Programmer
>>>> Case Western Reserve University
>>>>
>>>> _______________________________________________
>>>>
>>>> Seqfan Mailing list - http://list.seqfan.eu/