Consecutive odd primed integers

A few years ago, for some reason (I don’t remember exactly what it was) I thought of the following problem and tackled around a solution for it:

Prove that the triplet $(3, 5, 7)$ is the only triplet of consecutive odd integers such that all integers in it are primes.

In other words, prove that $\exists! n \in N (2n + 1, 2n + 3, 2n + 5)$ are primes.

We already know if we set $n = 1$ that we get the triplet $(3, 5, 7)$ , but as for the part of proving that this is unique, we need to show that at least one member of the triplet is divisible by 3. So, for example, for $n = 3$ we have $(7, 9, 11)$ , and 9 is not a prime because it’s divisible by 3.

We can use induction on n. The base case is already there for $n = 1$ , so for the inductive step we can assume that either of the members is divisible by 3 (but not the remaining). Now assuming one of the members in $(2n + 1, 2n + 3, 2n + 5)$ is divisible by 3, we need to show that one of the members in $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.

From here, we have 3 cases:

$2n + 1$ is divisible by 3. Then, so is $2n + 4$ , and $2n + 7$ , thus one of $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.
$2n + 3$ is divisible by 3. Thus one of $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.
$2n + 5$ is divisible by 3. Thus one of $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.

So, since at least one member of $(2n + 1, 2n + 3, 2n + 5)$ is divisible by 3, but only 3 is a prime (and not multiples of 3 of course), we get that $(3, 5, 7)$ is the only triplet of consecutive odd integers such that all members are prime.

Proof of the binomial theorem

While working on How To Prove It, I found this in the exercises.
To me, the binomial formula is really trivial, but it’s an interesting thing to prove because it requires manipulating summations and some algebra tricks. So let’s get started.

Prove that for all real number x and y, and every natural n:
$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k$
We will use mathematical induction on n.

Base case:
$n = 0: (x+y)^0 = 1 = {0 \choose 0} x^0 y^0$

Inductive hypothesis:
Assume that the formula holds for $n = j$ :
$(x+y)^j = \sum_{k=0}^{j} {j \choose k} x^{j-k} y^k$

Using this identity we need to show that it also holds for $n = j + 1$ .

Multiply both sides of the inductive hypothesis by $x + y$ :
$(x+y)^{j+1} = (x+y)\sum_{k=0}^{j} {j \choose k} x^{j-k} y^k$

Now we can split the summation like so:
$(x+y)^{j+1} = \sum_{k=0}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j} {j \choose k} x^{j-k+1} y^{k+1}$

Consume the first element of the first summation:
$(x+y)^{j+1} = x^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j} {j \choose k} x^{j-k} y^{k+1}$

Consume the last element of second summation:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j-1} {j \choose k} x^{j-k} y^{k+1}$

Shift the bounds of the second summation to match the first:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=1}^{j} {j \choose {k-1}} x^{j-k+1} y^k$

From here, we can factor the same elements:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} [x^{j-k+1} y^k] ({j \choose k} + {j \choose k-1})$

We will use the identity ${j \choose k} + {j \choose {k - 1}} = {{j + 1} \choose k}$ to simplify:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {{j + 1} \choose k} [x^{j-k+1} y^k]$

Note that ${{j + 1} \choose 0} x^{j + 1} y^0 = x^{j+1}$ , so we can insert first element of first summation back into the summation by setting lower bound to 0:
$(x+y)^{j+1} = y^{j+1} + \sum_{k=0}^{j} {{j + 1} \choose k} [x^{j-k+1} y^k]$

Apply similar reasoning for the upper bound to move $y^{j+1}$ inside the summation:
$(x+y)^{j+1} = \sum_{k=0}^{j + 1} {{j + 1} \choose k} [x^{j-k+1} y^k]$

Now, by setting $m = j + 1$ we get the induction hypothesis, thus the identity is proven.

…and in JavaScript, using Sweet.js

This post is a continuation of my previous post, Capturing abstractions in Lisp.

Today I was playing with Sweet.JS, a JavaScript library that adds the possibility to make macros within the language.

I went through the tutorial and it is pretty straight-forward.

// delay needs to be a macro in order for the code to work correctly.
// Otherwise the invocation of delay will evaluate all its arguments eagerly.
syntax delay = function (ctx) {
    let x = ctx.next().value;
    return #`(function() { return ${x} })`;
}

// similarly for cons-stream
syntax cons_stream = function(ctx) {
    const [...args] = ctx.next().value.inner();

    let param1 = args[0];
    let param2 = args.slice(2);

    return #`([${param1}].concat(delay(${param2})))`;
}

// force just evaluates
function force(x) {
    return x();
}

function next_integer(x) {
    return cons_stream(x, next_integer(x+1));
}

function all_positive_integers() {
    return next_integer(0);
}

function integer_ref(list, j) {
    if (j == 0) {
        return list[0];
    } else {
        return integer_ref(force(list[1]), j - 1);
    }
}

var integers = all_positive_integers();
// display 100th number:
console.log(integer_ref(integers, 100));

With this code snippet, we can see that using this library we get a very powerful Lisp-like syntax 🙂

Capturing abstractions in Lisp

I was skimming through SICP (after a pause) and I came across the chapter where Streams are discussed.

For those that have experience with JS Promises, Streams can be thought of as Promises. They allow us to make an illusion of infinity, e.g. all positive integers, by deferring evaluation.

For example, to generate all positive integers, we make a pair (1, next_int(1)), and then to evaluate the second member of that pair is (2, next_int(2)) and so on, for the nth number producing a list (1, (2, (…, (n, next_int(n))))) which will do n evaluations.

Here’s an implementation in Scheme that defines cons-stream (which will allow us to produce promises) and uses that to generate all integers infinitely (but not really, since all it does is just defer evaluation).

; delay needs to be a macro in order for the code to work correctly.
; Otherwise the invocation of delay will evaluate all its arguments eagerly.
(define-syntax delay
  (syntax-rules ()
    ((delay a)
     (lambda () a))))
; (defmacro delay (a) `(lambda () ,a))

; similarly for cons-stream
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
      (cons a (delay b)))))
; (defmacro cons-stream (a b) `(cons ,a (delay ,b)))

; force just evaluates
(define (force a) (a))

(define (next-integer x) (cons-stream x (next-integer (+ x 1))))

(define all-positive-integers (next-integer 0))

(define (integer-ref list i)
  (cond ((= i 0) (car list))
    (else (integer-ref (force (cdr list)) (- i 1)))))

; display 100th number:
(integer-ref all-positive-integers 100)

Looks and works pretty good!

Now, we can try doing the same in JS:

function force(x) {
    return x();
}
function cons_stream(a) {
    return function(b, c) {
        // this is delay basically but we can't abstract it in another method
        // since it will evaluate the params, so we need to use scope
        return function() {
            return [a].concat(b(c));
        }
    }
}

function next_integer(x) {
    return cons_stream(x)(next_integer, x+1);
}

function positive_integers() {
    return next_integer(0);
}

function integer_ref(list, j) {
    var item;

    // evaluate initially
    list = force(list);

    while (j != 0) {
        // get the last item from the list (promise)
        item = list.pop();

        // append it in its evaluated form
        list = list.concat(force(item));

        j--;
    }

    // exclude last item since it's a new promise
    return list[list.length - 2];
}

var all_positive_integers = positive_integers();

// display 100th number:
console.log(integer_ref(all_positive_integers, 100));

The code is a bit longer, but it works equally good.

In JS we can achieve the same effect that the Lisp macro does by using scopes.

But in my opinion, Lisp’s syntax is more powerful with the ability to not evaluate parameters because it allows us to capture abstractions such as delay, whereas in JS we couldn’t do the same.

Closed-form expression of a recursive function

Let’s suppose, for the funs, that you go to the store and suddenly the manager tells you “For every 2 pieces of milk, you get 1 bonus.”

So you stop and think.
For 2 pieces, you end up having 3.
For 4 pieces, you end up having 2 as a bonus, and another one from that bonus 2 makes 4 + 2 + 1 = 7.
For 8 pieces, you end up having 4 as a bonus, and 2 from the bonus 4 and additional 1 from the bonus 2 makes 8 + 4 + 2 + 1 = 15.
You say, a great deal!

Note here that we don’t discuss the case where you don’t get bonus from the bonuses as that’s not hard to calculate.

Now let’s abstract “For every k pieces, you get 1 bonus” and we can start working our way to a closed-form expression.

This was my first attempt to solve it using recursion:

function calc(n, k) {
    if (n < k) {
        return n;
    }
    return n + calc(n / k, k);
}

Cool, let’s give that a try:

> calc(2, 2)
3
> calc(4, 2)
7
> calc(6, 2)
10.5

Seems to be working as expected.

In understanding what that does, let’s try to expand the first few terms manually.
n + (n/k) + (n/k)/k + ((n/k)/k)/k + … = n + n/k + n/k^2 + n/k^3 + … = s
This will proceed until one of the terms is less than k.
Then I went ahead and created a function that calculates the summation (using n/k as upper bound, which seems to be good enough):

/* This function represents the following summation
n/k
Σ n/k^i
i=0

*/
function calc2(n, k) {
    var sum = 0;
    var i;

    for (i = 0; i < n / k; i++) {
        sum += n / Math.pow(k, i);
    }

    return sum;
}

The next thing I did was run a delta check on various ranges to calculate abs(calc – calc2). It was 0.00015 after a few iterations, so seems good.
Now if we multiply s by (k – 1) we get s(k – 1) = nk – n + n – (n/k) + (n/k) + … which follows that s = nk/(k – 1). Note that I used infinity as the upper bound, as in the long run this wouldn’t matter much. It might be a little off for the first values, but eventually it should converge.

function calc3(n, k) {
    return n * k / (k - 1);
}

One thing to note is that the lesser k, the better. Otherwise, the limit as k -> Infinity is equal to just n.
If we now instantiate k to 2, we get n * 2, which means that you pay the milk at 50% discount (in the long run), which is a really good thing!