Project Euler 88

Reading time ~4 minutes

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.

How to optimize PyTorch code ?

Optimizing some deep learning code may seem quite complicated. After all, [PyTorch](https://pytorch.org/) is already super optimized so w...… Continue reading

Acronyms of deep learning

Published on March 10, 2024

AI with OCaml : the tic tac toe game

Published on September 24, 2023