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

04172018, 02:00 PM
Post: #21




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
.
Hi, Gerald, (04172018 05:03 AM)Gerald H Wrote: On a Samsung S4 Android mobile phone 720^203 is completely factorized in seconds [•••] Impressive, but a Samsung S4 (~700800 €) is hardly a "calculator" as we understand them in this forum and the software used isn't an emulation of one either, so I rest my case. Would you care to post the factorization and the timing ? "In seconds" is a little vague ... just curious ... Thanks for the tip, I'll certainly download it for my Samsung tablet though I'm pretty sure the screen scaling will be way off. Regards. V. . 

04172018, 05:42 PM
Post: #22




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
(04172018 05:03 AM)Gerald H Wrote: On a Samsung S4 Android mobile phone Cool, I didn't know that existed. Thanks for the link! 

04182018, 04:53 AM
Post: #23




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
A quick look at ebay revealed this
https://www.ebay.at/itm/SamsungGalaxyS...SwIrpaqWGt as high priced S4 at € 149. 

04182018, 05:31 AM
Post: #24




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
Samsung S4 Android using PariDroid factors
720^203 in under 5 sec & 720^2018 in under 1 min. 

04182018, 11:05 AM
Post: #25




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
Finally worked out how to get result to PC.
Code: ? factorint(720^2018) 

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

04202018, 06:52 AM
Post: #27




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
(04192018 04:52 PM)Valentin Albillo Wrote: 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 Well, it's not an issue of the Android implementation alone. Even Pari/GP on a PC isn't able to factorize the product (720^2019)*(720^20+19) in reasonable time (canceled after about 15 minutes). The "factorint" routine does only trial factoring, no advanced methods. 

04202018, 07:35 AM
Post: #28




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
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++) This instantly yields 1401683395356260729391818575873415577599999999999999999981, the lower of the two factors (720^2019). 

04202018, 12:24 PM
Post: #29




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
.
Hi, Thomas, (04202018 07:35 AM)Thomas Ritschel Wrote: Of course, since Pari is a fully fledged programming language, one could write his own advanced factoring method. Thank you very much for both the link (extremely interesting article !) and your Pari oneliner 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 58digit 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. . 

04202018, 02:04 PM
Post: #30




RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
While nothing to do with this thread, Pari uses quite sophisticated methods to factorize.
While nothing to do with this thread: =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== cached 78498 primes. pmax = 999983 >> factor((720^2019)*(720^20+19)) fac: factoring 196471634081745552248512280061541905821883939119093566055892261119434162175999999999999999999999999999999 9999999639 fac: using pretesting plan: normal fac: no tune info: using qs/gnfs crossover of 95 digits div: primes less than 10000 fmt: 1000000 iterations Total factoring time = 0.1200 seconds ***factors found*** P58 = 1401683395356260729391818575873415577600000000000000000019 P58 = 1401683395356260729391818575873415577599999999999999999981 ans = 1 >> https://sourceforge.net/projects/yafu/ 

« Next Oldest  Next Newest »

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