login
Number of sums prime(i) + prime(j) that occur more than once for 1 <= i <= j <= n, where prime(k) = k-th prime.
2

%I #19 Mar 05 2023 21:29:07

%S 0,0,0,1,2,4,7,11,16,22,27,34,41,51,61,73,86,96,110,124,140,158,175,

%T 193,211,231,252,275,299,325,348,374,401,427,456,486,516,549,581,615,

%U 650,684,722,759,798,839,879,921,961,1005,1048,1095,1142,1189,1238

%N Number of sums prime(i) + prime(j) that occur more than once for 1 <= i <= j <= n, where prime(k) = k-th prime.

%e Let P(n) = {2, 3, .., p_n} be the set of the first n primes. Construct S(n) = {p+q : p,q in P}. If every sum p+q were distinct, then |S(n)| would be n*(n+1)/2 = A000217(n). But in reality, for n >= 4, certain sums occur more than once. a(n) is the count of repeated values. For example, P(6) = {2, 3, 5, 7, 11, 13} yields S(6) = {4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26}, but 4 sums arise more than once: 10 = 3+7 = 5+5, 14 = 3+11 = 7+7, 16 = 3+13 = 5+11, 18 = 5+13 = 7+11. Thus, a(6) = 4 = A000217(n) - |S(6)|.

%t f[x_] := Prime[x] t1=Table[Length[Union[Flatten[Table[f[u]+f[w], {w, 1, m}, {u, 1, m}]]]], {m, 1, 75}] t=Table[(w*(w+1)/2)-Part[t1, w], {w, 1, 75}]

%Y Cf. A000217, A061781.

%K nonn

%O 1,5

%A _Labos Elemer_, Jun 22 2001