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,2

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

Links

Table of n, a(n) for n=1..51.

Example

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

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 *)

Crossrefs

Cf. A064821, A335048.

Sequence in context: A193684 A308850 A368273 * A048230 A294412 A227017

Adjacent sequences: A335044 A335045 A335046 * A335048 A335049 A335050

Keyword

nonn

Author

Ivan N. Ianakiev, Jun 05 2020

Extensions

More terms from Giovanni Resta, Jun 05 2020

Status

approved