Wednesday, 7 November, 2007

Law of small numbers and such...

The first strong law of small numbers (Gardner 1980, Guy 1988, Guy 1990) states "There aren't enough small numbers to meet the many demands made of them."

The second strong law of small numbers (Guy 1990) states that "When two numbers look equal, it ain't necessarily so." Guy (1988a) gives 35 examples of this statement, and 40 more in Guy (1990). For example, example 35 notes that the first few values of the interpolating polynomial (n^4-6n^3+23n^2-18n+24)/24 [...] for n==1, 2, ... are 1, 2, 4, 8, 16, .... Thus, the polynomial appears to give the powers of 2, but then continues 31, 57, 99, ... (Sloane's A000127).
I just read this at Wolfram Mathworld; and something flashed within me. What if the differences between this poly and the actual powers of two were significant? Well, being terribly bored and having a lot of time to kill, I set out to explore that. I was stuck at the first step itself - I was in Linux, and didn't know any way to do math explorations like this. Had I been in Windows, I would have used Matlab (damn good and surprisingly easy to use). I'm sure there's some 'popular' Free Software for this kind of job, but I was not in a mood to search for software packages and get into dependency hell just yet. So, I just asked myself, can I do it with what I do know to do in Linux?
Writing C programs. Perl scripts. Shell scripts. For this kind of job, Perl somehow seemed more appropriate. So, I typed out a Perl script to find the differences (here f(n) is the 4th order polynomial given in the above article):

nf(n)2^ndiff
631321
757647
89912829
916325693
10256512256
113861024638
1256220481486
1379440963302
14109381927099
1514711638414913
1619413276830827
1725176553663019
183214131072127858
194048262144258096
205036524288519252
21619610485761042380
22754720971522089605
23910941943044185195
241090383886088377705
No obvious pattern emerged. Then, on second thoughts, there did seem to be some sort of pattern to it. The differences are all increasing. But each one increased by a lesser amount than the previous one. 7/1 is (quite obviously) 7, 29/7 is slightly greater than 4, 93/29 is slightly greater than 3, etc. As the numbers increased, it seemed that they increased by successively smaller factors. The numbers had some kind of geometrical pattern - sort of like a geometric series where you get successive terms by multiplying each term by a constant ratio. However, in this case, the ratio wasn't exactly constant. Instead, it seemed to be tending towards some constant.

To check this out, I then printed the quotient obtained by dividing each difference by its predecessor. Lo and behold, suddenly, there was Light:
nf(n)2^ndiffquotient
631321~
7576477
899128294.14285714285714
9163256933.20689655172414
102565122562.75268817204301
1138610246382.4921875
12562204814862.32915360501567
13794409633022.22207267833109
141093819270992.14990914597214
15147116384149132.10071841104381
16194132768308272.06712264467243
17251765536630192.04427936549129
1832141310721278582.02888017899364
1940482621442580962.01861440035039
2050365242885192522.01185605356147
216196104857610423802.00746458367036
227547209715220896052.00464801703793
239109419430441851952.00286417767951
2410903838860883777052.00174782775952
So, there you have it: the quotient of dividing each successive difference between 2^n and this f(n) is approaching 2. For n=70 and higher, it was so close to 2 that Perl gave it up and printed it as just 2. So, the quotients are converging towards 2 as far as we can see. Each successive difference, then, is obtained by multiplying the previous difference by a number very close to 2.
That is the kind of beauty math has. You obtain a sequence that looks like powers of 2 for small numbers, you find that it deviates from the actual value for higher powers, then you find that the deviation itself is increasing in powers of two. This thing has some inexplicable beauty to it... :)
So, now that we've found that this thing seems to converge to 2, how do we interpret it? That's the kind of thing for which you need mathematical training. If I had had some good math course on series and sequences, may be I would know what to do with this. May be I'd theoretically prove that the quotients actually converge to 2 as n tends to infinity. May be we can show that this f(n) can indeed be used to find powers of 2.
For now, let's get into the nitty gritty of this number crunching. First, I wrote this cute little program (any claims to its uncuteness are by Agents of Satan; avoid them like plague) :

#!/usr/bin/perl

use warnings;
use strict;

my @range = (6 .. 24); #6 is where the differences start to be non-zero
my $i;
my @diffs;

foreach $i (@range)
{
print $i,"\t\t";
print (( $i**4 - 6*$i**3 + 23*$i**2 - 18*$i + 24 ) / 24, "\t\t");
print 2**($i - 1), "\t\t";
push @diffs, (2**($i - 1) - (( $i**4 - 6*$i**3 + 23*$i**2 - 18*$i + 24 ) / 24));
print $diffs[$#diffs], "\t\t";
$#diffs && print $diffs[$#diffs]/$diffs[$#diffs-1];
print "\n";
}

Then, I ran the output through txt2html with --make_tables option. I got the HTML code for a table, which you can see with naked eye by right clicking here and choosing 'View source' (or whatever option reads close to that). Using the code, I made a blog post named 'Law of small numbers and such...'.

You just finished reading it!