|
| |
|
|
A335047
|
|
Maximum sum of primes (see Comments).
|
|
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
