A curious occurrence of the Fibonacci numbers

Anyone who has some familiarity with the Fibonacci numbers,
\[0, \,\ 1, \,\ 1, \,\ 2, \,\ 3, \,\ 5, \,\ 8, \,\ 13, \,\ 21, \,\ 34, \,\ 55, \,\ 89, \,\ \ldots,\]
will know that they have a way of cropping up in the most unlikely places. In today's posting we document another such instance.

They arise when we study the compositions of positive integers. I prefer to call them "ordered partitions" but "compositions" is the accepted term.

As you know, a partition of a positive integer $n$ is a way of writing $n$ as a sum of (an unspecified number of) positive integers, order not being regarded as important. Thus, there are $2$ partitions of $2$ (namely, $2$ and $1+1$); $3$ partitions of $3$:
\[3, \quad 2+1, \quad 1+1+1\]
and $5$ partitions of $4$:
\[4, \quad 3+1, \quad 2+2, \quad 2+1+1 \quad 1+1+1+1.\]
Note that we do not distinguish between $3+1$ and $1+3$; that is, the sums are unordered. The above lists show that the partition numbers of $2$, $3$, $4$ are $2$, $3$, $5$ respectively; we write $P(2) = 2$, $P(3) = 3$ , $P(4) = 5$, where $P$ denotes the partition function. The $P$-function grows at terrific speed; for example,

• $P(100) = 190,569,292$;
• $P(200) = 3,972,999,029,388$;
• $P(300) = 9,253,082,936,723,602$.

Big numbers!

The partition function is the setting for many famous and beautiful (and almost unbelievable) results, proved by mathematicians like Ramanujan, Hardy, Littlewood and Rademacher. But we shall not dwell on these results in this post.

A variation - "ordered partitions"

Instead, we shall choose to regard order as important, in which case we get ordered partitions (or compositions, as noted above). Let $f(n)$ denote the number of ordered partitions of $n$. We get the following values of $f(n)$:

• $f(1) = 1$, as $1$ has just one ordered partition ($1$ itself);
• $f(2) = 2$, as $2$ has the following two ordered partitions: $2$ and $1+1$;
• $f(3) = 4$, as $4$ has the following four ordered partitions: $3$, $2+1$,$1+2$, $1+1+1$;
• $f(4) = 8$, as $4$ has the following eight ordered partitions: $4$, $3+1$, $1+3$, $2+2$, $2+1+1$, $1+2+1$, $1+1+2$, $1+1+1+1$.

Observe the sequence of values: $1$, $2$, $4$, $8$. Why, we seem to have a doubling sequence! Can we expect, then, that $f(5) = 16$? Let's check: the ordered partitions of $5$ are $5$, $4+1$, $1+4$, $3+2$, $2+3$, $3+1+1$, $1+3+1$, $1+1+3$, $2+2+1$, $2+1+2$,$1+2+2$, $2+1+1+1$, $1+2+1+1$, $1+1+2+1$, $1+1+1+2$, $1+1+1+1+1$. The count is indeed $16$.

It appears then that $f(n) = 2^{n-1}$ for all $n \ge 1$. But how may one prove this compact and elegant result? Try it out!

Another variation - we leave out the number 1

Now let us introduce a simple variation: in the partitions we shall not allow the number $1$; thus, all the summands must exceed $1$. In this case $5$ has only three such ordered partitions: $5$, $3+2$, $2+3$.

In general, let $g(n)$ denote the number of ordered partitions of $n$ in which every summand exceeds $1$. We get the following values of $g(n)$:

• $g(1) = 0$ (no partitions are possible if $1$ cannot be used);
• $g(2) = 1$ (there is just one such partition, $2$ itself);
• $g(3) = 1$ (there is just one such partition, $3$ itself);
• $g(4) = 2$ (the two partitions are $4$ and $2+2$);
• $g(5) = 3$ (obtained above);
• $g(6) = 5$ (the five partitions are $6$, $4+2$, $2+4$, $3+3$, $2+2+2$);
• $g(7) = 8$ (the eight partitions are $7$, $5+2$, $2+5$, $4+3$, $3+4$, $3+2+2$, $2+3+2$, $2+2+3$);
• $g(8) = 13$ (the thirteen partitions are $8$, $6+2$, $2+6$, $5+3$, $3+5$, $4+4$, $4+2+2$, $2+4+2$, $2+2+4$, $3+3+2$, $3+2+3$, $2+3+3$, $2+2+2+2$).

We get the following sequence of values of the $g$ function: $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$. Why, we seem to have obtained the Fibonacci sequence! Is this really so?

Let us verify whether $g(9) = 21$ (for the next Fibonacci number after $13$ is $21$); the ordered partitions of $9$ in which every summand exceeds $1$ are $9$, $7+2$, $2+7$, $6+3$, $3+6$, $5+4$, $4+5$, $5+2+2$, $2+5+2$, $2+2+5$, $4+3+2$, $4+2+3$, $3+4+2$, $3+2+4$, $2+3+4$, $2+4+3$, $3+3+3$, $3+2+2+2$, $2+3+2+2$, $2+2+3+2$, $2+2+2+3$. Indeed there are $21$ such partitions!

Is it not remarkable that the Fibonacci numbers have arisen in such a context? To check that we are not being fooled by "circumstantial evidence", we need to prove logically that $g(n)$ is a Fibonacci number; the proof cannot be numerical or circumstantial. This is not as difficult as may seem at first sight, and may be shown by proving that the $g$'s obey the basic recursive law governing the Fibonacci numbers, namely:
\[g(n) = g(n-1) + g(n-2)\]
for any integer $n \ge 3$. Since $g(1)$ and $g(2)$ are already known to be the first two consecutive Fibonacci numbers, the rest then follows.

Here are some references to Fibonacci numbers that point out some further aspects of the Fibonacci numbers.

• Wolfram Mathworld - Fibonacci 
• Wikipedia - Mathworld 

The Wolfram reference lists several contexts where the Fibonacci numbers arise in a natural yet unexpected manner.

Pretty decimals

Everyone is fond of recurring decimals (well, I certainly am ...). Who can resist being charmed by the fact that
\[\frac{1}{7} = 0.142857 \ 142857 \ 142857 \ \ldots,\]
with the portion $142857$ recurring indefinitely (it is called the repetend) and having these several striking properties: first,

• $142857 \times 2 = 285714$
• $142857 \times 3 = 428571$
• $142857 \times 4 = 571428$
• $142857 \times 5 = 714285$
• $142857 \times 6 = 857142$

with the circular arrangement of digits in each product being exactly the same as in $142857$; and next, if we "slice" the number in two halves, like this:
\[\fbox{$142$} \ \fbox{$857$}\]
and add the two "halves", we get
\[142 + 857 = 999,\]
a number wholly composed of $9$'s.

If we try this with the fraction $1/13$, we find something very similar. The repetend is now $076923$, since
\[\frac{1}{13} = 0.076923 \ 076923 \ 076923 \ \ldots,\]
and this number has nearly the same features as the number $142857$; but there are also some curious differences. Thus, its multiples with the numbers $1$, $3$, $4$, $9$, $10$, $12$ yield numbers that have the same circular pattern of digits as $076923$:

• $076923 \times 1 = 076923$
• $076923 \times 3 = 230769$
• $076923 \times 4 = 307692$
• $076923 \times 9 = 692307$
• $076923 \times 10 = 769230$
• $076923 \times 12 = 923076$

whereas its multiples with the numbers $2$, $5$, $6$, $7$, $8$, $11$ yield another set of numbers which too bear the very same relationship amongst themselves:

• $076923 \times 2 = 153846$
• $076923 \times 5 = 384615$
• $076923 \times 6 = 461538$
• $076923 \times 7 = 538461$
• $076923 \times 8 = 615384$
• $076923 \times 11 = 846153$

Note that the numbers
\[153846, \quad 384615, \quad 461538, \quad 538461, \quad 615384, \quad 846153\]
all have the same circular arrangement of digits. How very curious!

You may well ask, is there any other property that bonds the numbers $1$, $3$, $4$, $9$, $10$, $12$ together, and similarly bonds the numbers $2$, $5$, $6$, $7$, $8$, $11$ together? Yes, there is! - try to find it.

Finally, note that if we slice the number $076923$ in two halves,
\[\fbox{$076$} \ \fbox{$923$}\]
and add the two halves, we get
\[076 + 923 = 999,\]
exactly like earlier.

Is this a general feature that we find with all recurring decimals? Try it out - go and explore more such decimals! You will almost certainly unearth more patterns of interest.

Here is an associated problem which is of some interest: Find the smallest positive integer with the feature that if the units digit is taken to the "opposite end" of the number, the new number is exactly twice the original number.

Powers sequences strung on a line

Infinite decimals have still more morsels to offer. For example, consider the decimal arising from the fraction $1/99998$:
\[\frac{1}{99998} = 0.00001 \  00002 \ 00004 \ 00008 \ 00016 \ 00032 \ 00064 \ \ldots.\]
Well, we see the powers of $2$ on display, all strung out on a line!

If we change the fraction to $1/99997$ we get something just as nice:
\[\frac{1}{99997} = 0.00001 \ 00003 \ 00009 \ 00027 \ 00081 \ 00243 \ 00729 \ \ldots.\]
Now we see the powers of $3$. Isn't that a pretty sight?

Once we get the general idea, it isn't at all hard to generalize it. For example, here is $1/9995$:
\[\frac{1}{99995} = 0.00001 \ 00005 \ 00025 \ 00125 \ 00625 \ 03125 \ 15625 \ldots.\]
But I hear you jumping up and saying something urgently to me:

"Hold on, now! These are the decimal expansions of rational numbers, so they ought to yield recurring decimals, right? But where are the recurring sequences in the above decimals? I don't see any!" 

Well, I'll leave it to you to figure that one out!

One can even get the Fibonacci numbers strung out on a line:
\[\frac{1000}{998999} = 0.001 \ 001 \ 002 \ 003 \ 005 \ 008 \ 013 \ 021 \ 034 \ 055 \ 089 \  \ldots.\]
Try to figure out which fraction will yield the Lucas numbers.

(The Lucas sequence is less well known than the Fibonacci sequence, but is defined in a very similar way. Its starting numbers are $2$ and $1$, in that order, and following these, each subsequent number is the sum of the two that precede it
\[2, \,\ 1, \,\ 3, \,\ 4, \,\ 7, \,\ 11, \,\ 18, \,\ 29, \,\ 47, \,\ 76, \,\ \ldots.\]
These numbers have extremely close interconnections with the Fibonacci numbers.)

\[\clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit\]

Primes in arithmetic progression

How many primes can you find in arithmetic progression (prime AP for short)? Recall that in an AP, the differences between successive members are the same, so the AP has the form $a$, $a+d$, $a+2d$, $a+3d$, $a+4d$, .... Here $a$ is called the "first term" while $d$ is the "common difference". For example, $1$, $4$, $7$, $10$ is a four term AP with common difference $d = 3$.

Here are some examples of prime APs:

• {$3$, $5$, $7$}, with length $3$ and common difference $2$;
• {$5$, $11$, $17$, $23$, $29$}, with length $5$ and common difference $6$;
• {$7$, $37$, $67$, $97$, $127$, $157$}, with length $6$ and common difference $30$.
• {$7$, $157$, $307$, $457$, $607$, $757$, $907$}, with length $7$ and common difference $150$.

It is easy to check that the prime AP {$3$, $5$, $7$}, with length $3$ and common difference $2$, is the only such prime AP, and a prime AP with common difference $2$ cannot exceed a length of $3$. To see why, we only need to examine the remainders left by these numbers on division by $3$.

It is also easy to see the following:

• If a prime AP has length greater than $2$, then its common difference must be an even number, and it must feature only odd primes (because $2$ is the only even prime).
• If a prime AP has length greater than $3$, then its common difference must be a multiple of $3$, and therefore a multiple of $6$ as well (since it also must be an even number). To see why, we only need to examine the remainders left by these numbers on division by $3$.
• If a prime AP has length greater than $5$, then its common difference must be a multiple of $5$, and therefore a multiple of $30$ as well (since it also must be a multiple of $6$). To see why, we only need to examine the remainders left by these numbers on division by $5$.
• If a prime AP has length greater than $7$, then its common difference must be a multiple of $7$, and therefore a multiple of $210$ as well (since it also must be a multiple of $30$). To see why, we only need to examine the remainders left by these numbers on division by $7$.

This chain of results may clearly be extended indefinitely.

By these means we can list innumerable necessary conditions for the existence of long prime APs.

But finding such APs is quite a different matter. As of now, it is largely based on trial-and-error, but guided by clever heuristics. In other words: try, try, and try again! To get a sense of the difficulties involved in this, try finding a prime AP of length $10$ or more - on your own!

Recently (earlier this month, in fact), researchers found a prime AP of length $26$. Here is a link to the site where the discovery was announced: AP26 discovery. The first prime of this AP is
\[43142746595714191,\]
and its common difference is this number:
\[23681770 \times (2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23).\]
In other words, this AP consists of the numbers
\[43142746595714191 + 5283234035979900 \times n\]
for $n = 0$, $1$, $2$, ..., $25$.

Note that the number
\[2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 = 223092870,\]
which is a factor of the common difference, is simply the product of the first $9$ primes. (You will find numbers of this kind repeatedly featuring in such searches.) You can check that the last member of this prime AP is the number
\[175223597495211691.\]
To verify that all these $26$ numbers are really prime would require a good computer algebra system, like Derive or Mathematica or the free open source package, Maxima. Here is what Maxima tells you when you ask it whether the $27$-th term of the AP is prime or not - that is, the number
\[43142746595714191 + 5283234035979900 \times 26;\]
Maxima returns the factorization
\[29 \times 31 \times 41 \times 59 \times 85433250011.\]
So this particular AP cannot be extended beyond $26$ terms.

As of now, this is the "champion" - the holder of the "world record"! No prime AP of length greater than $26$ is currently known.

But just a few years back, Terence Tao and Ben Green proved that there exist prime APs of any desired length! (We had featured Terence Tao in a previous posting.) In other words, there must exist a prime AP of length exceeding one billion; only, we may never ever find it, for it may well involve stupendously large numbers ...

Here are two other sites which will tell you a lot about this topic: Prime AP records and Wikipedia-primes in AP.
\[\clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit \quad \clubsuit\]

Views from Terence Tao

Here is an interesting interview with the remarkably prolific Terence Tao, who is one of the youngest Field Medalists ever (he got the Medal in 2006, during the last ICM); it is certainly worth reading:

• Terence Tao - interview

And here is Tao writing on his own blog, on a topic much discussed these days: the potentialities of the internet in teaching; this is actually a talk given at the American Academy of Arts and Sciences, at their induction ceremony:

• Speech given at American Academy of Arts and Sciences

What is interesting is that he posted a rough draft of the talk on his blog, prior to the actual talk, and invited comments and feedback, and then incorporated some of what he received into his talk.

Today, in the light of radical changes currently happening in the Indian education system, such as the passing of the Right to Education Act, there is considerable talk going on about teacher education. (There is a gigantic shortage in the supply of trained teachers today.) A key question here is whether Web based delivery systems have any role to play in tackling this vast problem. I think Prof Tao's comments have value in this context. A lot of thought needs to be given to this question, and I invite readers to share their views and post their comments. Links to pieces written about this would be very welcome.

Big numbers!

Here is a delightful piece about big numbers, written by Professor Marcus du Sautoy, who is a mathematician and a remarkably gifted expositor, and Oxford University's Simonyi Professor of the Public Understanding of Science (a post held till recently by Professor Richard Dawkins):

• Big numbers

The piece is from the Guardian (published in the UK). If you want to read more about the author, here is another piece from the Guardian:

• Marcus du Sautoy

It not tells you about the author but also describes some of the challenges he faces in today's cultural context.

Teachers will be particularly interested in this essay by du Sautoy, on how to spark off interest in mathematics in young children; it too is from the Guardian:

• Sparking interest in maths

It is, in fact, a must-read for all mathematics teachers.

Almost Pythagorean Triples (APTs) - 1

Practically everyone is familiar with Pythagorean triples - triples $(a,b,c)$ of positive integers for which
\[a^2 + b^2 = c^2.\]
If $a, b, c$ are coprime we call the triple a Primitive Pythagorean Triple, or PPT for short. Well known examples are the triples $(3, 4, 5)$ and $(5, 12, 13)$. There is a huge literature about PPTs: how we can generate them in a systematic way, what kinds of number theoretic properties they possess, and so on. Here is a typically striking result about PPTs:

• If $(a, b, c)$ is a PPT, then $a b c$ is divisible by $60$.

Here are some links to material about PPTs available on my own site, MathCelebration:

• PPT1-screen
• PPT1-print
• PPT2-screen
• PPT2-print

Let us now tweak the problem a bit, and ask about triples of positive integers that almost satisfy the condition required of a Pythagorean triple, missing it by the smallest possible margin (namely, by $1$). Thus, we want triples $(a, b, c)$ of positive integers such that
\[a^2 + b^2 = c^2 \pm 1.\]
If the positive sign holds we shall call $(a, b, c)$ an APT - short for "almost Pythagorean triple". And if the negative sign holds we shall call $(a, b, c)$ a NPT - short for "near Pythagorean triple".

But finding APTs and NPTs turns out to be trickier than finding PPTs. The difficulty is caused by the fact that the defining equations are not homogeneous. In the case of PPTs the defining equation is homogeneous of degree $2$; if we divide the equation $a^2 + b^2 = c^2$ by $c^2$, and write $x = a/c$, $y = b/c$, we get the equation $x^2 + y^2 = 1$, whose form immediately brings to mind the equation of a unit circle in the Cartesian plane. This observation if pursued yields a parametric solution to the Pythagorean equation. It is just this approach that has been followed in the articles listed above.

But this approach fails in the case of APTs and NPTs; the non-homogeneity of the equation $x^2 + y^2 = z^2 \pm 1$ negates all such attempts. So for the moment let me not say how we can go about finding them, but simply exhibit a few such triples - found simply by "brute force search" using a computer.

Here are some APTs. For simplicity I have taken $a \le b \le 30$.

a    b    c

_________

4     7     8 

5     5     7 

6    17   18 

7    11   13 

8     9   12 

9   19   21 

10   15   18 

11   13   17 

11   29   31 

13   19   23 

14   17   22 

15   26   30 

16   23   28 

17   21   27 

19   27   33 

20   25   32 

23   29   37 

29   29   41 

(Comment, in passing. The table looks terrible from a typesetting point of view, doesn't it? But I have yet to figure out how to typeset LaTeX-style tables in blogger.)

Try generating more such triples, and look for patterns hidden in them. I think there are more patterns there than one may expect.

The same thing is true for NPTs - i.e., triples $(a, b, c)$ of positive integers for which $a^2 + b^2 = c^2 - 1$. Here are a few such triples, generated the same way (with $a \le b \le 30$):

a   b   c

________

2    2    3  

4    8    9  

6   18  19  

12   12   17  

18   30   35  

If you experiment on this problem on your own, you will hit upon several oddities which are difficult to explain. For example, there seem to be many more APTs than NPTs. Within the region $a \le b \le 30$, the above two tables list all APTs and all NPTs. Observe that the APTs outnumber the NPTs by a fairly big margin. This discrepancy persists as the upper bound is raised. It is not at all clear why this is so.

We'll continue on this theme in the next post.

Jaime Escalante

Jaime Escalante, a mathematics teacher who taught in Los Angeles, California, USA, under very difficult conditions and achieved something truly remarkable, has just passed away (on 30 March 2010). Please see these two links:

• Jaime Escalante - Wikipedia, the free encyclopedia.
• LA Times - obituary

There was even a film made about him, in 1988 - Stand And Deliver.

It would be wonderful if we could document similar stories from India. I am certain that there are many, many unsung heroes out there, in the small town and villages, unknown to all except those who studied under them and learned not only the beauty of our subject but also about the vast canvas of life.