Property of squares

Consider the following task:
Print the first 100 squares using at most one loop. The constraints are that you are not allowed to use multiplication or functions.

To tackle this one, we will have to use one interesting property of the squares that I noticed while taking my kid to school. At the school, there was a table with all natural numbers listed from 1 to 100. While looking at it, I noticed the distances between the squares kept increasing by 2k + 1 for every kth square.

So for example, from 1 to 4 (the first square), the distance is 3. Since this is the first square, k = 1 so 2*1 + 1 = 3. The distance from 4 to 9 (the second square) is 5. Since this is the second square, k = 2 so 2*2 + 1 = 5. And so on.

Naturally I tried to generalize this and came to the following recurrent relation:

n_0 = 1
n_k = n_{k - 1} + 2k + 1

Before we use this relation in our program, we will first prove its correctness.

We will prove that n_k = (k + 1)^2 by induction.

The base case is k = 0: n_0 = 1 = 1^2 which is true. Now, we assume that n_k = (k + 1)^2. If we add 2k + 3 to both sides, we get n_{k + 1} = n_k + 2k + 3 = (k + 1)^2 + 2k + 3 = k^2 + 4k + 4 = (k + 2)^2. Thus the identity is proven.

Now, here is our simple program:

var s = 1;
for (var i = 1; i <= 100; i++) {
    console.log(s);
    s += i + i + 1;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s