HP 50g: Programming Problem: Integer Partition in Palindromic Integers

[Gerald H]

Every integer can be written as the sum of palindromic integers, eg

542 = 535 + 7

& in fact 49 palindromes are sufficient to express any integer, as proven here

https://arxiv.org/pdf/1508.04721.pdf

The task I'm interested in is producing a stand alone User RPL programme for the 50g that will decompose any positive integer into a sum of palindromes, the fewer the better.

For example the number

407374883553280653444058251937

can be decomposed in 120 palindromes:

Code:

:120:{
99999999999999999999999999999
99999999999999999999999999999
99999999999999999999999999999
99999999999999999999999999999
999999999999999999999999999
999999999999999999999999999
999999999999999999999999999
999999999999999999999999999
999999999999999999999999999
999999999999999999999999999
999999999999999999999999999
99999999999999999999999999
99999999999999999999999999
99999999999999999999999999
9999999999999999999999999
9999999999999999999999999
9999999999999999999999999
9999999999999999999999999
9999999999999999999999999
9999999999999999999999999
9999999999999999999999999
999999999999999999999999
999999999999999999999999
999999999999999999999999
999999999999999999999999
99999999999999999999999
99999999999999999999999
99999999999999999999999
99999999999999999999999
99999999999999999999999
99999999999999999999999
99999999999999999999999
99999999999999999999999
9999999999999999999999
9999999999999999999999
9999999999999999999999
9999999999999999999999
9999999999999999999999
9999999999999999999999
9999999999999999999999
9999999999999999999999
999999999999999999999
999999999999999999999
999999999999999999999
99999999999999999999
99999999999999999999
99999999999999999999
99999999999999999999
99999999999999999999
9999999999999999999
9999999999999999999
9999999999999999999
9999999999999999999
9999999999999999999
999999999999999999
999999999999999999
999999999999999999
99999999999999999
99999999999999999
9999999999999999
9999999999999999
9999999999999999
9999999999999999
9999999999999999
9999999999999999
9999999999999999
9999999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
9999999999999
9999999999999
9999999999999
9999999999999
9999999999999
999999999999
999999999999
999999999999
99999999999
99999999999
99999999999
99999999999
9999999999 9999999999
9999999999 9999999999
999999999 999999999
999999999 999999999
9999999 9999999
9999999 9999999
9999999 999999 999999
999999 999999 999999
999999 999999 999999
99999 99999 9999 9999
9999 9999 9999 999
999 22 11 9 9 1 }

& in 6

Code:

:6:{
407374883553280082355388473704
571088666880175
2897982 66 9 1 }

& in 5

Code:

:5:{
407374883553280082355388473704
571088646880175
22888822 9229 7 }

which may be minimal.

The programme should produce a list ordered by decreasing magnitude & tagged with the number of elements.

Smaller & faster programmes are desirable but the critical characteristic is lowest number of elements in the decomposition.

As a standard test for the programme I suggest input of

13^1313

a 1,463 digit integer, correct decompositions being the target & least number of elements deciding the winner.