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

04192018, 04:52 PM
Post: #26




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
(04182018 05:31 AM)Gerald H Wrote: Samsung S4 Android using PariDroid factors 720^203 in under 5 sec & 720^2018 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^2019)*(720^20+19) which obviously has the factors 720^2019 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. . Find All My HPrelated Materials here: Valentin Albillo's HP Collection 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)