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

[Valentin Albillo]

.
Hi, Gerald,

(04-17-2018 05:03 AM)Gerald H Wrote:  On a Samsung S4 Android mobile phone 720^20-3 is completely factorized in seconds [•••]

Impressive, but a Samsung S4 (~700-800 €) 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.
.

[John Keith]

(04-17-2018 05:03 AM)Gerald H Wrote:  On a Samsung S4 Android mobile phone

720^20-3

is completely factorized in seconds using

factorint

function in PariDroid

https://play.google.com/store/apps/detai....paridroid

Cool, I didn't know that existed. Thanks for the link!

[Gerald H]

A quick look at ebay revealed this

https://www.ebay.at/itm/Samsung-Galaxy-S...SwIrpaqWGt

as high priced S4 at € 149.

[Gerald H]

Samsung S4 Android using PariDroid factors

720^20-3

in under 5 sec &

720^20-18

in under 1 min.

[Gerald H]

Finally worked out how to get result to PC.

Code:

? factorint(720^20-18)
%1 = [2,1;3,2;5786921844227990216593,1;13456428449899512921320757672230543,1]

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

[Thomas Ritschel]

(04-19-2018 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

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

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^20-19)*(720^20+19) in reasonable time (canceled after about 15 minutes). The "factorint" routine does only trial factoring, no advanced methods.

[Thomas Ritschel]

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

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

[Gerald H]

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^20-19)*(720^20+19))

fac: factoring 19647163408174555224851228006154190582188393911909356605589226111943416217599999​9999999999999999999999999
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/