HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
04-13-2018, 11:35 AM (This post was last modified: 04-13-2018 11:35 AM by Gerald H.)
Post: #1
 Gerald H Senior Member Posts: 1,448 Joined: May 2014
HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
As is well-known, every integer can be represented as sum of max 4 squares

https://en.wikipedia.org/wiki/Lagrange%2...re_theorem

& that the number of such representations can be calculated as

https://en.wikipedia.org/wiki/Jacobi%27s...re_theorem

respecting order & sign.

The task is to write a User RPL programme to calculate the number of representations of any natural number exactly & swiftly.

Winner will be programme with lowest value of time*cuberoot(size).

I have a programme that processes 720^20 in 5.6 sec.
04-13-2018, 01:12 PM (This post was last modified: 04-13-2018 01:12 PM by pier4r.)
Post: #2
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
Gerald thanks for the programming challenge.
What I find interesting is the metric.

(04-13-2018 11:35 AM)Gerald H Wrote:  Winner will be programme with lowest value of time*cuberoot(size).

My perspective is that size is often paramount (likely due to the limited memory of older models). Weighting the speed with the size is also done, but with the size being as important as the speed well.

Applying a sort of a filter to the size, the cube root, so to make two programs that have similar size not too different (well aside from the speed factor) is pretty neat. I'd like to add maintainability as well, but that is hard to define. One should set like a commitee for it.

Wikis are great, Contribute :)
04-14-2018, 05:10 PM (This post was last modified: 04-14-2018 05:39 PM by Thomas Ritschel.)
Post: #3
 Thomas Ritschel Member Posts: 66 Joined: Feb 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
I have a solution based on Joe Horn's \Gs (sum of divisors) routine:

Code:
 %%HP: T(3)A(R)F(.); @ \Gs, by Joe Horn @ Sum of ALL the divisors of X \<< \-> n \<< n XQ FACTORS R\->I 1 + OBJ\-> 1. SWAP 2. / IP START PICK3 ROT 1 + ^ 1 - ROT 1 - / * NEXT \>> \>>

Code:
%%HP: T(3)A(R)F(.); @ Jacobi, by Thomas Ritschel @ number of representations @ Jacobi's four-square theorem \<< DUP 4 MOD IF 0 == THEN DUP 4 / \Gs 32 * NEG ELSE 0 END SWAP \Gs 8 * + \>>

For 720^20 it computed the result 42050501860687733694307540234728644161563553655537254442648 in less than 2 seconds (Edit: actually 0.8 sec).

However, it has a flaw: It doesn't work for the inputs 1 and 4 (\Gs fails if n==1).

Open for improvements...
04-14-2018, 06:17 PM
Post: #4
 Gerald H Senior Member Posts: 1,448 Joined: May 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
I have copied your programmes, Thomas, & for input

720^20

the programme returned

52175039830928864354013492999359544

in

1.42 sec.
04-14-2018, 08:18 PM (This post was last modified: 04-14-2018 08:36 PM by Thomas Ritschel.)
Post: #5
 Thomas Ritschel Member Posts: 66 Joined: Feb 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
(04-14-2018 06:17 PM)Gerald H Wrote:  I have copied your programmes, Thomas, & for input

720^20

the programme returned

52175039830928864354013492999359544

in

1.42 sec.

In my test I had 720^20 as an algebraic object on stack level 1, e.g. entered as '720^20'.

However, when 720^20 is evaluated to 1401683395356260729391818575873415577600000000000000000000 first, and then the Jacobi program is called, I also get 52175039830928864354013492999359544 in about 1.4 sec.

It turns out, that it fails for some kind of algebraic terms like 'a^b' or 'a*b', but not all of them (e.g. '3*11' seems to work well).

To make it save, an 'EVAL' should be added to the Jacobi program:

Code:
%%HP: T(3)A(R)F(.); \<< EVAL DUP 4 MOD IF 0 == THEN DUP 4 / \Gs 32 * NEG ELSE 0 END SWAP \Gs 8 * + \>>
04-15-2018, 12:08 AM
Post: #6
 Valentin Albillo Senior Member Posts: 591 Joined: Feb 2015
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
.
Hi, Gerald H:
(04-13-2018 11:35 AM)Gerald H Wrote:  The task is to write a User RPL programme to calculate the number of representations of any natural number exactly & swiftly.
[...]
I have a programme that processes 720^20 in 5.6 sec.

Nice challenge, regrettably I can't take part in it because it asks for an RPL solution, which I can't provide. However, you say that your program processes 720^20 in 5.6 sec and that's *amazing* speed indeed for such a big number, so I'd like to ask the following:

How long does your program take to process the vey slightly smaller number 720^20-3 ? And how long for the even smaller 720^20-18 ?

Thanks in advance and have a nice weekend.
V.
.

Find All My HP-related Materials here:  Valentin Albillo's HP Collection

04-15-2018, 04:58 AM
Post: #7
 Gerald H Senior Member Posts: 1,448 Joined: May 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
Yes, Valentin,

5.6 sec

is amazing for

720^20

, but the value was craftily chosen to only contain small factors each to a high power, as part of the algorithm my programme implements requires factorization of the input.

Similarly,

720^20-3

is craftily chosen to have large factors, thus practically rendering the calculation impossible on the 50g using my algorithm.

However, a more crafty algorithm obviating the need to factorize could enable the calculation on the 50g & I'm hopeful one may be found by a Forum member.
04-15-2018, 08:36 AM
Post: #8
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
Nice observations Valentin and Gerald! (And Thomas of course).

I for one, when a challenge is about the "context X" , wouldn't mind to see solutions "out of the box".

Can someone get 720^20-3 factorized at all (in a calculator context), and only after that factorized quickly? (Same for 720^20-18 and all the others hard variants)

Wikis are great, Contribute :)
04-15-2018, 11:42 AM (This post was last modified: 04-15-2018 11:44 AM by Thomas Ritschel.)
Post: #9
 Thomas Ritschel Member Posts: 66 Joined: Feb 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
Here is an improved version of my earlier program.
It is still using the idea from Joe's \Gs routine, but omits the even divisors:

Code:
%%HP: T(3)A(R)F(.); @ Jacobi, by Thomas Ritschel @ number of representations @ Jacobi's four-square theorem @ idea based on Joe Horn's \Gs \<< EVAL DUP 2 MOD 1 == 8 24 IFTE SWAP FACTORS DUP SIZE   IF 0 >   THEN R\->I OBJ\-> PICK3     IF 2 ==     THEN UNROT DROP2 2. -     END 1 SWAP 1. SWAP 2. / DUP     IF 0 >     THEN       START PICK3 ROT 1 + ^ 1 - ROT 1 - / *       NEXT *     ELSE DROP2 DROP     END   ELSE DROP   END \>>

Now it properly treats trivial inputs like 1 or 4 and works for algebraic inputs (like '720^20') as well.

The runtime has also improved:

0.66 sec for 720^20 entered as 1401683395356260729391818575873415577600000000000000000000
0.69 sec for 720^20 entered as '720^20'
04-15-2018, 02:07 PM
Post: #10
 Thomas Ritschel Member Posts: 66 Joined: Feb 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
I've got it further improved and significantly smaller:

Code:
%%HP: T(3)A(R)F(.); @ Jacobi, by Thomas Ritschel @ number of representations @ Jacobi's four-square theorem @ idea based on Joe Horn's \Gs \<< FACTORS DUP SIZE   IF 0 >   THEN R\->I OBJ\-> 1 SWAP 1. SWAP 2. /     START PICK3 DUP       IF 2 ==       THEN ROT DROP 1 UNROT       END ROT 1 + ^ 1 - ROT 1 - / *     NEXT   ELSE DROP 1   END 8 * \>>

Runtime for 720^20 and '720^20' is slightly slower: 0.69 and 0.72 secs, respectively.
04-15-2018, 03:09 PM
Post: #11
 Gerald H Senior Member Posts: 1,448 Joined: May 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
Very good, Thomas, for your latest version I have 720^20 returning correct value in .78 sec.

Programme returns wrong values for input 0 & 1.
04-15-2018, 03:34 PM (This post was last modified: 04-15-2018 03:35 PM by Thomas Ritschel.)
Post: #12
 Thomas Ritschel Member Posts: 66 Joined: Feb 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
(04-15-2018 03:09 PM)Gerald H Wrote:  Programme returns wrong values for input 0 & 1.

For input 1 it returns 8, which should be correct (= 2*4 possibilities).
But you're right, for 0 it should return 1 (not 8).

The following version of the program also treats 0 correctly:

Code:
%%HP: T(3)A(R)F(.); @ Jacobi, by Thomas Ritschel @ number of representations @ Jacobi's four-square theorem @ idea based on Joe Horn's \Gs \<< DUP   IF 0 ==   THEN DROP 1   ELSE FACTORS DUP SIZE     IF 0 >     THEN R\->I OBJ\-> 1 SWAP 1. SWAP 2. /       START PICK3 DUP         IF 2 ==         THEN ROT DROP 1 UNROT         END ROT 1 + ^ 1 - ROT 1 - / *       NEXT     ELSE DROP 1     END 8 *   END \>>
04-15-2018, 04:38 PM
Post: #13
 Gerald H Senior Member Posts: 1,448 Joined: May 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
Below my programme.

For 107 random 12 digit integers the ratio of

My Prog Time : Your Prog Time

is .84.

?

for input

1.

Size: 190.

CKSUM: # 4015d

Code:
« DUP   IF   THEN DUP 2 MOD     IF     THEN 8     ELSE       DO 2 IDIV2       UNTIL       END 2 * 1 + 24     END SWAP DUP 1 SAME     IF     THEN DROP     ELSE FACTORS OBJ→ DUP 2. + ROLL 1. ROT 2. /       START ROT 1 1 1. 6. ROLL         START SWAP PICK3 * DUP UNROT +         NEXT UNROT DROP2 *       NEXT     END   ELSE NOT   END »
04-15-2018, 06:54 PM (This post was last modified: 04-15-2018 06:55 PM by Thomas Ritschel.)
Post: #14
 Thomas Ritschel Member Posts: 66 Joined: Feb 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
(04-15-2018 04:38 PM)Gerald H Wrote:  Your programme returns

?

for input

1.

Well, by "any natural number" (quoting your initial post) I assumed positive integers (e.g. without a decimal dot).

By putting a R\->I in front of my program, it also works for numbers like 1. or 2.

Code:
%%HP: T(3)A(R)F(.); @ Jacobi, by Thomas Ritschel @ number of representations @ Jacobi's four-square theorem @ idea based on Joe Horn's \Gs \<< R\->I DUP   IF 0 ==   THEN DROP 1   ELSE FACTORS DUP SIZE     IF 0 >     THEN R\->I OBJ\-> 1 SWAP 1. SWAP 2. /       START PICK3 DUP         IF 2 ==         THEN ROT DROP 1 UNROT         END ROT 1 + ^ 1 - ROT 1 - / *       NEXT     ELSE DROP 1     END 8 *   END \>>
04-15-2018, 07:06 PM
Post: #15
 Gerald H Senior Member Posts: 1,448 Joined: May 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
Sorry, Thomas, my text was not clear - for input

1

the programme returns

?
04-15-2018, 07:11 PM
Post: #16
 Gerald H Senior Member Posts: 1,448 Joined: May 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
(04-15-2018 07:06 PM)Gerald H Wrote:  Sorry, Thomas, my text was not clear - for input

1

the programme returns

?

Sorry again, I created this problem by adjusting the programme FACTORS to return

{ 1 1. }

{}

for input

1

Your programme works correctly.
04-16-2018, 01:19 PM
Post: #17
 Thomas Ritschel Member Posts: 66 Joined: Feb 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
By dropping the ability to treat algebraic inputs and some minor changes I got my version slightly faster, but it still doesn't reach the speed of your program, Gerald, at the smaller inputs.

Code:
%%HP: T(3)A(R)F(.); @ Jacobi, by Thomas Ritschel @ number of representations @ Jacobi's four-square theorem @ idea based on Joe Horn's \Gs \<<   DUP   IF   THEN 8 SWAP FACTORS DUP SIZE     IF     THEN R\->I OBJ\-> PICK3       IF 2 ==       THEN SWAP DROP 1 SWAP       END       1 1. ROT 2. / DUP       IF       THEN         START PICK3 ROT 1 + ^ 1 - ROT 1 - / *         NEXT *       ELSE DROP2 DROP       END     ELSE DROP     END   ELSE DROP 1   END \>>
04-16-2018, 11:31 PM
Post: #18
 Valentin Albillo Senior Member Posts: 591 Joined: Feb 2015
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
(04-15-2018 08:36 AM)pier4r Wrote:  Nice observations Valentin and Gerald! (And Thomas of course).

Thanks for your appreciation and kind comment.

Quote:Can someone get 720^20-3 factorized at all (in a calculator context), and only after that factorized quickly? (Same for 720^20-18 and all the others hard variants)

I very much doubt it's doable on any 2018-era calculator (let alone "quickly") as 720^20-3 has two 23-digit prime factors and 720^20-18 has a 22-digit prime factor and a 35-digit one. In similar fashion, 720^20-19 and 720^20+19 are both prime.

Regards.
V.
.

Find All My HP-related Materials here:  Valentin Albillo's HP Collection

04-17-2018, 12:10 AM
Post: #19
 c0manche Junior Member Posts: 11 Joined: Jan 2018
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
(04-16-2018 11:31 PM)Valentin Albillo Wrote:
(04-15-2018 08:36 AM)pier4r Wrote:  Nice observations Valentin and Gerald! (And Thomas of course).

Thanks for your appreciation and kind comment.

Quote:Can someone get 720^20-3 factorized at all (in a calculator context), and only after that factorized quickly? (Same for 720^20-18 and all the others hard variants)

I very much doubt it's doable on any 2018-era calculator (let alone "quickly") as 720^20-3 has two 23-digit prime factors and 720^20-18 has a 22-digit prime factor and a 35-digit one. In similar fashion, 720^20-19 and 720^20+19 are both prime.

Regards.
V.
.

No surprises here just tried factorising 720^20-3 on an HP Prime and it throws a quadratic sieve failure
04-17-2018, 05:03 AM
Post: #20
 Gerald H Senior Member Posts: 1,448 Joined: May 2014
RE: HP 50g Programming Competition: How Many Partitions of an Integer in 4 Squares
On a Samsung S4 Android mobile phone

720^20-3

is completely factorized in seconds using

factorint

function in PariDroid