HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares

[Thomas Ritschel]

I have a solution based on Joe Horn's \Gs (sum of divisors) routine:

Code:


%%HP: T(3)A(R)F(.);
@ \Gs, by Joe Horn
@ Sum of ALL the divisors of X
\<< \-> n
\<< n XQ FACTORS R\->I 1 + OBJ\-> 1. SWAP 2. / IP
START PICK3 ROT 1 + ^ 1 - ROT 1 - / *
NEXT
\>>
\>>

Code:

%%HP: T(3)A(R)F(.);
@ Jacobi, by Thomas Ritschel
@ number of representations
@ Jacobi's four-square theorem
\<< DUP 4 MOD
IF 0 ==
THEN DUP 4 / \Gs 32 * NEG
ELSE 0
END SWAP \Gs 8 * +
\>>

For 720^20 it computed the result 42050501860687733694307540234728644161563553655537254442648 in less than 2 seconds (Edit: actually 0.8 sec).

However, it has a flaw: It doesn't work for the inputs 1 and 4 (\Gs fails if n==1).

Open for improvements...