Adeel Ansari
15 Jun 2023
•
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 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)
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.
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
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!