09-17-2016, 01:36 PM

09-17-2016, 03:57 PM

Gene,

while the description explicitly states that we may assume 1 <= k <= 9 and 1 <= n <= 100, 2 of the 5 test cases use degenerate input (k=12 and n=0). So, do we have to test for these or not?

Cheers, Werner

while the description explicitly states that we may assume 1 <= k <= 9 and 1 <= n <= 100, 2 of the 5 test cases use degenerate input (k=12 and n=0). So, do we have to test for these or not?

Cheers, Werner

09-17-2016, 04:03 PM

You can assume inputs between 1 <= n <= 9 and 1 <= k <= 100 (81 of course).

:-)

:-)

09-18-2016, 12:44 AM

Some clarifications please: The contest says minimum bytes or steps with registers counting for 8 bytes. On the 34S a step occupies two bytes and register is equivalent to 4 steps. Is the intention to count registers as eight steps (i.e. double their worth)?

Do the lettered registers count as used registers? They cannot be converted into program steps.

Likewise, does the stack count towards register use?

What about the statistical accumulations? These do eat into program space and occupy 140 bytes on the first sigma+.

Pauli

There are exceptions to the two byte instruction length but these won't be used here. Also, double precision registers are twice the size but again won't be used.

Do the lettered registers count as used registers? They cannot be converted into program steps.

Likewise, does the stack count towards register use?

What about the statistical accumulations? These do eat into program space and occupy 140 bytes on the first sigma+.

Pauli

There are exceptions to the two byte instruction length but these won't be used here. Also, double precision registers are twice the size but again won't be used.

09-18-2016, 01:06 AM

My intent was simply to penalize using "memories" of any kind of register usage.

Solution A is 80 bytes and uses no registers.

Solution B is 80 bytes but uses 30 memories.

Solution A wins.

Using the statistics registers is a good example. It should require a +140 to the byte count.

Here on the museum, the community will ultimately decide (as it should) the best solution. :-)

Here at HHC, I will do the best I can in the hour I'll have to judge every solution to this and the RPL contest. I don't ever have much time for lunch on Sundays at the conferences. :-)

Solution A is 80 bytes and uses no registers.

Solution B is 80 bytes but uses 30 memories.

Solution A wins.

Using the statistics registers is a good example. It should require a +140 to the byte count.

Here on the museum, the community will ultimately decide (as it should) the best solution. :-)

Here at HHC, I will do the best I can in the hour I'll have to judge every solution to this and the RPL contest. I don't ever have much time for lunch on Sundays at the conferences. :-)

09-18-2016, 04:42 AM

I've got a solution in 32 steps and four registers that runs essentially instantly for any inputs.

I'm sure it can be significantly improved -- it is taking a fairly naïve approach to the problem.

Pauli

I'm sure it can be significantly improved -- it is taking a fairly naïve approach to the problem.

Pauli

09-18-2016, 05:30 AM

(09-18-2016 04:42 AM)Paul Dale Wrote: [ -> ]I've got a solution in 32 steps and four registers that runs essentially instantly for any inputs.

{ { 2, 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 } { 3, 1 3 6 10 15 21 28 36 45 54 61 66 69 70 69 66 61 54 } { 4, 1 4 10 20 35 56 84 120 165 219 279 342 405 465 519 564 597 615 } { 5, 1 5 15 35 70 126 210 330 495 714 992 1330 1725 2170 2654 3162 3675 4170 } { 6, 1 6 21 56 126 252 462 792 1287 2001 2992 4317 6027 8162 10746 13782 17247 21087 } { 7, 1 7 28 84 210 462 924 1716 3003 5004 7995 12306 18312 26418 37038 50568 67353 87648 } { 8, 1 8 36 120 330 792 1716 3432 6435 11439 19433 31732 50016 76350 113178 163284 229713 315645 } { 9, 1 9 45 165 495 1287 3003 6435 12870 24309 43741 75465 125445 201675 314523 477015 705012 1017225 } }

Lists format:

{k, f(k,1) f(k,2) f(k,3) ... f(k,18)}

0,62 seconds on m48+ running on iPhone SE (all lists)

f(9,19) = 1435005 (0.3695 s on the real HP 50g)

If only my formula worked for n >= 20... the conversion to wp34s would be fairly easy.

Looking forward to your solutions... and formulas :-)

Gerson.

09-19-2016, 05:20 AM

My algorithm calculates the number of numbers of the required length or shorter that digit sum to the correct amount and then subtracts the number of numbers of one less than the required length -- this was the quick way to handle leading zeros and still get a direct combinatorial solution.

I didn't figure out a combinatorial solution that dealt with leading zeros properly and I suspect I'm missing something really obvious. It wasn't a great weekend for me

The END doesn't count (I hope), the initial LBL B can be omitted. Using the assembler, we can get relative subroutine calls which saves a step. Without this add LBL 01 between steps 7 and 8 and change the two BSR a to XEQ 01 and add one step. It uses four registers.

I suspect this can be further optimised, I really didn't spend a lot of time on this.

The program doesn't deal with out of range inputs since the clarification that they weren't allowed. It should scale up to larger input values too.

Pauli

I didn't figure out a combinatorial solution that dealt with leading zeros properly and I suspect I'm missing something really obvious. It wasn't a great weekend for me

Code:

` LBL B`

01: [cplx]STO J

02: DEC Y

03: XEQ a

04: [cplx]x[<>] J

05: XEQ a

06: RCL- J

07: RTN

08: a:: [cplx]STO 00

09: # 010

10: /

11: IP

12: MIN

13: 0

14: x[<>] Y

15: [Sigma] 00

16: RTN

17: LBL 00

18: (-1)[^x]

19: RCL 01

20: RCL Z

21: COMB

22: *

23: RCL 00

24: RCL+ 01

25: # 010

26: RCL* T

27: -

28: DEC X

29: RCL 01

30: DEC X

31: COMB

32: *

END

The END doesn't count (I hope), the initial LBL B can be omitted. Using the assembler, we can get relative subroutine calls which saves a step. Without this add LBL 01 between steps 7 and 8 and change the two BSR a to XEQ 01 and add one step. It uses four registers.

I suspect this can be further optimised, I really didn't spend a lot of time on this.

The program doesn't deal with out of range inputs since the clarification that they weren't allowed. It should scale up to larger input values too.

Pauli

09-19-2016, 11:09 AM

No replies to this, so everyone is as stumped as I am? ;-)

I'm still trying to figure out your 'direct combinatorics'.

And I can see only one very small improvement, that even a WP34 beginner like me could spot: division by 10 (steps 8 and 9) is the same as SDR 001, no?

Cheers (meaning, in this case, 'bravo'),

Werner

I'm still trying to figure out your 'direct combinatorics'.

And I can see only one very small improvement, that even a WP34 beginner like me could spot: division by 10 (steps 8 and 9) is the same as SDR 001, no?

Cheers (meaning, in this case, 'bravo'),

Werner

09-19-2016, 11:42 AM

(09-19-2016 11:09 AM)Werner Wrote: [ -> ]And I can see only one very small improvement, that even a WP34 beginner like me could spot: division by 10 (steps 8 and 9) is the same as SDR 001, no?

One step saved

Pauli

09-19-2016, 11:44 AM

I have a brute force solution in 27 steps and 2 local registers but I would like to understand the formulas used in Pauli's version as I can't compete on the execution time.

After entering the program press [g] [RTN] to position the program pointer to step 001 and to clear the return stack, then enter k and n values and press R/S.

To compute new f(k,n) after the result of the previous run has been displayed, just enter the new values of k and n and press R/S again.

I don't check for k>9 or n>100.

Code:

`001 LocR 002`

002 STO-.00 // n saved in R.00

003 x<>y

004 10^x

005 STO Y //last value in Y

006 SDR 001 //start value in X

007 CLα

008 αIP X

009 #048

010 αLENG

011 *

012 ENTER

013 DROP

014 α->x

015 -

016 αLENG

017 x#0?

018 BACK 005

019 DROP

020 X=? .00

021 INC .01

022 DROP

023 INC X

024 x<? Y

025 BACK 018

026 RCL .01

027 RTN

After entering the program press [g] [RTN] to position the program pointer to step 001 and to clear the return stack, then enter k and n values and press R/S.

To compute new f(k,n) after the result of the previous run has been displayed, just enter the new values of k and n and press R/S again.

I don't check for k>9 or n>100.

09-19-2016, 12:09 PM

Some explanation about my approach.

We're looking for \( \sum_{i=1}^{k}x_i = n \) where each \( x_i \) is a single digit. Without the single digit restriction, there are \( \binom{n+k-1}{k-1} \) possibilities (see e.g. here).

To enforce the must be a digit restriction use the inclusion-exclusion principle to remove the illegal cases with digits > 10 from the above result.

A bit of fiddling around gives: \( \sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1} \)

However, this allows leading zeros, so we do the summation a second time for k-1 instead of k and subtract that from the first sum to get the result:

\( \sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1} - \sum_{i=0}^{min(k-1, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k-1}{i} \binom{n+k-10i-2}{k-2} \)

I feel that there should be a more direct approach, but can't see it. My allergies have been dreadful for the last week and I'm not thinking even close to straight, so I could easily be completely wrong about all of this.

- Pauli

We're looking for \( \sum_{i=1}^{k}x_i = n \) where each \( x_i \) is a single digit. Without the single digit restriction, there are \( \binom{n+k-1}{k-1} \) possibilities (see e.g. here).

To enforce the must be a digit restriction use the inclusion-exclusion principle to remove the illegal cases with digits > 10 from the above result.

A bit of fiddling around gives: \( \sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1} \)

However, this allows leading zeros, so we do the summation a second time for k-1 instead of k and subtract that from the first sum to get the result:

\( \sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1} - \sum_{i=0}^{min(k-1, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k-1}{i} \binom{n+k-10i-2}{k-2} \)

I feel that there should be a more direct approach, but can't see it. My allergies have been dreadful for the last week and I'm not thinking even close to straight, so I could easily be completely wrong about all of this.

- Pauli

09-19-2016, 12:16 PM

(09-19-2016 11:44 AM)Didier Lachieze Wrote: [ -> ]I have a brute force solution in 27 steps and 2 local registers ...

Neat solution. I didn't even consider using the alpha register.

I did think about decomposing numbers into digits and building digits to form the number but neither worked out well. Alpha does this directly and superbly.

Pauli

09-19-2016, 01:47 PM

(09-19-2016 12:09 PM)Paul Dale Wrote: [ -> ]\( \sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1} - \sum_{i=0}^{min(k-1, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k-1}{i} \binom{n+k-10i-2}{k-2} \)

The most difficult part is deriving a working formula. Congratulations and thanks! Give me a formula and I'll move the world:-)

If n < 10, then a 7-step would do the job:

Code:

001- LBL A

002- +

003- DEC X

004- DEC X

005- RCL L

006- DEC X

007- COMB

END

Results start to be different when n > 9. I tabulated the first few differences for the case k = 6 and generalized the corresponding OEIS sequence for k, but this would work only for n up to 19. At this point I switched to the HP 50g for clarity:

Code:

« → k n

« 'COMB(n+k-2,;k-1,)' EVAL n 9, >

IF

THEN 'COMB(n+k-12,;k-2,)*(k*(n-9,)-1,)/(k-1,)' -

END

»

»

No further improvement from here, though.

(09-19-2016 12:09 PM)Paul Dale Wrote: [ -> ]My allergies have been dreadful for the last week and I'm not thinking even close to straight, so I could easily be completely wrong about all of this.

I woke up late on Sunday and remained in bed for the next eight or ten hours. Low blood sugar level, I think, six months after the latest episode. But I wouldn't have been able to find a solution anyway, as I can't think of anything even today, when it's gone.

Hope you are better now.

Gerson.

09-19-2016, 09:19 PM

Steps 13 and 14 in my original program are not required -- I forgot how the Sigma function takes it arguments Combine this with the earlier one step saving and my solution is down to 29 steps.

Pauli

Pauli

09-20-2016, 06:41 AM

(09-19-2016 01:47 PM)Gerson W. Barbosa Wrote: [ -> ]If n < 10, then a 7-step would do the job:

You mean, five?

Code:

`001- LBL A`

002- DEC X

003- DEC Y

004 STO+ Y

005- COMB

006- END

;-)

Cheers, Werner

09-20-2016, 09:03 AM

Hello!

So now that we have seen that feeding values to a built-in function (*) results in the shortest program I am really curious to see the SR56 implementation!

Regrads

Max

(*) yes I know, the smart thing is to see this solution in the first place

So now that we have seen that feeding values to a built-in function (*) results in the shortest program I am really curious to see the SR56 implementation!

Regrads

Max

(*) yes I know, the smart thing is to see this solution in the first place

09-20-2016, 09:17 AM

The shortest implementation thus far is a brute force approach. My combinatorial approach is several more steps.

Pauli

Pauli

09-20-2016, 12:21 PM

Only one solution was presented at HHC. Namir Shammas gave a solution that works, but has a rather long run time for some inputs.

Since there was only one solution, no winner was declared.

Test inputs were:

Since there was only one solution, no winner was declared.

Test inputs were:

Code:

`k n F(k,n)`

4 20 597

7 12 12,306

3 12 66

6 50 126

6 30 47,631

2 15 4

5 44 5

5 20 4,998

Code:

01: STO 01

02: X<>Y

03: DEC X

04: 10

05: X<>Y

06: Y^X

07: STO 00

08: 10

09: *

10: STO 03

11: 0

12: STO 02

13: LBL 00

14: RCL 00

15: X=? 03

16: GTO 01

17: 0

18: RCL 00

19: LBL 02

20: ENTER

22: ENTER

23: 10

24: STO / Z

25: STO / Y

26: X<>Y

27: FP

28: *

29: STO+ Z

30: RDN (ROLL DOWN)

31: IP

32: X NOT EQUAL 0

33: GTO 02

34: RDN

35: X=? 01

36: INC 02

37: INC 00

38: GTO 00

39: LBL 01

40: RCL 02

41: END

09-20-2016, 04:00 PM

(09-19-2016 09:19 PM)Paul Dale Wrote: [ -> ]Steps 13 and 14 in my original program are not required -- I forgot how the Sigma function takes it arguments Combine this with the earlier one step saving and my solution is down to 29 steps.

Kudos for the formula! Here is a slightly modified version of your solution with one step and one register less: 29 steps including the END and using 3 registers (I,J,K) instead of 4 (J,K,00,01), still a bit longer than my brute force solution (2 steps and 1 register more) but much much more faster !

Code:

`01: [cplx]STO J`

02: XEQ a

03: DEC K

04: XEQ a

05: RCL- I

06: RTN

07: a:: [cplx]RCL J

08: SDR 001

09: IP

10: MIN

11: [Sigma] 00

12: x<> I

13: RTN

14: LBL 00

15: (-1)[^x]

16: RCL K

17: RCL Z

18: COMB

19: *

20: RCL J

21: # 010

22: RCL* T

23: -

24: RCL K

25: DEC X

26: STO+ Y

27: COMB

28: *

29: END