The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A138000 a(n) is the least prime such that the subsets of { a(1), ..., a(n) } sum up to 2^n different values. 5


%S 2,3,7,11,29,53,107,211,431,853,1709,3433,6857,13709,27427,54851,

%T 109717,219409,438827,877651,1755319,3510623,7021249,14042491,

%U 28084997,56169977,112339957,224679913,449359829,898719707,1797439359,3594878731,7189757483,14379514973,28759029919

%N a(n) is the least prime such that the subsets of { a(1), ..., a(n) } sum up to 2^n different values.

%C Obviously one must exclude previously used primes. Here this is done by requiring 2^n subsets; equivalently, one could require a(n) to be different from preceding terms, or larger than a(n-1). (If a value smaller than a(n-1) were possible, then a(n-1) would not have been the minimal choice.)

%C If we replace "prime" with "noncomposite", the sequence starts 1, 2, 5, 11, 23, 43, 89, 179, 359, 719, 1433, 2879, ... and seems to coincide with A064934, having a different definition, though.

%C The present sequence clearly (cf. a(4)) would not be the same if the definition were changed to "least prime larger than the sum of preceding terms" (as in A064934).

%C It can be seen that a(n) is always very close to Sum_{i=1..n-1} a(i). As a consequence, the sequence grows like a(n) ~ 2^(n-0.256...) and thus is not a counterexample to Erdős's conjecture mentioned in the cited paper.

%C The sequence of partial sums, s(n) = Sum_{i=1..n} a(i) =

%C (2,5,12,23,52,105,...) is of alternating parity. If s(n)-1 is prime, this is an upper bound for a(n+1), since the smallest element of the sequence is 2; e.g., a(4) = s(3)-1. Thus if s(n) is even, a(n+1) <= nextprime(s(n)-1). If s(n) is odd, then a(n+1) may be nextprime(s(n)+2) (since the value of s(n) itself is never admissible), as in the case of a(3) = 5 + 2 > s(2) = 5, which is prime.

%H S. J. Benkoski and P. Erdős, <a href="http://dx.doi.org/10.1090/S0025-5718-1974-0347726-9">On weird and pseudoperfect numbers</a>, Math. Comp., 28 (1974), pp. 617-623. <a href="http://www.renyi.hu/~p_erdos/1974-24.pdf">Alternate link</a>; <a href="http://dx.doi.org/10.1090/S0025-5718-1975-0360452-6">1975 corrigendum</a>

%F a(n) > a(n-1) and a(n) <= nextprime((Sum_{i=1..n-1} a(i)) - (-1)^n); but in fact a(n) ~ Sum_{i=1..n-1} a(i) and thus a(n) ~ constant*2^n.

%e a(1) = 2, the smallest prime, since subsets of {2} are {},{2} summing to 0 resp. 2.

%e a(2) = 3, the second smallest prime, since subsets

%e {},{2},{3},{2,3} have sums 0, 2, 3, 5 which are all different.

%e Then, 5 is not allowed for a(3), since for {2,3,5}, the sum of the subset {2,3} would be the same as that of {5}.

%e For a(3)=7, however, the set of the previously possible sums, {0,2,3,5} and the set of possible sums using the new element, 7 + {0,2,3,5} = {7,9,10,12} are disjoint.

%e Obviously this is always true for a(n) larger than the sum of all preceding terms.

%e However, a(4) = 11 is smaller than this sum (7 + 3 + 2 = 12), yet {0,2,3,5,7,9,10,12} and 11 + {0,2,3,5,7,9,10,12} are disjoint.

%o (PARI) s=p=1; for( n=1,30, while( bitand(s,s>>p=nextprime(p+1)),); s+=s<<p; print1(p","))

%Y Cf. A064934.

%K nonn,changed

%O 1,1

%A _M. F. Hasler_, Apr 08 2008

%E a(23)-a(30) from _Donovan Johnson_, Feb 18 2009

%E a(31)-a(35) from _Giovanni Resta_, Feb 28 2020

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 17 14:50 EDT 2021. Contains 343972 sequences. (Running on oeis4.)