A123509 -id:A123509 - cp's OEIS frontend

A001212 a(n) = solution to the postage stamp problem with n denominations and 2 stamps.

2, 4, 8, 12, 16, 20, 26, 32, 40, 46, 54, 64, 72, 80, 92, 104, 116, 128, 140, 152, 164, 180, 196, 212

Offset: 1

Fred Lunnon [W. F. Lunnon] defines "solution" to be the smallest value not obtainable by the best set of stamps. The solutions given are one lower than this, that is, the sequence gives the largest number obtainable without a break using the best set of stamps.

a(20)=152: There is only one set of 20 denominations covering all sums through 152: {1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 50, 56, 62, 68, 71, 72, 73, 75, 76}. - Tim Peters (tim.one(AT)comcast.net), Oct 04 2006

Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, p. 115 (Coins of the Realm), 1984.
R. K. Guy, Unsolved Problems in Number Theory, C12.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. Alter, Letter to N. J. A. Sloane, Mar 25 1977
R. Alter and J. A. Barnett, A postage stamp problem, Amer. Math. Monthly, 87 (1980), 206-210.
M. F. Challis, Two new techniques for computing extremal h-bases A_k, Comp J 36(2) (1993) 117-126
M. F. Challis and J. P. Robinson, Some Extremal Postage Stamp Bases, J. Integer Seq., 13 (2010), Article 10.2.3.
Erich Friedman, Postage stamp problem
R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs, SIAM J. Algebraic and Discrete Methods, 1 (1980), 382-404.
R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs
F. H. Kierstead, Jr.,, The Stamp Problem, J. Rec. Math., Vol. ?, Year ?, page 298. [Annotated and scanned copy]
J. Kohonen, A meet-in-the-middle algorithm for finding extremal restricted additive 2-bases, arXiv preprint arXiv:1403.5945, 2014 and J. Int. Seq. 17 (2014) # 14.6.8.
J. Kohonen, J. Corander, Addition Chains Meet Postage Stamps: Reducing the Number of Multiplications, J. Integer Seq., 17 (2014), Article 14.3.4.
J. Kohonen, Early Pruning in the Restricted Postage Stamp Problem, arXiv preprint arXiv:1503.03416, 2015
W. F. Lunnon, A postage stamp problem, Comput. J. 12 (1969) 377-380.
W. F. Lunnon, A postage stamp problem [Annotated scanned copy]
J. P. Robinson, Some postage stamp 2-bases, JIS 12 (2009) 09.1.1.
E. S. Selmer, Letter to N. J. A. Sloane, Sep 10 1991
Eric Weisstein's World of Mathematics, Postage stamp problem
Mingjia Yang, An experimental walk in patterns, partitions, and words, Ph. D. Dissertation, Rutgers University (2020).

Postage stamp sequences: A001208 A001209 A001210 A001211 A001212 A001213 A001214 A001215 A001216 A005342 A005343 A005344 A014616 A053346 A053348 A075060 A084192 A084193
Cf. A006638, A123509.
Equals A196094(n) - 1 and A234941(n+1)-2.
A row or column of the array A196416 (possibly with 1 subtracted from it).

Corrected a(17). Added a(18) and a(19) from Challis. - R. J. Mathar, Apr 01 2006
Entry improved by comments from John Seldon (johnseldon(AT)onetel.com), Sep 15 2004
a(20) from Tim Peters (tim.one(AT)comcast.net), Oct 04 2006
Added terms a(21) and a(22) from Challis and Robinson. John P Robinson (john-robinson(AT)uiowa.edu), Feb 19 2010
Added term a(23) from Challis and Robinson's July 2013 addendum, by Jukka Kohonen, Oct 25 2013
Added a(24) from Kohonen and Corander (2013). - N. J. A. Sloane, Jan 08 2014

A008932 Number of increasing sequences of Goldbach type of length n; a(0) = 1 by convention.

Original entry on oeis.org

1, 1, 2, 5, 17, 65, 292, 1434, 7875, 47098, 305226, 2122983, 15752080, 124015310, 1031857395, 9041908204, 83186138212, 801235247145, 8059220936672, 84463182889321

Offset: 0

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)

From David S. Newman, Feb 17 2009: (Start)
This sequence also arises in the following way.
Call a set A of nonnegative integers a basis if every nonnegative integer can be written as the sum of two (not necessarily distinct) elements of A.
Call a basis an increasing basis if its elements are arranged in increasing order, a0 < a1 < a2 < ...
For example, A126684: 0, 1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, ... is an increasing basis.
Now consider the set of all initial subsequences of any length {a0, a1, a2,...,an} of all the increasing bases.
These can be arranged in lexicographic order, giving:
  0
  0, 1
  0, 1, 2
  0, 1, 3
  0, 1, 2, 3
  0, 1, 2, 4
  0, 1, 2, 5
  0, 1, 3, 4
  0, 1, 3, 5
  ...
How many such subsequences are there of length n? (End)
The answer is a(n-1), or a(n) if "length n" ignores the initial zero. A Goldbach sequence is then an increasing basis with each element increased by 1. - [Corrected by Martin Fuller, Apr 28 2025]
The largest value for each term in any increasing basis is given by A123509. - Martin Fuller, Jun 01 2010

M. Torelli, Increasing integer sequences and Goldbach's conjecture, preprint, 1996.

M. Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121.
Index entries for sequences related to Goldbach conjecture

Cf. A123509.

A008932(n,pol=0)= { local(a=0, i, pol2);
!n && return(1);
i = #pol;
pol2 = pol^2;
for (i=#pol, #pol2+1,
a += A008932(n-1, pol+'x^i);
!polcoeff(pol2,i) && break;);
a } \\ Martin Fuller, Jun 01 2010

a(9)-a(14) from Martin Fuller, Feb 18 2009
Edited by N. J. A. Sloane, Mar 12 2009
a(15)-a(16) from Sean A. Irvine, Apr 19 2018
a(17)-a(19) from Martin Fuller, Apr 30 2025

A196094 a(0) = 1; a(n) = A001212(n) + 1 for n > 0.

Original entry on oeis.org

1, 3, 5, 9, 13, 17, 21, 27, 33, 41, 47, 55, 65, 73, 81, 93, 105, 117, 129, 141, 153, 165, 181, 197, 213

Offset: 0

N. J. A. Sloane, Sep 27 2011

Lunnon sometimes works with this sequence rather than A001212. A001212 is the main entry.

J. Kohonen, J. Corander, Addition Chains Meet Postage Stamps: Reducing the Number of Multiplications, arXiv preprint arXiv:1310.7090 [math.NT], 2013-2014.
W. F. Lunnon, A postage stamp problem, Comput. J. 12 (1969) 377-380.

Cf. A001212, A123509, A234941.

Row m=2 of the array A196416.

Definition amended by Georg Fischer, Jan 25 2020

A193258 Sprimes: A sparse prime-like set of numbers that are constructed recursively to satisfy a Goldbach-type conjecture.

Original entry on oeis.org

1, 3, 7, 11, 13, 27, 31, 35, 49, 61, 77, 79, 93, 101, 115, 117, 133, 163, 183, 187, 193, 235, 245, 257, 271, 279, 323, 335, 343, 381, 399, 439, 481, 497, 507, 535, 549, 569, 619, 669, 681, 693, 713, 739, 815, 833, 863, 905, 941, 973, 1033, 1053, 1089, 1119

Offset: 1

Ian R Harris, Aug 26 2011

nonn

Closely related to A123509, and the concept of a "basis". A key difference is that the set described here can only generate even numbers, and 0 is not allowed in the set.

			a(1)=1.
Note that S1={1}, so A={1}.
Now m=min{N\A}=2.
Thus C1={3} (amongst the natural numbers only 3 can be added to 1 to give 4).
Since 3 is the only candidate, a(2)=3.
To get a(3), we repeat steps 2) to 6).
So, S2={1,3}, A={1,2,3}, m=min{N\A}=4.
Thus the candidate set is C2={5,7} (we can add 5 to 3 to get 8, or 7 to 1 to get 8).
Then w5=|({(5+1)/2, (5+3)/2} union{5}) intersect {4,5,6,7,8,9,10,...}|=|{4,5}|=2.
And w7=|({(7+1)/2, (7+3)/2} union {7}) intersect {4,5,6,7,8,9,10,11,12,13,14,...}|=|{4,5,7}|=3.
Since of the two candidates, 7 has the higher worth, then a(3)=7.

Ian R Harris, Technical report

Cf. A000040, A008578, A000959, A123509, A126684, A008932.

@cached_function
def A193258(n):
    if n == 1: return 1
    S = set(A193258(i) for i in [1..n-1])
    A = set((i+j)/2 for i, j in cartesian_product([S, S]))
    m = next(i for i in PositiveIntegers() if i not in A)
    C = set(2*m-i for i in S if 2*m-i > A193258(n-1))
    worthfn = lambda c: len(set((c+i)/2 for i in S).difference(A))
    wc = sorted(list((worthfn(c), c) for c in C)) # sort by worth and by c
    return wc[-1][1]
# D. S. McNeil, Aug 29 2011

The set of numbers S is chosen to satisfy the Goldbach conjecture. That is any even positive number must be able to be written as the sum of exactly two members of S (typically there are multiple ways to do this). The members of the set are generated by a deterministic recursive algorithm as follows (N is the set of positive integers):
1) a(1)=1
2) Given Sk={a(1),...,a(k)}, form the set A={n in N | exists a(i), a(j) in Sk, (a(i)+a(j))=2n}.
3) Let m=min{N\A}. (Then 2m is the smallest positive even number which cannot be formed from sums of the current finite list of sprimes.)
4) Define candidate set Ck={n in \N| n > a(k), exists a(i) in Sk such that a(i)+n=2m}. (This is a set of possible choices for a(k+1).)
5) To each member of Ck, assign "worth" wi=|({(i+a(j))/2| a(j) in Sk} union {i}) intersect {N\A}|. (This assigns to each candidate a worth equal to the number of new values that will be added to set A if the candidate is added to Sk.)
6) a(k+1)=max{i in Ck | wi=maximum (over {j in Ck}) (wj)}.
Repeat steps 2) to 6).

A302648 a(n) is the largest integer b_n such that there exists a set of n integers b_1=0, b_2, ..., b_n whose pairwise sums cover all integers between 0 and 2*b_n.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 10, 13, 16, 20, 22, 27, 32, 36, 40, 46, 52, 58, 64, 70, 76, 82, 90, 98, 106, 114, 122, 131

Offset: 1

Zhao Hui Du, Apr 11 2018

All known terms satisfy a(n) = (A123509(n) - 1)/2 except for n=11, where A123509(11) = 47 but the corresponding item in this array is 22.
Enumerating all sequences corresponding to A123509(11)=47, we found the solutions are (0 1 2 3 7 11 15 19 21 22 24) and (0 1 2 5 7 11 15 19 21 22 24), and none of them satisfy this problem.
For most solutions of the problem, the differences between adjacent items are symmetric, and one of the differences is repeated multiple times in the middle of the difference array. E.g., for n=23 we have 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 75 77 80 84 86 87 89 90 with differences {1 2 1 2 4 3 2 6 8 8 8 8 8 8 6 2 3 4 2 1 2 1}.
Using this property, we find that a(29) >= 140, a(30) >= 149, a(31) >= 158, a(32) >= 168, a(33) >= 178, a(34) >= 188.

			   3: 0 1 2
   4: 0 1 3 4
   5: 0 1 3 5 6
   6: 0 1 3 5 7 8
   7: 0 1 2 5 8 9 10
   8: 0 1 3 4 9 10 12 13
   9: 0 1 2 5 8 11 14 15 16
  10: 0 1 3 4 9 11 16 17 19 20
  11: 0 1 3 4 6 11 13 18 19 21 22
  12: 0 1 3 5 6 13 14 21 22 24 26 27
  13: 0 1 3 4 9 11 16 21 23 28 29 31 32
  14: 0 1 3 4 9 11 16 20 25 27 32 33 35 36
  15: 0 1 3 4 5 8 14 20 26 32 35 36 37 39 40
  16: 0 1 3 4 5 8 14 20 26 32 38 41 42 43 45 46
  17: 0 1 3 4 5 8 14 20 26 32 38 44 47 48 49 51 52
  18: 0 1 3 4 5 8 14 20 26 32 38 44 50 53 54 55 57 58
  19: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 59 60 61 63 64
  20: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 65 66 67 69 70
  21: 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 68 71 72 73 75 76
  22: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 67 69 72 76 78 79 81 82
  23: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 75 77 80 84 86 87 89 90
  24: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 83 85 88 92 94 95 97 98
  25: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 85 91 93 96 100 102 103 105 106
  26: 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 85 93 99 101 104 108 110 111 113 114

Cf. A123509.

/* C code to generate first part of the sets --
change K to larger value to generate more sets */
#include 
#include 
#include 
#ifndef K
#define K 8
#endif
#ifndef R
#define R 1
#endif
#define UPBOUND 40960
unsigned short data[K+R];
unsigned short sumbuf[UPBOUND];
unsigned short diffbuf[UPBOUND];
unsigned short modbuf[K];
int rcount;
int level;
int next_sum,next_diff;
int cur_best=10000000;
void output()
{
    int i,j;
    int b=data[level-1]+K;
    int tindex=1;
    for(i=b;i=data[j]&&(h-data[j])%K==0){
                  min_index=(h-data[j])/K;
              }
           }
           if(min_index<0)return;
           if(min_index>tindex)tindex=min_index;
       }
    }
    for(i=0;itindex)tindex=min_index;
       }
    }
    if(K*(level-1)-data[level-1]<=cur_best){
       cur_best=K*(level-1)-data[level-1];
       printf("%d,>=%d | ",K*(level-1)-data[level-1],tindex);
       for(i=0;i0){
        if(rcount>=R)return 0;
        rcount++;
    }
    modbuf[r]++;
    for(i=0;i0){
       rcount--;
    }
    sumbuf[x+x]--;diffbuf[0]--;
    for(i=0;i=K&&data[level-1]+K<=next_sum){
        output();
    }
    for(i=startv;i<=next_sum&&i<=K-1+data[level-1];++i){
        if(push(i)){
            search(i+1);
            pop();
        }
    }
}
int main()
{
    data[0]=0;data[1]=1;
    sumbuf[0]=sumbuf[1]=sumbuf[2]=1;rcount=0;
    diffbuf[0]=2;diffbuf[1]=1;next_diff=2;
    next_sum = 3;
    level=2;
    search( 2);
}

a(n) <= (A123509(n) - 1)/2.

cp's OEIS Frontend

A001212 a(n) = solution to the postage stamp problem with n denominations and 2 stamps.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A008932 Number of increasing sequences of Goldbach type of length n; a(0) = 1 by convention.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A196094 a(0) = 1; a(n) = A001212(n) + 1 for n > 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A193258 Sprimes: A sparse prime-like set of numbers that are constructed recursively to satisfy a Goldbach-type conjecture.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Formula

A302648 a(n) is the largest integer b_n such that there exists a set of n integers b_1=0, b_2, ..., b_n whose pairwise sums cover all integers between 0 and 2*b_n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

C

Formula