(HP15C / HP41 ) Recursive program of the 1st April

[Nihotte(lma)]

Some digits for a sum !

To celebrate the today April 1, I offer a small recursive program (lol) for the HP15C and the HP41
The purpose is to express a number into several distinct digits which, added together, match this number
With all the possibility, please...
Almost easy !
Yes ! But each digit (from 1 to 9) should be use only a time in the final sum !
So, the bigger number you can targeted is 45 (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45)
Example : 13 by 2 digits consists in (7 + 6), (8 + 5) and (9 + 4)

I don't remember how and when this idea came to me, but my programs for HP15C et HP41 date back to 2004...

Take the precaution of reserving space for the memory registers, by selecting partition
- HP15C : 32 f DIM (i)
- HP41 : SIZE 034

An example of operation :
Type 23 ENTER 2 and
- HP15C : GSB A
- HP41 : XEQ DCOMP
Read back :
76 R/S
85 R/S
94 R/S
0


Why recursive ?

That's because the program is based on this recursive function :

Find_Sum(array, target, max, sum, used, ind)
go = true
while (ind >= 1) and go do
if (used + 1 == max) then
if (sum + ind == target) then
array[ind] = busy; go = false
display(array)
else if (sum + ind > target) then
ind = ind - 1
else
go = false
end if
else if (used + 1 < max) then
if (sum + ind < target) then
array[ind] = busy
Find_Sum(array, target, max, (sum + ind), (used + 1), (ind - 1))
array[ind] = free; ind = ind - 1
else
ind = ind - 1
end if
else
go = false
end if
wend


For the example :
initial call with Find_Sum([0, 0, 0, 0, 0, 0, 0, 0, 0], 13, 2, 0, 0, 9)
the function returns (7, 6) (8, 5) and (9, 4)

Parameters
array is array [1..9] of free or busy (0 or 1) is 000000000 to 111111111
target is integer from 1 to 45
max is index from 0 to 9
sum is integer from 0 to 45
used is index // digit from 0 to 9 : used = INT ( LOG ( array )) + 1 // Sum of contents of array[i] when i grows from 1 to 9
ind is index from 0 to 9

[Gamo]

Very nice recursive program.

A little typo though at the example provided here.


An example of operation :
Type 23 ENTER 2 and <-------- is this suppose to be 13 ?
- HP15C : GSB A
- HP41 : XEQ DCOMP
Read back :
76 R/S
85 R/S
94 R/S
0


Thanks

Gamo[/color]

[Nihotte(lma)]

Oh yes, Gamo !!
This is effectively a 13 as target.
Thank you for your vigilance !

In fact, it's interesting to test 23 by 4 digits because it's return several results !
But it's rather slow with the HP15C


-----------------------------------------------------------------------------------------

(04-02-2020 09:26 AM)Gamo Wrote:  Very nice recursive program.

A little typo though at the example provided here.


An example of operation :
Type 23 ENTER 2 and <-------- is this suppose to be 13 ?
- HP15C : GSB A
- HP41 : XEQ DCOMP
Read back :
76 R/S
85 R/S
94 R/S
0


Thanks

Gamo[/color]

[Nihotte(lma)]

Hello !

I'm coming back on this thread because I remember WHY !
This detail has occupied my mind last days and after a deep introspection, I think I have found out the good reason !!

At this time (2004), I liked very much to make some cross-numbers grids. One of the favorite problem to solve is like «the sum of figures is XX» !

The first program I made was for the HP48G-GX (it was my usual calculator at time and it was the faster one).
So, it was much more practical to find the correct answer such a question in the grid.
The program was, then, interested in numbers whose sum derived only from the 1 to 9 numbers.

I just adjusted it (yesterday) so that I could also use hexadecimal (A - F) numbers and I could bring the highest amount managed to 120 instead of only 45.

The output display has been modified too and it is close to this one on used in the HP16C.
It relies on the possibility of designating which figures are used to arrive at the sum.
Thus, the displayed result should be understood as a light board on which the selected figures are lit !
To get the total of 120, all the digits from 15 (hexadecimal F) to 1 are involved.
So, they are all on : the result is 7FFFFh. (cf. examples, below)

Here is the program on HP48 :


Objects for the HP48
-------------------------------


RESUL
{ #7FFFFh }

AJOUT #1110h 31
« 'RESUL' SWAP HEX STO+ »

RECHE #2310h 433.5
« → t n m s c i
« 4 SF i
WHILE DUP 1 ≥ 4 FS? AND
REPEAT
→ i
« i
IF c 1 + m == THEN
IF s i + n == THEN
t 2 i 1 - ^ R→B OR
AJOUT 4 CF
ELSE
IF s i + n > THEN
1 -
ELSE
4 CF
END
END
ELSE
IF c 1 + m < THEN
IF s i + n < THEN
t 2 i 1 - ^ R→B OR
n m s i + c 1 + i 1 -
RECHE 4 SF 1 -
ELSE
1 -
END
ELSE
4 CF
END
END
»
END
»
DROP 4 CF
»

DCOMP #B2D4h 109.5
« → n m
« { } 'RESUL' STO
#0h n m 0 0 15 RECHE
'RESUL' RCL
»
»


Use
------

13 SPC 2 DCOMP
{
#801h // 12 + 1
#402h // 11 + 2
#204h // 10 + 3
#108h // 9 + 4
#90h // 8 + 5
#60h // 7 + 6
}

120 SPC 15 DCOMP
{
#7FFFF // 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b
// 15+14+13+12+11+10+9+8+7+6+5+4+3+2+1
}

Nota : To switch between a display in HEX or BIN mode you should key in MTH → BASE → HEX or BIN

[Nihotte(lma)]

Oops ! Please, read #7FFF (only 15 bits !) for he result of 120 by 15...

[Nihotte(lma)]

The same listing for HP15C and HP41 system with included example
(Thank you for you practical note, rprosperi)

[Nihotte(lma)]

Do you know The Shadoks ?
(from Jacques Rouxel and Claude Piéplu on French TV between years 1968 and 1973)

The Shadoks were known for mottos such as:
« Why do it the easy way when you can do it the hard way ? »
(« Pourquoi faire simple quand on peut faire compliqué ? »)

Now, I know why : to make it running on the HP12C, of course !!

So, the program version for the HP12C is coming in the dance too.

And as usual, with other of my works already published in this forum for this calculator, no use of index register or indirect memories in this program.
However, one register acts as the stack and another as the level pointer.

Some compromises have been necessary.
For example, no use of CLEAR REG is possible in a program on the HP12C; so this action is needed before to run the expected search.
In other way, the constant memory of the calculator does'nt save the program pointer.
If a long program falls in auto power off after displaying a result, you must resume with a manual GTO 35 and R/S.
(However, in the majority of cases, the first responses are coming relatively quickly with this version of the program - try 45 ENTER 9 !).

Remark :
After a first full process, at the global end of the search, the work registers are empty again.
Like after a f CLEAR REG.
But PMT always retains 10 !
In this case, no needs to CLEAR all the memories or to store 10 on PMT again.

The listing of the program assumes two examples of use.



13/04/2020 - 22:48 : program fall --> program falls

[Nihotte(lma)]

Some digits for a sum

The extended implementation of the program for the HP16C is close to its version for the HP12C .
This umpteenth version directly displays each result of the search explicitly with all its required digits.

The mechanism implemented in this program is the same as that used in the version for the HP12C.
Effectively, 15 hexadecimal digits can fit in a 64-bit word (60 bits is enough).

So, this is the program, to find at most the 15 digits to use for a sum of 120.

(Unlike the HP12C, there is no arithmetic on the registers for the HP16C. 1, STO + 1 changes to RCL 1, 1, +, STO 1. However, the tests are more provided. The consolidation of the 2 implementations makes it possible to write, in the same spirit, a version optimized for the HP11C ! Welcome in the dance, too...).

[Nihotte(lma)]

(04-12-2020 12:27 PM)Nihotte(lma) Wrote:  « Why do it the easy way when you can do it the hard way ? »
(« Pourquoi faire simple quand on peut faire compliqué ? »)
To make it running on the HP12C, of course !!

Here is a other version of the program for the HP12C to compute the list of digits that matches a number when you all add them !
I've just cut some lines not really essential, even if it locked all the options in the chosen algorithm !
Perhaps could you even succeed in again improving it !
(The use process is not modified)


STO 6
x<>y
STO 5
9
STO 2
(06) RCL 2
g x=0
g GTO 46
RCL PMT
STO x 0
RCL 2
STO + 0
STO + 3
EEX
STO + 1
STO - 2
RCL 6
RCL 1
-
g x=0
g GTO 40
RCL 5
RCL 3
-
EEX
g x<=y
g GTO 06
(28) RCL PMT
STO / 0
RCL 0
g FRAC
STO - 0
x
STO 2
STO - 3
EEX
STO - 1
STO - 2
g GTO 06
(40) RCL 5
RCL 3
-
g x=0
g GTO 50
g GTO 28
(46) RCL 1
g x=0
g GTO 54
g GTO 28
(50) RCL 3
RCL 0
R/S
g GTO 28
(54) RCL 6
RCL 5
g GTO 00

56 lines
P-57 r-13

22/04/2020


Some digits for a sum


Examples of use :

f CLEAR REG
10 STO PMT
f 0
g GTO 00

13 ENTER 2 R/S
94 R/S
85 R/S
76 R/S
(13)

45 ENTER 9 R/S
987654321 R/S
(45)

[Nihotte(lma)]

Some digits for a sum

There is my ultimate version for the HP15C...

So, here is a final version of the program for the HP15C which includes all the remarks already referring to the more recent posts

After all this journey, the circle is complete !

Thanks