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?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).

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 |

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 |

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!

## 3 comments:

Awesome!!! Beautiful Post... Easily understood by everyone :) Keep up the good work.

Hi, The fact that O(2^n) obviously exceeds O(x^a) asymptotically is what you have observed. In general, Take any numbers in the sequence n^0, n^1, ..., n^k and interpolate them to be a polynomial of order k, and find out ratios eventually it will converge to n. :)

Post a Comment