Sudoku

In the last few years, Sudoku has grown to rival crossword puzzles in popularity.

 

A Sudoku puzzle consists of a 9x9 grid with nine 3x3 mini-grids.   The 81 boxes need to be filled in with the digits from 1 to 9.  The trick is that all 9 numbers must be used once and only once in each row, column, and mini-grid.  A few of the numbers will already be filled in for you.

 

Sudoku is pure logic - there are no calculations involved.

 

In future posts, we will look at some specific Sudoku situations, and how to solve them logically.

 

If you want to do a Sudoku puzzle, there is an on-line Sudoku site that prints two free puzzles daily.   You can print them out and play.

 

Also, Sudoku is available in all the major newspapers and in lots of books.  I even got an electronic Sudoku device as a gift.

 

Amazon has a lot of Sudoku merchandise.

Using Awk to Find Average Annual Interest Rate

In a previous Unix blog post, I gave two awk scripts for calculating compound interest.

 

Now, let us look at the opposite problem.  If we have a starting amount and ending amount, after X number of time periods, what is the average interest rate per time period?  We can use awk.

 

For example, If we started with $4000, and had $5200 after 6 years, what interest rate did we average per year?

 

We can use:

 

nawk 'BEGIN {print (5200/4000)^(1/6)}'

 

to get an answer of 1.0447.  So, we made about 4.5% a year for 6 years.

 

In this case, we are using the math principle that raising something to 1/N is like taking the Nth root.

 

So, 4000* 1.0447^6 = 5200.

 

This is covered in my powers and roots post on my math and logic blog.

Logrithms and Exponentials, Part 2

Previously, I introduced powers and roots, and then introduced logrithms and exponentials.

 

Now, we will tie them together. 

 

Logs and exponents used to be valuable in the days before computers and calculators because the log function turns powers/roots into multiplication and division.

 

l( x^y) = y * l(x)  and l( x^(1/y) ) =  l(x) / y

 

So, for example, if you want to solve 4^100, you can do e( l(4^100) ) instead.

This becomes e( 100 * l(4) ).

 

The square root of 9 is 9^(1/2) = e( l(9)/2).

 

In the old days, engineers and scientists could use these techniques, along with slide rules and log tables, to solve engineering problems.

 

Today, I sometimes use this technique when I want to take roots using the unix basic calculator program. Usually, I use awk, which can do ^(1/X).

Logrithms and exponentials, Part 1

In my last post, I introduced powers and roots. 

 

For example, 3^2 = 3*3 = 9 and 9^(1/2) = 3

 

Now, let us look at logrithms (logs) and exponentials.  These are opposing functions. One undoes the other.  For example, if we call the log function l() and the exponent function e(), then l(e(X)) = X and e(l(X)) = X

 

When we deal with logs/exponents, we usually deal with two bases, either base 10 or base e (which is a constant defined as 2.71828182845904523536...).  Base e is also called natural logs.

 

If we use base 10, then l() would return the power that we need to raise 10 to to get the number.  For example, l(100) would be 2, because 10^2 = 100. The e() function would raise 10 to the power of the number.  for example, e(2) = 10^2 = 100.

 

So, e(l(100)) = e(2) = 10^2 = 100

and l(e(100)) = l(10^100) = 100  because you need to raise 10 to the 100 power to get 10^100.

 

If we use base e, then l() would return the power needed to raise e (2.718..) to get the number.  The e() function would raise e (2.718...) to the power of the number.

 

So, l(3)  = 1.0986 because 2.718^1.0986 = 3

      e(3) = 20.0855, because 2.718^3 = 20.0855

(note that in the two examples we used 2.718, but that is just rounding e).

 

Base 10 is more convenient to humans, but e (2.718...) is called the natural log because the constant occurs in nature.  In the future, we will use base e when dealing with logs/exponents.

 

 

 

 

 

Introduction to Powers and Roots

Raising a number to a power P means multiplying the number by itself P times.

It is usually denoted with the symbol ^ or **.

 

For example,

        3^0 = 1

        3^1 = 3 = 3

        3^2 = 3*3 = 9

        3^3 = 3 * 3 * 3 = 27

        3^4 = 3 * 3 * 3 * 3 = 81

 

Raising any number to 0 is always defined as 1.

When you use ^2 it is called squaring, and ^3 is calling cubing.

 

 

The opposite function is called finding the root.  It means taking a number n and a root r, and returning the number that, if raised to power r, will give n.  The symbol is hard to show on the computer, so, for a moment, we will just call it rootr().

 

For example,

         root1(3) = 3

         root2(9) = 3

         root3(27) = 3

         root4(81) = 3

 

Now, just like subtraction is adding a negative number, and dividing is multiplying a fraction, roots can be expressed as raising to a fractional power.

 

So,

       3^(1/1) = 3  because 3^1 = 3

       9^(1/2) = 3    because 3^2 = 9

       27^(1/3) = 3  because 3^3 = 27

       81^(1/4) = 3  because 3^4 = 81

      

Adding Up a Consecutive Range of Integers

In the last post, I described a formula for calculating the sum of integers 1 to N.

 

Now, let's derive a formula for the more general case of summing the integers from M to N, where M <= N.

 

Well, we can write the Sum of M to N as: Sum(M,N) = Sum(1,N)  - Sum(1, M-1)

So, for example, the sum of 5-6 would be the sum from 1-6 minus the sum from 1-4.

 

We know that the Sum(1,N) would be N*(N+1)/2.  The Sum(1,M) would be M*(M+1)/2.

Then, the Sum(1,M-1) would be (M-1)*(M-1+1)/2, which simplifies to (M-1)*M/2, or

M*(M-1)/2.

 

Thus, the Sum(M,N) would be N*(N+1)/2 - M*(M-1)/2

 

So, the sum of 5-6 would be  6*7/2 - 5*4/2 = 21 - 10 = 11

 

Now, we can calculate the sum of any series of consecutive integers - even 5 to 10 million - in one step.

 

This is an example of simple elegance over brute force.

Summing Consecutive Integers

A neat fact is that the sum of integers from 1 to N is equal to N * (N+1) / 2.

 

So, for example, 1+2+3+4+5 is equal to 5*6/2, which is 15.

 

This fact is really useful if you want to sum huge strings of consecutive numbers, because no matter how many numbers you have, this formula will give you the answer in one calculation.

 

So, if you actually added up the integers from 1 to 10,000 it would require 10,000 additions.  But, you can easily calculate the sum with one calculation: 10000*10001 / 2. which equals 50,005,000.

 

Thus, a programmer who codes the formula, instead of using brute force addition, would create a program that would run instantaneously, even for adding up millions of integers.

Here is an awk script for summing the integers, which I posted on my unix blog.