## Friday, November 13, 2009

### My first OEIS contributions!

I made my first ever contributions to N.J.A. Sloane's On-Line Encyclopedia of Integer Sequences yesterday. They're basically enumerations of all admissible basis for the postage stamp problem.
 ```k\h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ``` ```(A167809) 2 1 2 5 17 65 292 1,434 7,875 47,098 305,226 2,122,983 15,752,080 124,015,310 1,031,857,395 9,041,908,204 83,186,138,212 ``` ```(A167810) 3 1 3 13 86 760 8,518 116,278 1,911,198 37,063,964 835,779,524 21,626,042,510 635,611,172,160 ``` ```(A167811) 4 1 4 26 291 4,752 109,640 3,380,466 136,053,274 6,963,328,612 444,765,731,559 ``` ```(A167812) 5 1 5 45 750 20,881 880,325 54,329,413 4,727,396,109 563,302,698,378 ``` ```(A167813) 6 1 6 71 1,694 73,126 5,235,791 593,539,539 102,141,195,784 ``` ```(A167814) 7 1 7 105 3,407 217,997 24,929,035 4,863,045,067 ```
Anyone with a reasonable brute force solver can generate these exact numbers, so I don't really take much in terms of credit for being the "author". I can always submit more sequences by varying the parameters if I just want to senselessly "stake my claim" on them, so to speak, but I see little point in doing any more than I already did. I do think that these sequences are important for several reasons:
• One can quantify the size of the search space and its growth rate, and assess the limits of practicality of a brute force solver.
• Having some terms is better than none when you're trying to define a tight asymptotic bound, or better yet, an exact formula.
• More practically, these are the benchmark numbers to compare to once you start pruning the search tree.
• It's always useful to have these sequences on record since they may unexpectedly pop up elsewhere, or be in some other way related to other sequences in the encyclopedia.
That last point is emphasized when I found out that the enumeration for `h = 2` is related to Goldbach's conjecture somehow. In fact, A167809 is essentially a duplicate of A008932, which has an impressively short PARI code attached. I wish I know what it does, see if it can be generalized. In fact, there are a lot of important results for `h = 2`, of which any generalization would be a huge breakthrough.
(update) I've figured what the PARI code does, and yes, it is quite trivially generalizable to `h > 2`. This is a straightly mathematical approach to the postage stamp problem. To illustrate, let's look at the case when `h = 3` and the basis is `{ 0 } U { 1, 2, 5 }`.
```> sort(expand((x^0 + x^1 + x^2 + x^5)^3));
15      12      11      10      9      8      7      6      5      4      3
x   + 3 x   + 3 x   + 3 x   + 3 x  + 6 x  + 9 x  + 7 x  + 6 x  + 6 x  + 7 x

2
+ 6 x  + 3 x + 1```
A term `c[i]*x^i` means that the number `i` is obtainable in `c[i]` different ways as the sum of exactly `h` numbers in the basis (including the introduced `0`), allowing permutations (e.g. `9x^7 ->` 7 = 0+2+5 = 0+5+2 = 2+0+5 = 2+5+0 = 5+0+2 = 5+2+0 = 1+1+5 = 1+5+1 = 5+1+1).