We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or register
to publish this job!

Login or register
to save this job!

Login or register
to save interesting jobs!

Login or register
to get access to all your job applications!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel ๐Ÿš€.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Login or register
to save articles!

Login to see the application

Engineers who find a new job through Functional Works average a 15% increase in salary ๐Ÿš€

You will be redirected back to this page right after signin

Blog hero image

A Trivial Mathematical Problem

Adeel Ansari 21 March, 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.

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?

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

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.

Author's avatar
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.

Related Issues

open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Started
  • 0
  • 16
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Started
  • 0
  • 5
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Started
  • 0
  • 5
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Started
  • 0
  • 7
  • Intermediate
  • HTML

Get hired!

Sign up now and apply for roles at companies that interest you.

Engineers who find a new job through Functional Works average a 15% increase in salary.

Start with GitHubStart with Stack OverflowStart with Email