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.

Python plot 3d scatter and density

It is often easy to compare, in dimension one, an histogram and the underlying density. This is quite useful when one want to visually ev...… Continue reading

Best casual readings in mathematics

Published on May 03, 2020

LightGBM on the GPU

Published on April 29, 2020