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

[Robert Gerbicz]

2012/9/28 Charles Greathouse <charles.greathouse at case.edu>

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

Added a dp code that computes all values of a(1),a(2),...,a(n) in total
cost of O(n^1.5).