Palindromes

# Palindromes for the HP-41

Overview

1°)  Integer -> A Palindrome
2°)  Integer = Sum of Palindromes

1°)  Integer -> A Palindrome

-"PAL" takes a positive integer in X-register and returns a palindrome in X-register
-For example if X = 678 , "PAL" computes:

678+876     =  1554
1554+4551   =  6105
6105+5016   = 11121
11121+12111 = 23232

Data Registers:     R00 = temp
Flags: /
Subroutines: /

 01 LBL "PAL"  02 LBL 00  03 STO 00  04 XEQ 10  05 RCL 00  06 X=Y?  07 GTO 02  08 +  09 VIEW X  10 GTO 00  11 LBL 10  12 0  13 X<>Y  14 LBL 01  15 RCL X  16 10  17 ST* T  18 ST/ Z  19 MOD  20 ST+ Z  21 RDN  22 INT  23 X#0?  24 GTO 01  25 X<>Y  26 RTN  27 LBL 02  28 CLD  29 END

( 48 bytes / SIZE 001 )

 STACK INPUT OUTPUT X N > 0 Palindrome

Example:    678  XEQ "PAL"  the HP41 displays the successive results ( 1554  6105  11121  23232 )

and finally returns  X = 23232

Notes:

-The result is meaningless if the sum becomes larger than 9999999999
-So you could add something like E10  X<=Y?  E^X  X<>Y  after line 08
-Thus, the HP41 will display OUT OF RANGE  in this case

2°)  Integer = Sum of Palindromes

-"SPAL" takes a positive integer in X-register and stores in R05-R06-.....  palindromes  p1 , p2 , ....  such that  N = p1 + p2 + ...

Data Registers:     R00 to R04 = temp    R05-R06-......-Ree = the palindromes whose sum = N
Flags: /
Subroutines: /

 01 LBL "SPAL"  02 10  03 STO 04          04 4  05 STO 00  06 X<> Z  07 GTO 01  08 LBL 10  09 0  10 X<>Y  11 LBL 02  12 RCL X  13 RCL 04  14 ST* T  15 ST/ Z  16 MOD  17 ST+ Z 18 RDN  19 INT  20 X#0?  21 GTO 02  22 X<>Y  23 RTN  24 LBL 01  25 ISG 00  26 CLX  27 STO 01  28 XEQ 10  29 RCL 01          30 X=Y?  31 GTO 04  32 LOG  33 RCL 04  34 X<>Y 35 X=Y?  36 9.1  37 FRC  38 X=0?  39 GTO 03  40 X<> L  41 INT  42 RCL 01  43 RCL 01          44 1  45 R^  46 +  47 2  48 /  49 INT  50 10^X  51 STO 03 52 MOD  53 -  54 RCL 03  55 -  56 STO 02  57 LASTX  58 /  59 X=0?  60 9  61 XEQ 10  62 RCL 03  63 MOD  64 RCL 02          65 +  66 STO IND 00  67 RCL 01  68 X<>Y 69 -  70 GTO 01  71 LBL 03  72 RCL 01  73 1  74 -  75 STO IND 00  76 LASTX  77 ST+ 00  78 LBL 04  79 STO IND 00  80 RCL 00          81 .1  82 %  83 5  84 +  85 STO 00  86 END

( 119 bytes / SIZE var. )

 STACK INPUT OUTPUT X N > 0 5.eee

Where  5.eee  is the cotrol number of the registers containing the palindromes

Example:     Express  9999999998  as a sum of palindromes

9999999998  XEQ "SPAL"   >>>>   5.010                                 ---Execution time = 20s---

and we have in registers R05 to R10:

R05 = 9999889999
R06 =         108801
R07 =             1001
R08 =               181
R09 =                   9
R10 =                   7
---------------------------
SUM = 9999999998

Notes:

-Lines 33 to 36 avoid an error when the number N is very large ( close to E10 )

-The method works well but it doesn't always give the best solution
-Cf reference [1] for better algorithms... which would require many bytes with an HP41 !

References:

[1]  Javier Cilleruello , Florian Luca , Lewis Baxter - "Every Positive Integer is a Sum of Three Palindromes"
[2]  William D. Banks - "Every Natural Number is the Sum of Forty-nine Palindromes"