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

[Valentin Albillo]

(04-18-2018 05:31 AM)Gerald H Wrote:  Samsung S4 Android using PariDroid factors 720^20-3 in under 5 sec & 720^20-18 in under 1 min.

Thanks, Gerald, for the timings and factorization. As I said, impressive !

I did download it to my Samsung tablet (a present, I don't do "smartphones") and verified your timing and factorization (mine are even faster), and also tried to factorize

(720^20-19)*(720^20+19)

which obviously has the factors 720^20-19 and 720^20+19 (both prime) but it didn't succeed and after a long while I had to cancel it.

It did surprise me because this one is an easy case for the much simpler and less powerful Fermat's factorization method (cf. Wikipedia) and as I'm aware that most advanced factorization procedures first of all get rid of all small factors by merely performing a preliminary step of trial division up to some prime limit (say up to 131071), thus I thought that they would next run a short trial of Fermat's method to get rid of comparable large factors and only then would they use their advanced procedures (quadratic sieve, elliptic curves, etc).

Regrettably it seems this implementation for Android doesn't do that or it would have factorized this product instantly.

V.
.