cp's OEIS Frontend

A036440 Number of ways of arranging row n of the prime pyramid.

%I A036440 #40 Feb 16 2025 08:32:37
%S A036440 1,1,1,1,1,1,2,4,7,24,80,216,648,1304,3392,13808,59448,155464,480728,
%T A036440 1588162,5626309,28279112,157469880,842498189,4998554801,28466978744,
%U A036440 166572523589,1020487969891,5753385660978
%N A036440 Number of ways of arranging row n of the prime pyramid.
%C A036440 Number of ways to arrange numbers from 1 to n in a row, starting with 1 and ending with n, such that the sum of every two adjacent numbers is prime.
%C A036440 From _Daniel Forgues_, May 18 2011: (Start)
%C A036440 Since the sum of any two adjacent entries is at least 3, the sum is thus an odd prime, which implies that any two consecutive entries have opposite parity. Since the first and last entries of row n are fixed to 1 and n, we have to find n-2 entries, where ceiling((n-2)/2) are even and floor((n-2)/2) are odd, so for row n the number of arrangements to investigate is
%C A036440     (ceiling((n-2)/2))! * (floor((n-2)/2))!   (Cf. A010551(n-2), n >= 2.)
%C A036440 Prime pyramids are also (more fittingly?) called prime triangles. (End)
%D A036440 R. K. Guy, Unsolved Problems Number Theory, C1.
%H A036440 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeTriangle.html">Prime Triangle</a>.
%e A036440 a(8)=4 because of the 720 permutations P of {1,2,3,4,5,6,7,8} with first element 1 and last element 8, these four satisfy the "prime pyramid" condition that P[i] + P[i+1] be prime for i=1..7:
%e A036440   1 2 3 4 7 6 5 8; (lexicographically earliest row 8)
%e A036440   1 2 5 6 7 4 3 8;
%e A036440   1 4 7 6 5 2 3 8;
%e A036440   1 6 7 4 3 2 5 8.
%e A036440 For row 8, there are 6! = 720 permutations of {2,3,4,5,6}, but if we take into account that the parity of all entries of row n must alternate, we only have to consider ceiling((8-2)/2)! * floor((8-2)/2)! = 36 cases.
%t A036440 prsQ[n_]:=AllTrue[Total/@Partition[n,2,1],PrimeQ]; Table[Count[Join[{1},#,{n}]&/@ Permutations[ Range[2,n-1]],_?prsQ],{n,12}] (* _Harvey P. Dale_, May 07 2023 *)
%Y A036440 Cf. A051237 for lexicographically earliest prime pyramid.
%K A036440 nonn,nice
%O A036440 1,7
%A A036440 _John W. Layman_
%E A036440 More terms from _Jud McCranie_
%E A036440 a(25)-a(27) from _Max Alekseyev_, Jan 05 2008
%E A036440 a(28)-a(29) from _Giovanni Resta_, Apr 01 2014