# A Trivial Mathematical Problem

21 Mar 2022 • Clojure

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 analyse 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);
...>         }
...>         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);
...>         }
...>         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);
...>         }
...>         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);
...>         }
...>         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);
...>             }
...>         }
...>         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, https://practical.li/clojure/reference/clojure-syntax/ratios.html. 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 idea, I know; but possible.

Im fnd of hrmny, symtry, prcsion, elqunce, modrtion and smplcty; bt do undrstnd tht nt all are pssbl, neithr dsirbl, everywhere – nt quite all the time.

Related jobs

See all

### WorksHub

CareersCompaniesSitemapFunctional WorksBlockchain WorksJavaScript WorksAI WorksGolang WorksJava WorksPython WorksRemote Works

### Locations hello@works-hub.com Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ 108 E 16th Street, New York, NY 10003