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

No comments:

Post a Comment