Product-sum numbers

2015-12-18

Problem 088: Product-sum numbers

Description:

A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1, a2, ... , ak} is called a product-sum number: N = a1 + a2 + ... + ak = a1 * a2 * ... * ak.

For example, 6 = 1 + 2 + 3 = 1 × 2 × 3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.

k=2:  4 = 2 * 2 = 2 + 2
k=3:  6 = 1 * 2 * 3 = 1 + 2 + 3
k=4:  8 = 1 * 1 * 2 * 4 = 1 + 1 + 2 + 4
k=5:  8 = 1 * 1 * 2 * 2 * 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 * 1 * 1 * 1 * 2 * 6 = 1 + 1 + 1 + 1 + 2 + 6

Hence for 2<=k<=6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for 2<=k<=12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2<=k<=12000?

Solution:

v XXXX
  OOOO

### ... ###
### ... ###
### ... ###

### ... ###
### ... ###
### ... ###

                                            vp+8+8/g05\%g05:\1:p+3/<
>"`` "+*20p"}`"*30p8:*:*:*:*40p28*8*8*50p20g>:!#v_1-:40g\:50g%\50g ^
vp142p13+1g03p122p+8812                       $<v:--g14g13g03g14<
v                          <                    #              _^#-3++`g14g+3/g05\%g05:--g1<                         <p+3/g05\%g05:-<
>31g1+31p 082*g::41g\/\1+*4 1p1+082*p051p  >41g31g30g21g-+`#v_30g31g41g--1`41g31g`!30g31g4 ^g--:50g%\50g/3+g41g`++3-#^_41g30g31g41g-^
                            ^p+3/g05\        %g05<           > 51g:50g%\50g/82*+g:41g\/41p3v
vp15+1g15p13+\g13p14*\g14:g+*28/g05\%g05:g1 5p+*28/g05\%g05:g15g+*28/g05\%g05:+1g15p13-\g1<
>51g30g1+-#v_              v               ^                              <
v  p13+1g13<
>51g:50g%\50g/82*+g::1+51g:50g%\50g/82*+p 41g\/41p1+41g*41p51g21g`#v_     ^
vp310p300                   <                                       >51g21p^
                 >3+g61g1+:50g%\50g/3+p61g:50   v >$$v
    >1pv>71g-  #v v#                 <          #  $_v#`\g18<
    7v0<^:g+3/g< ^ /g05\%g05:g16g+3/g 05\%g05:+1:p16:< >81g-|
>01-^>::50g%\50^ v_$:0\:50g%\5 0g/3+p^>::50g%\50g/3+g::|    $
     ^_v#-g02:+1<>:71g`#v_81p:>1-:1+  |         # ^  $$<    1
       $        ^      $># 7#  1 p# <$<0  p+3/g05\%g05:\0  +<
    v00<                      ^p+3/g05        \%<
    v+1                        <
    >::91p50g%\50g/3+g+91g:30g-|
                               >$.$@

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Let's say LIMIT is our maximum value of k (12 000).

We start with an array of size LIMIT, filled with ones. Our current sum is LIMIT and our current product is 1. To kickstart the whole progress we set arr[1] = 2 (now sum is LIMIT+1 and product is 2). We also remember the amount of changed fields, which are possible not one (initial 2).

Now we iterate through all the possible array-combinations (with a few tricks to limit the search-space).

In each step we increment array[0]. And update the fields sum and product. This update is not that complex, sum is incrementing by 1 and product is (product / arr[0]-1) * arr[0]
While prod > sum + (LIMIT - len) we reset the current arr[pos] to arr[pos + 1] and increment arr[pos + 1] (and obviously increment pos and update sum and product)
After that we have a valid array valud. We can now test for which value of k this is a result (and if is is better than a previous found value)
The value of k is k := LIMIT - (sum - prod) The trick here is that we generate a solution by cutting away a lot of the ones at the end of our array to get a solution where prod = sum (cutting ones decreemnts sum but leaves prod unchanged).
The condition to cut away only ones is given by our previous condition prod > sum + (LIMIT - len).
After we have gone through all the possible values this way we only have calculate the sum of all the unique values

Because in the last step the list is almost sorted (not totally sorted but there arent that many cases where result[i] > result[i+1]) we can use a need little algorithm which eliminates duplicates by running through the list and doing sum occasional backtracing with an complexity of almost O(N).

I know, the algorithm got a bit complex, but it's pretty fast - even when converted to befunge.

Interpreter steps:	141 097 978
Execution time (BefunExec):	23s (5.92 MHz)
Program size:	1024 x 50
Solution:	7587457
Solved at:	2015-12-18