A368491 - OEIS

%I #44 Feb 05 2024 11:17:15

%S 1,5,45,1453,186285,381681581,3126736191405,409827566090715053,

%T 214867674970568857223085,1802440697199513680253124870061,

%U 967677980931418755473971539884090851245,2078072640579877586820864371518464918573279084461,285608128960093974754528418755948821932657172723113570336685

%N a(n) is the integer whose bits designate the possible subset sums of the first n prime numbers.

%C Bit position 0 (which is sum 0) is the least significant bit of a(n).

%C The resulting binary string is palindromic for all n. A subset sum of zero marks one end of the binary string, while the sum of all n primes marks the other end. Therefore, starting from no primes and adding some and starting from all primes and omitting some correspond to the same pattern. (This is so for any values, not just primes.)

%C It is observed that for an array of primes, for large values of n, the binary string starts with a certain pattern and ends with the reverse of this certain pattern and consists of all ones in the middle area.

%F a(n) = a(n-1) BITOR a(n-1)*2^prime(n).

%F a(n) = 91*2^(A007504(n)-6) - 83 for n > 3.

%e For n = 0, there are no terms from which to calculate a subset sum. An empty array gives zero as the only possible sum. This is designated by the binary string 1 which has a value of 1 in base 10.

%e For n = 2, sums of 0,2,3,5 are possible, yielding a binary string of 101101, which has a value of 45 in base 10. The impossibility of sums 1 and 4 is indicated by 0's in the binary string.

%e For n = 3, the primes are 2,3,5 and their subset sums 0, 2, 3, 5, 7, 8, 10 are the positions of 1 bits in a(3) = 1453,

%e        10   8 7   5   3 2   0   bit positions

%e a(n) =  1 0 1 1 0 1 0 1 1 0 1   binary

%o (Python)

%o from primesieve import *

%o n = 20

%o ps = generate_n_primes(n)

%o res = 1

%o a = []

%o a.append(res)

%o for v in ps:

%o   res = (res | (res << v))

%o   a.append(res)

%o print(a)

%Y Cf. A000040, A082548 (number of sums), A007504 (see formula).

%K base,nonn

%O 0,2

%A _Yigit Oktar_, Dec 27 2023