login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A335048 Minimum sum of primes (see Comments). 1
0, 3, 8, 13, 22, 31, 44, 57, 74, 91, 112, 133, 158, 183, 212, 241, 274, 307, 344, 381, 422, 463, 508, 553, 602, 651, 704, 757, 814, 871, 932, 993, 1058, 1123, 1192, 1261, 1334, 1407, 1484, 1561, 1642, 1723, 1808, 1893, 1982, 2071, 2164, 2257, 2354, 2451, 2552 (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 minimum sum of the primes. a(n) is the respective minimum 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 > 1 it is probable that a(n) = n*(n+1) - (n+n-2) if n is odd and a(n) = n*(n+1) - (n+n-1) 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 minimum sum of 13 (5+3+5) is 3214.

MATHEMATICA

p[n_]:=Permutations[Range[n]]; g[n_]:=Min[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]&]]; g/@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 = Reverse@ 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, A335047.

Sequence in context: A212649 A084535 A194427 * A185954 A051838 A076792

Adjacent sequences:  A335045 A335046 A335047 * A335049 A335050 A335051

KEYWORD

nonn

AUTHOR

Ivan N. Ianakiev, Jun 05 2020

EXTENSIONS

More terms from Giovanni Resta, Jun 05 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 28 13:24 EDT 2020. Contains 337393 sequences. (Running on oeis4.)