A335047 Maximum sum of primes (see Comments).

0, 3, 8, 17, 24, 37, 52, 69, 86, 107, 128, 153, 178, 207, 236, 269, 302, 339, 376, 417, 458, 503, 548, 597, 646, 699, 752, 809, 866, 927, 988, 1053, 1118, 1187, 1256, 1329, 1402, 1479, 1556, 1637, 1718, 1803, 1888, 1977, 2066, 2159, 2252, 2349, 2446, 2547, 2648

Offset: 1

Author

Ivan N. Ianakiev, Jun 05 2020

Keywords

• nonn

Comments

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.

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

Examples

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

Crossrefs

Cf. A064821, A335048.

Programs

Mathematica

p[n_]:=Permutations[Range[n]];f[n_]:=Max[Total/@Select[Table[Table[
p[n][[j,i]]+p[n][[j,i+1]],{i,1,Length[p[n][[j]]]-1}],{j,1,Length[p[n]]}],
AllTrue[#,PrimeQ]&]];f/@Range[7] (* slow, just for demo *)
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 *)

Extensions

More terms from Giovanni Resta, Jun 05 2020