A Trivial Mathematical Problem

I came across a mathematical problem, related to Number Theory, while leisurely browsing maths and programming related stuff. So, I just thought why not try to solve it using Clojure — in the hope that, this way I would be able to brush up my knowledge of both, Clojure and Number Theory. Here I would like to share, how did that go, and the outcomes.

Statement

For every fraction of the form 1/n (where n is a positive integer), one can always find a pair of two positive integers, p and q, such that:

1/n = 1/p + 1/q

There could be one or more pairs of this sort, fitting the above equation.

Example

Given n = 2

1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4

Problem Statement

Could you list out all these equations for a given n?

Solution

Let's take the equation,

1/n = 1/p + 1/q

and try to solve it for q,

1/n - 1/p = 1/p + 1/q - 1/p
1/q = 1/n - 1/p
1/q = (p - n)/np
q = np/(p -n)

where p > n.

Now, it's easy, we just need to put p, incrementally, in order to find q. But the question is, where should we stop? We must stop somewhere; after all, there are not infinitely many such pairs. So, to answer that question we analize the example given, where n = 2

1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4

If we notice, we may see that we should stop when p > 2n. Going beyond that would either reverse the values of p and q; i.e., for p = 3, q will be 6, and, for p = 6, q will be 3; or q will not be an integer — though, I can't prove the latter, as of now. Anyway, now we may proceed with the code.

If one is coming from an imperative language, say Java, one might think of looping p, incrementally, as such:

jshell>         int n = 2;
   ...>         List<List<Integer>> pairs = new ArrayList<>();
   ...>         for (int p = n + 1; p <= (n * 2); p++) {
   ...>             int q = (n * p) / (p - n);
   ...>             pairs.add(List.of(p, q));
   ...>         }
   ...>         System.out.println(pairs);
   ...>
n ==> 2
pairs ==> []
[[3, 6], [4, 4]]

Great! Let's test if the numbers are correct.

jshell>         int n = 2;
   ...>         List<List<Integer>> pairs = new ArrayList<>();
   ...>         for (int p = n + 1; p <= (n * 2); p++) {
   ...>             int q = (n * p) / (p - n);
   ...>             pairs.add(List.of(p, q));
   ...>         }
   ...>         System.out.println(pairs);
   ...>
   ...>         List<Double> results = new ArrayList<>();
   ...>         for (var pair : pairs) {
   ...>             results.add((1 / ((double) pair.get(0)) + 1 / ((double) pair.get(1))));
   ...>         }
   ...>         System.out.println(results);
   ...>
n ==> 2
pairs ==> []
[[3, 6], [4, 4]]
results ==> []
[0.5, 0.5]

Brilliant! Now, we try another number for n, say 3.

jshell>         int n = 3;
   ...>         List<List<Integer>> pairs = new ArrayList<>();
   ...>         for (int p = n + 1; p <= (n * 2); p++) {
   ...>             int q = (n * p) / (p - n);
   ...>             pairs.add(List.of(p, q));
   ...>         }
   ...>         System.out.println(pairs);
   ...>
   ...>         List<Double> results = new ArrayList<>();
   ...>         for (var pair : pairs) {
   ...>             results.add((1 / ((double) pair.get(0)) + 1 / ((double) pair.get(1))));
   ...>         }
   ...>         System.out.println(results);
   ...>
n ==> 3
pairs ==> []
[[4, 12], [5, 7], [6, 6]]
results ==> []
[0.3333333333333333, 0.34285714285714286, 0.3333333333333333]

Oops! There is something wrong with the pair, [5, 7]; but the maths is right, so, there must be something wrong with the code. What if the q, for p = 5, is rather a ratio. Let's find out.

jshell>         double n = 3D;
   ...>         List<List<Double>> pairs = new ArrayList<>();
   ...>         for (double p = n + 1; p <= (n * 2); p++) {
   ...>             double q = (n * p) / (p - n);
   ...>             pairs.add(List.of(p, q));
   ...>         }
   ...>         System.out.println(pairs);
   ...>
   ...>         List<Double> results = new ArrayList<>();
   ...>         for (var pair : pairs) {
   ...>             results.add((1 / pair.get(0) + 1 / ((double) pair.get(1))));
   ...>         }
   ...>         System.out.println(results);
   ...>
n ==> 3.0
pairs ==> []
[[4.0, 12.0], [5.0, 7.5], [6.0, 6.0]]
results ==> []
[0.3333333333333333, 0.33333333333333337, 0.3333333333333333]

Indeed, as we can see, it's supposed to be 7.5, instead of 7; now, the results are also correct. But we are only interested in integer values of q. So, we must filter those decimal values out.

jshell>         int n = 3;
   ...>         List<List<Integer>> pairs = new ArrayList<>();
   ...>         for (int p = n + 1; p <= (n * 2); p++) {
   ...>             if (((n * p) % (p - n)) == 0) {
   ...>                 int q = (n * p) / (p - n);
   ...>                 pairs.add(List.of(p, q));
   ...>             }
   ...>         }
   ...>         System.out.println(pairs);
   ...>
   ...>         List<Double> results = new ArrayList<>();
   ...>         for (var pair : pairs) {
   ...>             results.add((1 / ((double) pair.get(0)) + 1 / ((double) pair.get(1))));
   ...>         }
   ...>         System.out.println(results);
   ...>
n ==> 3
pairs ==> []
[[4, 12], [6, 6]]
results ==> []
[0.3333333333333333, 0.3333333333333333]

Great! Now, we try to implement the solution in Clojure. Let's start with translating the Java code, as closely as possible.

user=> (let [n 3]
         (loop [p (inc n)
                pairs []]
           (if (<= p (* 2 n))
             (recur (inc p) (conj pairs [p (/ (* n p) (- p n))]))
             pairs)))
[[4 12] [5 15/2] [6 6]]

Oh, we missed the condition to filter out q, where q is a ratio. Don't worry, we can do fix that; but notice that instead of a decimal we got a ratio. What? Try this,

user=> (class 1/2)
clojure.lang.Ratio

Ooo! So, we have a Ratio class. For more insight, read about ratios. Now, we continue fixing that,

user=> (let [n 3]
         (loop [p (inc n)
                pairs []]
           (if (<= p (* 2 n))
             (let [q (/ (* n p) (- p n))]
               (if (ratio? q)
                 (recur (inc p) pairs)
                 (recur (inc p) (conj pairs [p (/ (* n p) (- p n))]))))
             pairs)))
[[4 12] [6 6]]

Good! Now, let's make it a little idiomatic.

user=> (let [n 3]
         (for [p (range (inc n) (inc (* n 2)))
               :let [q (/ (* n p) (- p n))]
               :when (not (ratio? q))]
           [p q]))
([4 12] [6 6])

Here is the doc for, range, and for. Is that it? No… Let's see if there is another way, maybe better, or at least shorter.

user=> (let [n 3]
         (->> (range (inc n) (inc (* 2 n)))
              (map #(vector % (/ (* n %) (- % n))))
              (filter #(not (ratio? (last %))))))
([4 12] [6 6])

Nah! Not really. The former was perfectly fine. However, we see some interesting functions here; among the notable ones, we have, map, filter, and ->>, a threading macro.

Let's not end here. Let's take the solution, the one using (for ...), and try to return the reciprocals, instead, like so,

user=> (let [n 3]
         (for [p (range (inc n) (inc (* n 2)))
               :let [q (/ (* n p) (- p n))]
               :when (not (ratio? q))]
           [(/ 1 p) (/ 1 q)]))
([1/4 1/12] [1/6 1/6])

Now, we can easily sum it up, to get 1/3 for each pair.

user=> (let [n 3
             pairs (for [p (range (inc n) (inc (* n 2)))
                         :let [q (/ (* n p) (- p n))]
                         :when (not (ratio? q))]
                     [(/ 1 p) (/ 1 q)])]
         (map #(+ (first %) (last %)) pairs))
(1/3 1/3)

End Note

After running the code with several values for n, I noticed, that for prime numbers, such pairs are always 2. So, we can implement a function, say prime? using the code like so,

user=> (defn prime? [n]
         (= 2 (count (for [p (range (inc n) (inc (* n 2)))
                           :let [q (/ (* n p) (- p n))]
                           :when (not (ratio? q))]
                       [p q]))))
#'user/prime?
user=> (prime? 4988959)
true
user=> (prime? 4988957)
false

Not a very good idea, I know; but possible.