Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%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