Implementing cauchy sequences

I have decided to work on constructing some of the computable numbers using cauchy sequences. Generally, this is as simple as mapping over the counting numbers. Here is a construction of e:

(def e
 (map
  (fn [i]
    (apply + (map (comp / factorial) (range i))))
  (range)))

You can evaluate this sequence into:

(0 1 2 5/2 8/3 65/24 163/60 1957/720 ...)

In this way we will provide us with an approximation for e. Here are some additional sequences:

(def pi
 (infinite-series
  (fn [n]
    (/ (* 4 (Math/pow -1 n))
       (+ (* 2 n) 1)))))

(def golden-ratio
 (map
  (fn [i]
    (/ (nth fib (inc i))
       (nth fib i)))
  (rest (range))))

These should make for relatively good approximations of these irrational numbers.

Antireduce

Antireduce is an useful function in sequence pattern recognition. Antireduce takes a binary operation (usually the inverse of some other binary operation) and returns the result of applying it across a sequence of values:

(defn antireduce
  [op coll]

  (map
   (fn [i]
     (if (= i 0)
       (first coll)
       (op (nth coll i) (nth coll (dec i)))))
   (range (count coll))))

For example, we can apply this function to the triangular-numbers:

(= (take 4 (iterate (partial antireduce -) 
  [0 1 3 6 10 15 21 28 36 45])
  
  (0 1 3 6 10 15 21 28 36 45)
  (0 1 2 3 4 5 6 7 8 9)
  (0 1 1 1 1 1 1 1 1 1)
  (0 1 0 0 0 0 0 0 0 0))

Alternatively, we can use this on the factorial function by using the higher inverse-hyper-operator, division.

(= (take 2 (iterate (partial antireduce /) 
  [1 1 2 6 24 120 720 5040 40320 362880]))

  (1 1 2 6 24 120 720 5040 40320 362880)
  (1 1 2 3 4 5 6 7 8 9))

The antireduce function itself can be reversed:

(defn reducify
   [op coll]

   (map
    (fn [i]
      (reduce op (map (partial nth coll) (range (inc i)))))
    (range (count coll))))

This function should allow us to automatically recognise some basically sequences.

Cauchy sequences and intervals

The counting numbers are fundamental to all of computation. Using collections of counting numbers we can construct more complex objects, for example, the rational numbers can be constructed with three counting numbers: a numerator, a denominator, and a sign.

The rational numbers allow us to effectively confront most challenges; however, there are some numbers, known as the irrational numbers, in which can never be expressed as rational numbers. Just as you can never express infinity because there is always a greater number, there is always a greater rational approximation for any irrational number. Such values that can never be expressed because they always have another step that can always bring them closer to a target point are the convergence value of a cauchy sequence.

For example, one of the first irrational numbers discovered was the square root of two, which can be expressed in terms of the following cauchy sequence:

$$\sqrt{2} = \sum _{n = 0}^{\infty} {(-1)^{n + 1} \frac{(2n-3)!!}{(2n)!!}}$$

Most other popular irrational numbers like e, pi, or the golden ratio can be expressed in terms of cauchy sequences:

$$e = \sum _{n=0}^{\infty} {\frac{1}{n!}}$$
$$\pi = 4 \sum _{n=0}^{\infty} {\frac{(-1)^n}{2n+1}}$$
$$\varphi = [1; \overline{1}]$$

Although we can never acquire any of these values, we can approximate them in terms of intervals. For example, we know pi is in the interval between 3 and 4, and as we use our cauchy sequence we progressively narrow that range. Once we have constructed intervals, we are going to want to perform some operations on them, leading to interval arithmetic. These same methods approximation can be used for physical measurements.

Nested upto

A simple upto function might look like this:

(defn upto
  "Get the numbers from 1 to n."
  [n]

  (range 1 (inc n)))

This can be extended to a nested upto function:

(defn nested-upto
  "Compute the numbers upto n nested by k."
  [n k]

  (cond
   (= k 0) 1
   (= k 1) n   
   :else (map #(nested-upto % (dec k)) (range 1 (inc n)))))

Here is upto 5 at different levels of nesting to show what I mean:

(1 2 3 4 5)

((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5))

(((1))
 ((1) (1 2))
 ((1) (1 2) (1 2 3))
 ((1) (1 2) (1 2 3) (1 2 3 4))
 ((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5)))

The multichoose function I talked about previously can now be implemented using nested ranges:

(defn multichoose
  [n k]
  (apply + (flatten (list (nested-upto n k)))))

This demonstrates this basic mathematical principle.

Factorials and triangular numbers

These two functions are:

$$T_n = \sum_{i=1}^n {i}$$
$$n! = \prod_{i=1}^n {i}$$

There are also raising and falling versions of the factorial:

$$x^{\overline n} = \prod_{i=0}^n {x+i}$$
$$x^{\underline n} = \prod_{i=0}^n {x-i}$$

Here is the corresponding code:

(def triangular-number 
  (let [sum (partial apply +)]
    (comp sum range inc)))

(def factorial
  (let [product (partial apply *)
        upto (comp (partial map inc) range)]
    (comp product upto)))

(defn rising-factorial
  [x n]
  (apply * (map (partial + x) (range 0 n))))

(defn falling-factorial 
  [x n]
  (apply * (map (partial - x) (range 0 n))))

(defn choose
  [n k]
  (/ (falling-factorial n k)
     (factorial k)))

(defn multichoose 
  [n k]
  (/ (rising-factorial n k)
     (factorial k)))

The multichoose function is incredibly important because all polytopic numbers, including triangular-numbers and tetrahedral numbers can be expressed with it.

(def triangular-number
  #(multichoose % 2))

(def tetrahedral-number
  #(multichoose % 3))

(def pentatope-number
  #(multichoose % 4))

This is the relationship between factorials and triangular-numbers. Triangular-numbers can be expressed in terms of factorials probably because the higher hyper operator, multiplication, encodes more information then addition.