3
$\begingroup$

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)

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – smci
    Jan 4, 2015 at 21:09
  • 1
    $\begingroup$ Actually it is that sequence. I just wrote a program to check and 157 = 107+29+11+7+3 $\endgroup$
    – smci
    Jan 4, 2015 at 22:23
  • $\begingroup$ OEIS search usually gives helpful inspiration (on arbitrary integer sequences)... $\endgroup$
    – smci
    Jan 4, 2015 at 22:43
  • $\begingroup$ so the definition on A138000 can be restated/replaced by the definition of mine? $\endgroup$
    – Gary B
    Jan 4, 2015 at 23:59
  • $\begingroup$ Apparently. But at first glance I couldn't see how Benkoski and Erdos' statement corresponds to yours. $\endgroup$
    – smci
    Jan 5, 2015 at 5:08

1 Answer 1

2
$\begingroup$

This seems identical to:

OEIS A138000 "Least prime such that the subsets of { a(1),...,a(n) } sum up to 2^n different values." http://oeis.org/A138000

Discovered by S. J. Benkoski and P. Erdos, On weird and pseudoperfect numbers, Math. Comp. 28 (1974) 617-623

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.

$\endgroup$
6
  • $\begingroup$ are you absolutely 100% sure that it is the same sequence? $\endgroup$
    – Gary B
    Jan 4, 2015 at 23:30
  • 1
    $\begingroup$ @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". $\endgroup$
    – Erick Wong
    Jan 4, 2015 at 23:44
  • $\begingroup$ damn,what a coincidence!.thanx Wong. $\endgroup$
    – Gary B
    Jan 4, 2015 at 23:53
  • $\begingroup$ @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(?) $\endgroup$
    – smci
    Jan 5, 2015 at 5:40
  • 1
    $\begingroup$ Then compute the next 20 terms and tell us if they match, for starters. $\endgroup$
    – smci
    Jan 5, 2015 at 17:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .