login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Maximum sum of primes (see Comments).
1

%I #8 Jul 14 2020 23:47:52

%S 0,3,8,17,24,37,52,69,86,107,128,153,178,207,236,269,302,339,376,417,

%T 458,503,548,597,646,699,752,809,866,927,988,1053,1118,1187,1256,1329,

%U 1402,1479,1556,1637,1718,1803,1888,1977,2066,2159,2252,2349,2446,2547,2648

%N Maximum sum of primes (see Comments).

%C Out of all permutations of the numbers 1..n such that the sum of all adjacent numbers is a prime (A064821) find the one with the maximum sum of the primes. a(n) is the respective maximum sum or equals zero if a permutation does not exist.

%C The sum of primes arising from a permutation of 1..n is always equal to n*(n+1) minus the values of the two endpoints, so for n > 6 it is probable that a(n) = n*(n+1) - (1+3) if n is odd and a(n) = n*(n+1) - (1+2) if n is even. - _Giovanni Resta_, Jun 05 2020

%e For n = 4 there are 4 permutations: 1234, 1432, 3214, 3412. The one with the maximum sum of 17 (5+7+5) is 1432.

%t p[n_]:=Permutations[Range[n]];f[n_]:=Max[Total/@Select[Table[Table[

%t p[n][[j,i]]+p[n][[j,i+1]],{i,1,Length[p[n][[j]]]-1}],{j,1,Length[p[n]]}],

%t AllTrue[#,PrimeQ]&]];f/@Range[7] (* slow, just for demo *)

%t G[n_] := G[n] = Reap[Do[If[PrimeQ[i + j], Sow[i <-> j]], {i, n}, {j, i-1}]][[2, 1]]; a[n_] := Block[{p = 1 + Boole@ OddQ@ n, ep, s}, ep = SortBy[ Select[ Tuples[ Range[1, n, p], 2], #[[1]] > #[[2]] &], Total]; s = SelectFirst[ ep, FindHamiltonianPath[ G[n], #[[1]], #[[2]]] != {} &, {}]; If[s == {}, 0, n (n + 1) - Total[s]]]; Array[a, 51] (* _Giovanni Resta_, Jun 05 2020 *)

%Y Cf. A064821, A335048.

%K nonn

%O 1,2

%A _Ivan N. Ianakiev_, Jun 05 2020

%E More terms from _Giovanni Resta_, Jun 05 2020