Product-sum numbers

Statement

The problem can be found here.

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 x a2 x … x ak.

For example, 6 = 1 + 2 + 3 = 1 x 2 x 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 x 2 = 2 + 2

k=3: 6 = 1 x 2 x 3 = 1 + 2 + 3

k=4: 8 = 1 x 1 x 2 x 4 = 1 + 1 + 2 + 4

k=5: 8 = 1 x 1 x 2 x 2 x 2 = 1 + 1 + 2 + 2 + 2

k=6: 12 = 1 x 1 x 1 x 1 x 2 x 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?

Ideas

The fact that the sum of the “product-sum numbers” was asked by counting only once each number lead me to think that there was some way to test wether a number is a “product-sum” easily.

Though it was quite easy to prove that prime numbers cannot be product sum numbers, other criterions were not that obvious.

12000 did not seem to be that far for a naive approach : for each number, find the first product-sum number following it.

For this, only a test “is this number a sum product number for k terms” was needed. The simplest way to perform it simply was to enumerate all the possible ways to write an integer as a product of integers (different from 1).

``````let enumerate_products n =
let rec aux k i acc =
if i == k then [i::acc]
else if i > k then []
else
if k mod i == 0 then
(aux (k/i) i (i::acc))@(aux k (i+1) acc)
else (aux k (i+1) acc)
in
aux n 2 []
``````

Testing is now easy:

``````let is_sum_product n k =
if is_prime n then
false
else
let product_representations = enumerate_products n in

let pseudo_sum product_representation =
(sum_list product_representation) + k - (List.length product_representation) in

List.exists (fun x -> (pseudo_sum x) == n) product_representations
``````

Using the fact that a number n, decomposed in k factors needs to be bigger than k and smaller than 2k in order to be a product sum, finding the next product-sum number is easy:

``````let find_smallest_sum_product k =
let rec aux i =
if i > 2*k then
failwith "error somewhere"
else if is_sum_product i k then i
else aux (succ i) in
aux (succ k) (* would not work for n=k=1... *)
``````

A simple solution

The whole code to find the solution is the following. With ocamlopt, it took me around 3 minutes on a laptop.

``````let is_prime n =
let rec is_not_divisor d =
d * d > n || (n mod d <> 0 && is_not_divisor (d+1)) in
n <> 1 && is_not_divisor 2

let sum_list input_list =
List.fold_right (fun x y -> x + y) input_list 0

let enumerate_products n =
let rec aux k i acc =
if i == k then [i::acc]
else if i > k then []
else
if k mod i == 0 then
(aux (k/i) i (i::acc))@(aux k (i+1) acc)
else (aux k (i+1) acc)
in
aux n 2 []

let is_sum_product n k =
if is_prime n then
false
else
let product_representations = enumerate_products n in

let pseudo_sum product_representation =
(sum_list product_representation) + k - (List.length product_representation) in

List.exists (fun x -> (pseudo_sum x) == n) product_representations

let find_smallest_sum_product k =
let rec aux i =
if i > 2*k then
failwith "error somewhere"
else if is_sum_product i k then i
else aux (succ i) in
aux (succ k) (* would not work for n=k=1... *)

let sum_sum_product a b =
let integer_interval = List.init (b-a+1) (fun i -> i+a) in
let sum_products = List.map find_smallest_sum_product integer_interval in
let unique_sum_products = List.sort_uniq compare sum_products in
sum_list unique_sum_products ;;

(* Unit testing *)
assert (sum_sum_product 2 12 == 61);

(* Result *)
print_int (sum_sum_product 2 12000);
print_string "\n";
``````

More problems

If you like this kind of problems, I strongly recommend The Art of Mathematics: Coffee Time in Memphis, by Béla Bollobás.

To find out more about OCaml this book provides a detailed presentation of the language.

Best books on Fermat's last theorem

I haven't published many articles these days, the main reason being that I got attracted into the history of Fermat's last theorem. This ...… Continue reading

Benchmark Fossil Demand Forecasting Challenge

Published on July 23, 2022

Random number generation in Cython

Published on February 25, 2022