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

[Valentin Albillo]

.
Hi, Thomas,

(04-20-2018 07:35 AM)Thomas Ritschel Wrote:  Of course, since Pari is a fully fledged programming language, one could write his own advanced factoring method.

One nice example is William B. Hart's ONE LINE FACTORING ALGORITHM:

Code:

OLF(x)=;i=1;while(i<x,if(issquare(ceil(sqrt(i*x))^2%x),return(gcd(x,floor(ceil(sqrt(i*x))-sqrt((ceil(sqrt(i*x))^2)%x)))));i++)

\p42   /* set precision to 42 digits */
q=(720^20+19)*(720^20-19)
OLF(q)

This instantly yields 1401683395356260729391818575873415577599999999999999999981, the lower of the two factors (720^20-19).

Thank you very much for both the link (extremely interesting article !) and your Pari one-liner which does what I fully expected factorint would do, i.e.: factorize this particular product instantly.

By the way, you say "set precision to 42 digits" but both factors are 58-digit long and their product is twice as long so, why 42 ?

Thanks again, you made my day, never go to bed without learning something interesting.
V.
.