Greetings mathfactorisers!  I am one of the new wave of additional commentators on the website.  I thought I would introduce myself a little.  I am currently working as a postdoc researcher at Imperial College London, though I am also polishing my CV as my current contract finished in March.  My research is in tilings and patterns, especially those which fit onto themselves at different scales.  For those of you in London next summer I am preparing an exhibit titled “How shapes fill space” for the Royal Society Summer exhibition.  This will look at the mathematics of tilings and patterns with lots of shapes and models to play with.I also like to make pretty pictures from this research, like the example below, which is based on a tiling created by the prime mathfactor Chaim himself.   I hope to describe some of this on the mathfactor, for a taste check out my other writing at Maxwell’s demon.  This piece on rep-tiles is probably of particular interest.  For more of my pictures take a look at my website.

Standard Podcast [ 11:50 ] Play Now | Play in Popup | Download

Isaac Newton gave an elegant solution to this problem. Can you?

To understand the question, first consider the square numbers:

1 4 9 16 25 36 49 ….

Below successive squares, write the differences between them. For example, 4 – 1 = 3.

1   4   9   16   25   36   49 ....

  3   5   7    9     11    13 ....

And then repeat:

1   4   9   16   25   36   49 ....

   3   5   7    9     11    13 ....

     2   2   2     2      2  ....

It turns out that for any polynomial p, if we make a table of the values p(1), p(2), etc and take differences, successively, eventually we will have a constant row, and the number of differences we need is exactly the degree of the polynomial. For example, for 2n^3 – n, we have

 1     14      51    124    245  .....

       13   37   73   121 ....

           24   36   48  ....

               12   12 ...

(and all 12’s on this row)

Now for the puzzle!

(A warm up might be to prove the assertion above, that this works at all)

If we have just the front column of the table, we can recover the rest, and in particular, the values on the top row:

2

   1

      7 

Can only be

 
2      3    11    26    48    77 ....

     1      8     15     22  29  ....

          7       7      7     7    7  ...

It’s not too hard to figure out the polynomial that generates the values on the top row…

But more generally, give a simple formula for any polynomial in terms of the values in the first column in any such table!

(BIG WORD OF CAUTION: An elegant formula isn’t necessarily in the fully-multiplied-out form!)

Standard Podcast [ 11:14 ] Play Now | Play in Popup | Download

Pascal’s triangle, with its host of nifty tricks, provides the surprising solution to last weeks’ puzzle on sequences of averages. 

As a bonus puzzle, not mentioned in the podcast, consider the following variation with a completely different solution: Our sequence starts 

1, 1, …

Now each additional term is twice the average of all the earlier terms, not including the terms immediate predecessor! So, the third term is twice the average of 1, i.e. 2. We have now 1,1,2 …

The fourth term is twice the average of 1 & 1, i.e. 2 and we have 1,1,2,2

Continuing in this way we get 1, 1, 2, 2, 8/3, 3, etc.  The sequence wobbles around, but will grow steadily. But the remarkable thing is that the nth term, divided by n, tends to exactly (1 – 1/e^2)/2, a fact well worth trying to prove!

Our favorite new and not-so-new products of 2008!

Standard Podcast [ 17:14 ] Play Now | Play in Popup | Download

Check out these great gifts!

• Zome is an incredibly powerful construction system!
• the great puzzles of Puzzellation (available at Barnes and Nobles)
• The terrific puzzle computer game DROD
• The Magic Mirror Image Coloring Book
• The Riddles of the Sphinx by David J Bodycombe, an amazing compendium of puzzles, of hundreds of kinds, at all levels of difficulty, with historical essays to boot!
• Which leads us to Nikoli, the great Japanese puzzle co! (Rules can be found here)
• The Princeton Companion to Mathematics is a landmark classic. A must-have for every serious student, researcher or amateur.
• How Round is Your Circle just one of the many fantastic titles out on Princeton University Press
• AK Peters is another fantastic press, with a wide range of interesting math and CS titles, including, ahem, the Symmetries of Things.
• Binary Arts/ThinkFun is another source of great puzzles!
• And the authors Martin Gardner and Ivan Moscovitch are always fantastic!

Hope this helps and have fun!! Let us know how it works out!

Happy Holidays from the Math Factor!

Dirk Huylebrouck, the Mathematical Tourist columnist in the Mathematical Intelligencer, tells us about the remarkable Ishango bone, a 22,000 year old arithmetical exercise!

Standard Podcast [ 17:37 ] Play Now | Play in Popup | Download

We should take a moment to explain why,

1) If N is not prime, then 2^N − 1 is not prime either:

If N = a b then

(2^a − 1) × ( 2^0a + ^1a +^2a + …+^(b-1)a )

= 2^{a b} − 1 = 2^N − 1

2) if P=2^p − 1 is prime, then Q = 2^p−1P is perfect:

A number is perfect if it is the sum of all of its proper divisors. The divisors of Q are

1, 2, 2², …, 2^p−1 and P, 2P, 2²P, …, 2^p−1P = Q

Q is perfect if all of these divisors sum to 2Q (Since we’re summing in Q itself, as well as all of the proper divisors of Q)

But this sum is

(1+2+…+2^p−1)+ (1+2+…+2^p−1)P

= (1+2+…+2^p−1)(P+1)

=(2^p-1)(2^p)

= (P) (2 × 2^p−1) = 2Q

3) Now this is a little harder, but not too bad if you follow closely: If an even number N is perfect, then it is of this form!

So, let N be an even perfect number; in particular, then, N = 2ⁿ X for some n≥1 and odd number X.

The divisors of N are all the numbers 2ⁱ x where 0 ≤ i ≤ n and x is a divisor of X .

If we let S be the sum of the divisors of X, then the sum of all of the divisors of N is thus

(2ⁿ⁺¹ − 1) S = 2N

(recalling that N is perfect!)

So

(2ⁿ⁺¹ − 1) S = 2ⁿ⁺¹ X

Since (2ⁿ⁺¹ − 1) is odd, we must have that 2ⁿ⁺¹ divides into S , and so for some q ,

S = 2ⁿ⁺¹ q

and

(2ⁿ⁺¹ − 1) 2ⁿ⁺¹ q = 2ⁿ⁺¹ X

Canceling from both sides we now have

X = (2ⁿ⁺¹ − 1) q

In particular, X is a proper multiple of q . Now add q to both sides of this last equation; we obtain

X + q = 2ⁿ⁺¹ q = S

Think about this: S is the sum of all of the divisors of X. If q ≠ 1, then there are at least three divisors of X, namely 1, q and X itself. But then we have a contradiction, since S would then be greater than X + q.

So: q = 1 and X = 2ⁿ⁺¹ − 1

and our original N is of the correct form!

4) BUT no one knows if there is an odd perfect number, or even if there are infinitely many even perfect numbers!

Standard Podcast [ 11:01 ] Play Now | Play in Popup | Download

In August 2008, the 45th known Mersenne prime, a mere 2^43,112,609-1 was discovered by the Great Internet Mersenne Prime Search! Our puzzle this week is really just to rediscover for yourself proofs that 

• if a number of the form 2^N-1 is prime, then N must also be prime (Or contrapositively, if N is composite, then 2^N-1 is also composite)
• if a number of the form 2^N-1 is prime then the number 2^(N-1) x (2^N-1) is perfect— that is, it is the sum of all its proper divisors.

For example, 2³ – 1 = 7, which happens to be prime. 2² x (2³-1) = 28, which has proper divisors 1, 2, 4, 7, and 14, which sum to (drumroll) 28.

For fun you might look around for numbers of the form 2^{a prime} -1 that are not themselves prime; this shouldn’t take too long since these are far more common than that those that are, the Mersenne Primes.

If you want a little more of a challenge, try to prove that

• any even perfect number must be of this form

and if you want to be really famous, settle the conjectures that

• this takes care of everything—in other words that there are no odd proper numbers
• but that there are in fact infinitely many Mersenne primes and so infinitely many even perfect numbers

Ed Pegg, of mathpuzzle.com , Wolfram research and consultant to the TV show Numb3rs, returns to discuss cellular automata and a fiendishly difficult puzzle.

Standard Podcast [ 10:34 ] Play Now | Play in Popup | Download

Peter Winkler discusses the bonus chapter, on the word game HIPE, in his book, Mathematical Mind Benders!

Standard Podcast [ 6:08 ] Play Now | Play in Popup | Download

In an earlier post Spaghetti Loops, we asked several problems that we promised had something to do with the number e.

The first question really has to do more with the famous harmonic series; in this post we showed that the sum

1 + 1/2 + 1/3 + 1/4 + …. + 1/n

adds up to about the natural log of n, plus a small constant, Euler’s γ ≈ .577215664901… In other words, to sum up to, say N, at least e^{(N- γ)} terms are used.

Read the rest of this entry »