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 [...] for , 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):

n	f(n)	2^n	diff
6	31	32	1
7	57	64	7
8	99	128	29
9	163	256	93
10	256	512	256
11	386	1024	638
12	562	2048	1486
13	794	4096	3302
14	1093	8192	7099
15	1471	16384	14913
16	1941	32768	30827
17	2517	65536	63019
18	3214	131072	127858
19	4048	262144	258096
20	5036	524288	519252
21	6196	1048576	1042380
22	7547	2097152	2089605
23	9109	4194304	4185195
24	10903	8388608	8377705

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:

n	f(n)	2^n	diff	quotient
6	31	32	1	~
7	57	64	7	7
8	99	128	29	4.14285714285714
9	163	256	93	3.20689655172414
10	256	512	256	2.75268817204301
11	386	1024	638	2.4921875
12	562	2048	1486	2.32915360501567
13	794	4096	3302	2.22207267833109
14	1093	8192	7099	2.14990914597214
15	1471	16384	14913	2.10071841104381
16	1941	32768	30827	2.06712264467243
17	2517	65536	63019	2.04427936549129
18	3214	131072	127858	2.02888017899364
19	4048	262144	258096	2.01861440035039
20	5036	524288	519252	2.01185605356147
21	6196	1048576	1042380	2.00746458367036
22	7547	2097152	2089605	2.00464801703793
23	9109	4194304	4185195	2.00286417767951
24	10903	8388608	8377705	2.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!