Call the following a NON additive-subtractive prime sequence or lets name it Gary's sequence. It goes like this: let a(0)=2. The next term is defined as smallest prime number which cannot be expressed as the sum and/or difference of any previous terms (note that it means using any combination of plus and minus signs and any number of previous terms).

The sequence begins: 2, 3, 7, 11, 29, 53, 107,... this sequence is infinite.

My question is:

Can you describe the behavior of this sequence or maybe you can even create a formula for generating this?

(Remember you are allowed to use each prime exactly once and repetition like 2+2+3+7+11 is absolutely not allowed). For example, 17 is not a member of this sequence because 17 can be expressed as 11+2+7-3 . Also 83 is not a member of this sequence since 83 can be expressed as 11+29-3-7+53 . Also 47 is not a member of this sequence because 47 can be expressed as 29+7+11)

• Interesting. The first 7 terms are similar to OEIS A138000 "Least prime such that the subsets of { a(1),...,a(n) } sum up to 2^n different values.", discovered by S. J. Benkoski and P. Erdos, On weird and pseudoperfect numbers, Math. Comp. 28 (1974) 617-623. – smci Jan 4 '15 at 21:09
• Actually it is that sequence. I just wrote a program to check and 157 = 107+29+11+7+3 – smci Jan 4 '15 at 22:23
• OEIS search usually gives helpful inspiration (on arbitrary integer sequences)... – smci Jan 4 '15 at 22:43
• so the definition on A138000 can be restated/replaced by the definition of mine? – Gary B Jan 4 '15 at 23:59
• Apparently. But at first glance I couldn't see how Benkoski and Erdos' statement corresponds to yours. – smci Jan 5 '15 at 5:08

This seems identical to:

You're following in the footsteps of giants ;-)

Your next term should be a(8) = 211 (not 157 = 107+29+11+7+3)

As to the closed-form, OEIS says:

a(n) > a(n-1) and a(n) <= nextprime(sum(a(i),i=1..n-1)-(-1)^n) ; but in fact a(n) ~ sum(a(i),i=1..n-1)

and thus a(n) ~ constant*2^n

where constant >~ 1.6739958...

It's probably safest to define a(n) using nearestprime() rather than nextprime(), to avoid precision issues for large n.

As to the name, Benkoski and Erdos didn't give this sequence a name... but I don't think you can call it Gary's sequence.

• are you absolutely 100% sure that it is the same sequence? – Gary B Jan 4 '15 at 23:30
• @GaryB Yes, have you tried proving it yourself? It boils down to showing that "all subsets have distinct sums" is equivalent to "each term cannot be expressed as a sum/difference of previous terms". – Erick Wong Jan 4 '15 at 23:44
• damn,what a coincidence!.thanx Wong. – Gary B Jan 4 '15 at 23:53
• @ErickWong it is equivalent if the subsets are disjoint, even when a(n) < sum of all preceding a(i), which I think they say in OEIS you can prove inductively(?) – smci Jan 5 '15 at 5:40
• Then compute the next 20 terms and tell us if they match, for starters. – smci Jan 5 '15 at 17:20