We're planting a tree for every job application! Click here to learn more
GolangWorks

A Trivial Mathematical Problem

Adeel Ansari

21 Mar 2022

5 min read

A Trivial Mathematical Problem
  • Lisp
  • Java
  • Mathematics
  • Functional Programming
  • 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);
   ...>             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)

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.

Did you like this article?

Adeel Ansari

I'm fond of harmony, symmetry, precision, eloquence, moderation, and simplicity; but do understand that not all are possible, neither desirable, everywhere – not quite all the time.

See other articles by Adeel

Related jobs

Title

The company

title

Remote

Title

The company

title

Remote

Title

The company

title

Remote

Title

The company

title

Remote

Related articles

title

title

title

title

CareersCompaniesSitemapFunctional WorksBlockchain WorksJavaScript WorksAI WorksGolang WorksJava WorksPython WorksRemote Works
email iconhello@works-hub.comUK flag

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

US flag

108 E 16th Street, New York, NY 10003

Subscribe to our newsletter

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

© 2021 WorksHub

Privacy PolicyDeveloped by WorksHub