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$
  • 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 '15 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 '15 at 22:23
  • $\begingroup$ OEIS search usually gives helpful inspiration (on arbitrary integer sequences)... $\endgroup$ – smci Jan 4 '15 at 22:43
  • $\begingroup$ so the definition on A138000 can be restated/replaced by the definition of mine? $\endgroup$ – Gary B Jan 4 '15 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 '15 at 5:08
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$
  • $\begingroup$ are you absolutely 100% sure that it is the same sequence? $\endgroup$ – Gary B Jan 4 '15 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 '15 at 23:44
  • $\begingroup$ damn,what a coincidence!.thanx Wong. $\endgroup$ – Gary B Jan 4 '15 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 '15 at 5:40
  • 1
    $\begingroup$ Then compute the next 20 terms and tell us if they match, for starters. $\endgroup$ – smci Jan 5 '15 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.