Postage stamp problem A004129

[Ed Pegg]

https://oeis.org/A004129  
Postage stamp problem: largest m such that there exists an n-subset S of nonnegative integers such that 1,...,m can be expressed as a sum of two distinct elements of S.  

Looking at this, I was reminded of the sparse ruler problem, which Brian Wichmann pretty much solved with a recipe. Since this  A004129  seems to be very difficult, I decided to convert it into a recipe problem. 

For n ≥ 24, the construction gives A004129(n) ≥ Floor[(n + 3)^2/4] - 3.  

note... the values over 105 are unproven.  

rep[x_,k_]:=ConstantArray[x,k];
gapWord[x___]:=Flatten[{x}];
stamp[gaps_List]:=Prepend[1+Accumulate[gaps],1];
(*PennyRed[d,r]=1^(d-2),d-1,d^r*)
PennyRed[d_,r_]:=gapWord[rep[1,d-2],d-1,rep[d,r]];
(*BlueMauritius[a,r]=1^(a-1),a,(a+1)^r,a,1^a*)
BlueMauritius[a_,r_]:=gapWord[rep[1,a-1],a,rep[a+1,r],a,rep[1,a]];
(*Cottonreel[k,q]=1,2^k,1^2,2k+4,3,((2k+5),3)^q*)
Cottonreel[k_,q_]:=gapWord[1,rep[2,k],rep[1,2],2 k+4,3,rep[{2 k+5,3},q]];
(*SevenTail[r]=1,2,1^2,4,3,7^r*)
SevenTail[r_]:=gapWord[1,2,rep[1,2],4,3,rep[7,r]];
(*NineTail[r]=1,2^2,1,5,2,3,4,9^r*)
NineTail[r_]:=gapWord[1,rep[2,2],1,5,2,3,4,rep[9,r]];
(*PennyBlack[d,r]=1^(d-9),2,4,1,d-6,2,1^2,d-1,d^r*)
PennyBlack[d_,r_]:=gapWord[rep[1,d-9],2,4,1,d-6,2,rep[1,2],d-1,rep[d,r]];
(*Treskilling14[r]=1,2^2,3,1,7,2^2,1,3,1^2,13,14^r*)
Treskilling14[r_]:=gapWord[1,rep[2,2],3,1,7,rep[2,2],1,3,rep[1,2],13,rep[14,r]];
(*Zeppelin15[r]=1^2,3,2,1^3,8,1,2,5,1^2,14,15^r*)
Zeppelin15[r_]:=gapWord[rep[1,2],3,2,rep[1,3],8,1,2,5,rep[1,2],14,rep[15,r]];
(*Gronchi16[r]=1^2,3,1,2,1^3,8,1,3,5,1^2,15,16^r*)
Gronchi16[r_]:=gapWord[rep[1,2],3,1,2,rep[1,3],8,1,3,5,rep[1,2],15,rep[16,r]];
(*InvertedJenny[p,r]=1^2,3,1,2^p,8,1,3,2^p,1^2,2p+10,(2p+11)^r*)
InvertedJenny[p_,r_]:=gapWord[rep[1,2],3,1,rep[2,p],8,1,3,rep[2,p],rep[1,2],2 p+10,rep[2 p+11,r]];
(*BaselDove[m,r]=1^m,m-1,1^m,2m+2,1^(m-3),m+2,1^(m-2),4m-1,(4m)^r*)
BaselDove[m_,r_]:=gapWord[rep[1,m],m-1,rep[1,m],2 m+2,rep[1,m-3],m+2,rep[1,m-2],4 m-1,rep[4 m,r]];
(*RedMercury[m,r]=1^m,m,1^m,2m+3,1^(m-2),m+2,1^(m-1),4m+1,(4m+2)^r*)
RedMercury[m_,r_]:=gapWord[rep[1,m],m,rep[1,m],2 m+3,rep[1,m-2],m+2,rep[1,m-1],4 m+1,rep[4 m+2,r]];

And these lead to solutions.  

A004129Known=<|1->{{1}},
3->{stamp[PennyRed[2,0]]},
6->{stamp[PennyRed[2,1]]},
9->{{1,2,3,6},stamp[PennyRed[3,1]]},
13->{stamp[PennyRed[4,1]]},
17->{stamp[PennyRed[5,1]],stamp[PennyRed[4,2]]},
22->{stamp[PennyRed[5,2]]},
27->{stamp[PennyRed[6,2]],stamp[PennyRed[5,3]],stamp[Cottonreel[2,0]],stamp[BlueMauritius[2,2]]},33->{stamp[PennyRed[6,3]],stamp[SevenTail[2]],stamp[Cottonreel[3,0]],stamp[BlueMauritius[2,3]]},
40->{stamp[SevenTail[3]]},
47->{stamp[BlueMauritius[3,3]],stamp[SevenTail[4]],stamp[NineTail[2]],stamp[Cottonreel[3,1]]},
56->{stamp[NineTail[3]]},
65->{stamp[NineTail[4]]},
74->{stamp[NineTail[5]]},
83->{{1,2,3,5,9,10,15,17,18,19,29,40,51,62,73},stamp[NineTail[6]]},
94->{stamp[PennyBlack[11,5]]},
105->{stamp[PennyBlack[11,6]]},
116->{stamp[PennyBlack[11,7]]},
127->{stamp[PennyBlack[11,8]],stamp[PennyBlack[12,7]]},
139->{stamp[PennyBlack[12,8]]},
151->{stamp[PennyBlack[12,9]],stamp[PennyBlack[13,8]]},
165->{stamp[Treskilling14[8]]},
179->{stamp[Treskilling14[9]]},
193->{stamp[Treskilling14[10]]},
207->{stamp[Treskilling14[11]],stamp[Zeppelin15[10]]},
222->{stamp[Zeppelin15[11]]},
237->{stamp[Zeppelin15[12]],stamp[Gronchi16[11]]},
253->{stamp[Gronchi16[12]]},
269->{stamp[Gronchi16[13]],stamp[InvertedJenny[3,12]]},
286->{stamp[InvertedJenny[3,13]]},
303->{stamp[InvertedJenny[3,14]],stamp[RedMercury[4,13]]},
321->{stamp[RedMercury[4,14]]},
339->{stamp[RedMercury[4,15]],stamp[InvertedJenny[4,14]]},
358->{stamp[InvertedJenny[4,15]]},
377->{stamp[InvertedJenny[4,16]],stamp[BaselDove[5,15]]},
397->{stamp[BaselDove[5,16]]},
417->{stamp[BaselDove[5,17]],stamp[InvertedJenny[5,16]]},
438->{stamp[InvertedJenny[5,17]]},
459->{stamp[InvertedJenny[5,18]],stamp[RedMercury[5,17]]},
481->{stamp[RedMercury[5,18]]}|>;

Or, decoded:   

<|1->{{1}},3->{{1,2}},

6->{{1,2,4}},

9->{{1,2,3,6},{1,2,4,7}},

13->{{1,2,3,6,10}},

17->{{1,2,3,4,8,13},{1,2,3,6,10,14}},

22->{{1,2,3,4,8,13,18},{1,2,3,4,8,13,18}},

27->{{1,2,3,4,5,10,16,22},{1,2,3,4,8,13,18,23},{1,2,4,6,7,8,16,19},{1,2,4,7,10,12,13,14}},

33->{{1,2,3,4,5,10,16,22,28},{1,2,4,5,6,10,13,20,27},{1,2,4,6,8,9,10,20,23},{1,2,4,7,10,13,15,16,17}},

40->{{1,2,4,5,6,10,13,20,27,34}},

47->{{1,2,3,6,10,14,18,21,22,23,24},{1,2,4,5,6,10,13,20,27,34,41},{1,2,4,6,7,12,14,17,21,30,39},{1,2,4,6,8,9,10,20,23,34,37}},

56->{{1,2,4,6,7,12,14,17,21,30,39,48}},

65->{{1,2,4,6,7,12,14,17,21,30,39,48,57}},

74->{{1,2,4,6,7,12,14,17,21,30,39,48,57,66}},

83->{{1,2,3,5,9,10,15,17,18,19,29,40,51,62,73},{1,2,4,6,7,12,14,17,21,30,39,48,57,66,75}},

94->{{1,2,3,5,9,10,15,17,18,19,29,40,51,62,73,84}},

105->{{1,2,3,5,9,10,15,17,18,19,29,40,51,62,73,84,95}},

116->{{1,2,3,5,9,10,15,17,18,19,29,40,51,62,73,84,95,106}},

127->{{1,2,3,5,9,10,15,17,18,19,29,40,51,62,73,84,95,106,117},{1,2,3,4,6,10,11,17,19,20,21,32,44,56,68,80,92,104,116}},

139->{{1,2,3,4,6,10,11,17,19,20,21,32,44,56,68,80,92,104,116,128}},

151->{{1,2,3,4,6,10,11,17,19,20,21,32,44,56,68,80,92,104,116,128,140},{1,2,3,4,5,7,11,12,19,21,22,23,35,48,61,74,87,100,113,126,139}},

165->{{1,2,4,6,9,10,17,19,21,22,25,26,27,40,54,68,82,96,110,124,138,152}},

179->{{1,2,4,6,9,10,17,19,21,22,25,26,27,40,54,68,82,96,110,124,138,152,166}},

193->{{1,2,4,6,9,10,17,19,21,22,25,26,27,40,54,68,82,96,110,124,138,152,166,180}},

207->{{1,2,4,6,9,10,17,19,21,22,25,26,27,40,54,68,82,96,110,124,138,152,166,180,194},{1,2,3,6,8,9,10,11,19,20,22,27,28,29,43,58,73,88,103,118,133,148,163,178,193}},

222->{{1,2,3,6,8,9,10,11,19,20,22,27,28,29,43,58,73,88,103,118,133,148,163,178,193,208}},

237->{{1,2,3,6,8,9,10,11,19,20,22,27,28,29,43,58,73,88,103,118,133,148,163,178,193,208,223},{1,2,3,6,7,9,10,11,12,20,21,24,29,30,31,46,62,78,94,110,126,142,158,174,190,206,222}},

253->{{1,2,3,6,7,9,10,11,12,20,21,24,29,30,31,46,62,78,94,110,126,142,158,174,190,206,222,238}},

269->{{1,2,3,6,7,9,10,11,12,20,21,24,29,30,31,46,62,78,94,110,126,142,158,174,190,206,222,238,254},{1,2,3,6,7,9,11,13,21,22,25,27,29,31,32,33,49,66,83,100,117,134,151,168,185,202,219,236,253}},

286->{{1,2,3,6,7,9,11,13,21,22,25,27,29,31,32,33,49,66,83,100,117,134,151,168,185,202,219,236,253,270}},

303->{{1,2,3,6,7,9,11,13,21,22,25,27,29,31,32,33,49,66,83,100,117,134,151,168,185,202,219,236,253,270,287},{1,2,3,4,5,9,10,11,12,13,24,25,26,32,33,34,35,52,70,88,106,124,142,160,178,196,214,232,250,268,286}},

321->{{1,2,3,4,5,9,10,11,12,13,24,25,26,32,33,34,35,52,70,88,106,124,142,160,178,196,214,232,250,268,286,304}},

339->{{1,2,3,4,5,9,10,11,12,13,24,25,26,32,33,34,35,52,70,88,106,124,142,160,178,196,214,232,250,268,286,304,322},{1,2,3,6,7,9,11,13,15,23,24,27,29,31,33,35,36,37,55,74,93,112,131,150,169,188,207,226,245,264,283,302,321}},

358->{{1,2,3,6,7,9,11,13,15,23,24,27,29,31,33,35,36,37,55,74,93,112,131,150,169,188,207,226,245,264,283,302,321,340}},

377->{{1,2,3,6,7,9,11,13,15,23,24,27,29,31,33,35,36,37,55,74,93,112,131,150,169,188,207,226,245,264,283,302,321,340,359},{1,2,3,4,5,6,10,11,12,13,14,15,27,28,29,36,37,38,39,58,78,98,118,138,158,178,198,218,238,258,278,298,318,338,358}},

397->{{1,2,3,4,5,6,10,11,12,13,14,15,27,28,29,36,37,38,39,58,78,98,118,138,158,178,198,218,238,258,278,298,318,338,358,378}},417->{{1,2,3,4,5,6,10,11,12,13,14,15,27,28,29,36,37,38,39,58,78,98,118,138,158,178,198,218,238,258,278,298,318,338,358,378,398},{1,2,3,6,7,9,11,13,15,17,25,26,29,31,33,35,37,39,40,41,61,82,103,124,145,166,187,208,229,250,271,292,313,334,355,376,397}},438->{{1,2,3,6,7,9,11,13,15,17,25,26,29,31,33,35,37,39,40,41,61,82,103,124,145,166,187,208,229,250,271,292,313,334,355,376,397,418}},

459->{{1,2,3,6,7,9,11,13,15,17,25,26,29,31,33,35,37,39,40,41,61,82,103,124,145,166,187,208,229,250,271,292,313,334,355,376,397,418,439}, {1,2,3,4,5,6,11,12,13,14,15,16,29,30,31,32,39,40,41,42,43,64,86,108,130,152,174,196,218,240,262,284,306,328,350,372,394,416,438}},

481->{{1,2,3,4,5,6,11,12,13,14,15,16,29,30,31,32,39,40,41,42,43,64,86,108,130,152,174,196,218,240,262,284,306,328,350,372,394,416,438,460}}|>

[Ed Pegg]

However .... 
1^5,6^17,1^6,102,7^5,109,7^5   
This provides a superior solution for 42 stamps, working up to 509.  The best the previous stamps can offer is 503.

 {1, 2, 3, 4, 5, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96, 102, 108, 109, 110, 111, 112, 113, 114, 216, 223, 230, 237, 244, 251, 360, 367, 374, 381, 388, 395}  

Based on https://arxiv.org/pdf/1606.04770 .
At least three more recipes are needed for larger cases.  Probably more.

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/a4ca729e-92db-487d-90cb-7fd12ed0e0dcn%40googlegroups.com.

[Ed Pegg]

Yep, I needed a new stamp, based on  Kløve–Mossige/Kohonen-Example-3 

(* Magenta[t,q]:1^(t-1),t^q,1^t,t q,(t+1)^(t-1),t(q+2)+1,(t+1)^(t-1)
   Number of stamps including 0: 4t+q+1 Range: 4tq+2t^2+6t-1+Boole[t==q] *)
Magenta[t_, q_] :=gapWord[rep[1, t - 1], rep[t, q], rep[1, t], t q,rep[t + 1, t - 1], t (q + 2) + 1, rep[t + 1, t - 1]]

A004129Known = <|
 222 -> {stamp[Zeppelin15[11]]},
 237 -> {stamp[Zeppelin15[12]], stamp[Gronchi16[11]]},
 253 -> {stamp[Gronchi16[12]]},
 269 -> {stamp[Gronchi16[13]], stamp[InvertedJenny[3, 12]]},
 286 -> {stamp[InvertedJenny[3, 13]]},
 303 -> {stamp[InvertedJenny[3, 14]], stamp[RedMercury[4, 13]]},
 321 -> {stamp[RedMercury[4, 14]]},
 339 -> {stamp[RedMercury[4, 15]], stamp[InvertedJenny[4, 14]],
   stamp[Magenta[5, 13]]},
 359 -> {stamp[Magenta[5, 14]]},
 379 -> {stamp[Magenta[5, 15]]},
 399 -> {stamp[Magenta[5, 16]]},
 419 -> {stamp[Magenta[6, 13]]},
 443 -> {stamp[Magenta[6, 14]]},
 467 -> {stamp[Magenta[6, 15]]},
 491 -> {stamp[Magenta[6, 16]]},
 515 -> {stamp[Magenta[6, 17]]},
 539 -> {stamp[Magenta[6, 18]]},
 563 -> {stamp[Magenta[6, 19]]},
 587 -> {stamp[Magenta[7, 16]]},
 615 -> {stamp[Magenta[7, 17]]},
 643 -> {stamp[Magenta[7, 18]]},
 671 -> {stamp[Magenta[7, 19]]},
 699 -> {stamp[Magenta[7, 20]]},
 727 -> {stamp[Magenta[7, 21]]},
 755 -> {stamp[Magenta[7, 22]]},
 783 -> {stamp[Magenta[8, 19]]},
 815 -> {stamp[Magenta[8, 20]]}
 |>;  

[Ed Pegg]

A larger run finds  
A004129(19)≥117.  
{0, 1, 2, 3, 6, 10, 14, 18, 22, 26, 30, 33, 34, 35, 36, 72, 74, 79, 81}  
{1, 1, 1, 3, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 36, 2, 5, 2}  
1^3, 3, 4^6, 3, 1^3, 36, 2, 5, 2  

and also  
{0, 1, 2, 3, 6, 10, 14, 18, 22, 26, 30, 33, 34, 35, 36, 72, 75, 78, 81}  

So I need more stamps.

Sparse rulers were analyzed with a program called Scrunch ... I have a similar program called SumScrunch that found the two solutions above. I'm running it on the value 118 now.