Adeel Ansari

21 Mar 2022

â€¢

5 min read

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.

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.

Given `n = 2`

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

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

?

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);
...> 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, 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)
```

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.

Did you like this article?

Adeel Ansari

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.

See other articles by Adeel

hello@works-hub.com

Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ

108 E 16th Street, New York, NY 10003

Join over 111,000 others and get access to exclusive content, job opportunities and more!