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.