login
Lexicographically earliest prime pyramid, read by rows.
11

%I #41 Mar 07 2017 09:45:41

%S 1,1,2,1,2,3,1,2,3,4,1,4,3,2,5,1,4,3,2,5,6,1,4,3,2,5,6,7,1,2,3,4,7,6,

%T 5,8,1,2,3,4,7,6,5,8,9,1,2,3,4,7,6,5,8,9,10,1,2,3,4,7,10,9,8,5,6,11,1,

%U 2,3,4,7,10,9,8,5,6,11,12,1,2,3,4,7,6,5,12,11,8,9,10,13,1,2,3,4,7,6,13,10

%N Lexicographically earliest prime pyramid, read by rows.

%C Row n begins with 1, ends with n and sum of any two adjacent entries is prime.

%C From _Daniel Forgues_, May 17 2011 and May 18 2011: (Start)

%C Since the sum of any two adjacent entries is at least 3, the sum is an odd prime, which implies that any two consecutive entries have opposite parity.

%C Since the first and last entries of row n are fixed at 1 and n, we have to find n-2 entries, where ceiling((n-2)/2) of them are even and floor((n-2)/2) are odd, so for row n the number of possible arrangements is

%C (ceiling((n-2)/2))! * (floor((n-2)/2))! (Cf. A010551(n-2), n >= 2.)

%C The number of ways of arranging row n to get a prime pyramid is given by A036440. List them in lexicographic order and pick the first (earliest) to get row n of lexicographically earliest prime pyramid.

%C Prime pyramids are also (more fittingly?) called prime triangles. (End)

%C It appears that the limit of the rows of the lexicographically earliest prime pyramid is A055265 (see comment in that sequence).

%C Assuming Dickson's conjecture (or the later Hardy-Littlewood Conjecture B), no backtracking is needed: if the first n-2 elements in each row are chosen greedily, a penultimate member can be chosen such that its sums are prime. - _Charles R Greathouse IV_, May 18 2011

%D R. K. Guy, Unsolved Problems Number Theory, Section C1.

%H T. D. Noe, <a href="/A051237/b051237.txt">Rows n=1..100 of triangle, flattened</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimeTriangle.html">Prime Triangle</a>

%H OEIS Wiki, <a href="/wiki/Prime_triangles">Prime triangles</a>

%e Triangle begins:

%e 1;

%e 1, 2;

%e 1, 2, 3;

%e 1, 2, 3, 4;

%e 1, 4, 3, 2, 5;

%e 1, 4, 3, 2, 5, 6;

%e 1, 4, 3, 2, 5, 6, 7;

%e 1, 2, 3, 4, 7, 6, 5, 8;

%e 1, 2, 3, 4, 7, 6, 5, 8, 9;

%e 1, 2, 3, 4, 7, 6, 5, 8, 9, 10;

%e 1, 2, 3, 4, 7, 10, 9, 8, 5, 6, 11;

%e 1, 2, 3, 4, 7, 10, 9, 8, 5, 6, 11, 12;

%e 1, 2, 3, 4, 7, 6, 5, 12, 11, 8, 9, 10, 13;

%t (* first do *) Needs["Combinatorica`"] (* then *) f[n_] := Block[{r = Range@ n}, While[ Union[ PrimeQ[ Plus @@@ Partition[r, 2, 1]]][[1]] == False, r = NextPermutation@ r]; r]; f[1] = 1; Array[f, 13] // Flatten (* _Robert G. Wilson v_ *)

%Y See A187869 for the concatenation of the numbers for each row.

%Y Cf. A036440, A051239, A055265.

%K tabl,nice,nonn,easy

%O 1,3

%A _N. J. A. Sloane_

%E More terms from _Jud McCranie_