A051239 -id:A051239 - cp's OEIS frontend

A055265 a(n) is the smallest positive integer not already in the sequence such that a(n)+a(n-1) is prime, starting with a(1)=1.

1, 2, 3, 4, 7, 6, 5, 8, 9, 10, 13, 16, 15, 14, 17, 12, 11, 18, 19, 22, 21, 20, 23, 24, 29, 30, 31, 28, 25, 34, 27, 26, 33, 38, 35, 32, 39, 40, 43, 36, 37, 42, 41, 48, 49, 52, 45, 44, 53, 50, 47, 54, 55, 46, 51, 56, 57, 70, 61, 66, 65, 62, 69, 58, 73, 64, 63, 68, 59, 72, 67, 60

Offset: 1

Henry Bottomley, May 09 2000

The sequence is well-defined (the terms must alternate in parity, and by Dirichlet's theorem a(n+1) always exists). - N. J. A. Sloane, Mar 07 2017
Does every positive integer eventually occur? - Dmitry Kamenetsky, May 27 2009. Reply from Robert G. Wilson v, May 27 2009: The answer is almost certainly yes, on probabilistic grounds.
It appears that this is the limit of the rows of A051237. That those rows do approach a limit seems certain, and given that that limit exists, that this sequence is the limit seems even more likely, but no proof is known for either conjecture. - Robert G. Wilson v, Mar 11 2011, edited by Franklin T. Adams-Watters, Mar 17 2011
The sequence is also a particular case of "among the pairwise sums of any M consecutive terms, N are prime", with M = 2, N = 1. For other M, N see A055266 & A253074 (M = 2, N = 0), A329333, A329405 - A329416, A329449 - A329456, A329563 - A329581, and the OEIS Wiki page. - M. F. Hasler, Feb 11 2020

			a(5) = 7 because 1, 2, 3 and 4 have already been used and neither 4 + 5 = 9 nor 4 + 6 = 10 are prime while 4 + 7 = 11 is prime.

Zak Seidov, Table of n, a(n) for n = 1..10000 (First 1000 terms from T. D. Noe)
N. J. A. Sloane, Table of n, a(n) for n = 1..100000 (computed using Orlovsky's Mma program)
M. F. Hasler, Prime sums from neighboring terms, OEIS Wiki, Nov. 23, 2019
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A117922; fixed points: A117925; A117923=a(a(n)). - Reinhard Zumkeller, Apr 03 2006
Cf. A036440, A051237, A051239, A055266, A088643. A010051.
Cf. A086527 (the primes a(n)+a(n-1)).
Cf. A070942 (n's such that a(1..n) is a permutation of (1..n)). - Zak Seidov, Oct 19 2011
See also A076990, A243625.
See A282695 for deviation from identity sequence.
A073659 is a version where the partial sums must be primes.

import Data.List (delete)
a055265 n = a055265_list !! (n-1)
a055265_list = 1 : f 1 [2..] where
   f x vs = g vs where
     g (w:ws) = if a010051 (x + w) == 1
                   then w : f w (delete w vs) else g ws
-- Reinhard Zumkeller, Feb 14 2013

A055265 := proc(n)
    local a,i,known ;
    option remember;
    if n =1 then
        1;
    else
        for a from 1 do
            known := false;
            for i from 1 to n-1 do
                if procname(i) = a then
                    known := true;
                    break;
                end if;
            end do:
            if not known and isprime(procname(n-1)+a) then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A055265(n),n=1..100) ; # R. J. Mathar, Feb 25 2017

f[s_List] := Block[{k = 1, a = s[[ -1]]}, While[ MemberQ[s, k] || ! PrimeQ[a + k], k++ ]; Append[s, k]]; Nest[f, {1}, 71] (* Robert G. Wilson v, May 27 2009 *)
q=2000; a={1}; z=Range[2,2*q]; While[Length[z]>q-1, k=1; While[!PrimeQ[z[[k]]+Last[a]], k++]; AppendTo[a,z[[k]]]; z=Delete[z,k]]; Print[a] (*200 times faster*) (* Vladimir Joseph Stephan Orlovsky, May 03 2011 *)

v=[1];n=1;while(n<50,if(isprime(v[#v]+n)&&!vecsearch(vecsort(v),n), v=concat(v,n);n=0);n++);v \\ Derek Orr, Jun 01 2015

U=-a=1; vector(100,k, k=valuation(1+U+=1<M. F. Hasler, Feb 11 2020

a(2n-1) = A128280(2n-1) - 1, a(2n) = A128280(2n) + 1, for all n >= 1. - M. F. Hasler, Feb 11 2020

Corrected by Hans Havermann, Sep 24 2002

A051237 Lexicographically earliest prime pyramid, read by rows.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

Row n begins with 1, ends with n and sum of any two adjacent entries is prime.
From Daniel Forgues, May 17 2011 and May 18 2011: (Start)
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.
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
  (ceiling((n-2)/2))! * (floor((n-2)/2))! (Cf. A010551(n-2), n >= 2.)
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.
Prime pyramids are also (more fittingly?) called prime triangles. (End)
It appears that the limit of the rows of the lexicographically earliest prime pyramid is A055265 (see comment in that sequence).
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

			Triangle begins:
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, 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, 2, 3, 4, 7, 10, 9, 8, 5, 6, 11, 12;
1, 2, 3, 4, 7, 6, 5, 12, 11, 8, 9, 10, 13;

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

T. D. Noe, Rows n=1..100 of triangle, flattened
Eric Weisstein's World of Mathematics, Prime Triangle
OEIS Wiki, Prime triangles

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

Cf. A036440, A051239, A055265.

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

More terms from Jud McCranie

A103839 Number of permutations of (1,2,3,...,n) where each of the (n-1) adjacent pairs of elements sums to a prime.

Original entry on oeis.org

1, 2, 2, 8, 4, 16, 24, 60, 140, 1328, 2144, 17536, 23296, 74216, 191544, 2119632, 4094976, 24223424, 45604056, 241559918, 675603568, 8723487720, 22850057800, 285146572432, 859834538938, 8276479696196, 32343039694056, 429691823372130

Offset: 1

N. J. A. Sloane, Mar 30 2005

nonn

The number of Hamiltonian paths in a graph of which the nodes represent the numbers (1,2,3,...,n) and the edges connect each pair of nodes that add up to a prime. - Bob Andriesse, Oct 04 2020

While A076220(n) > a(n) for 2A076220(n) / a(n) < A076220(n-1) / a(n-1). - Bob Andriesse, Dec 05 2023

			For n = 5, we have the 4 permutations and the sums of adjacent elements:
1,4,3,2,5 (1+4=5, 4+3=7, 3+2=5, 2+5=7)
3,4,1,2,5 (3+4=7, 4+1=5, 1+2=3, 2+5=7)
5,2,1,4,3 (5+2=7, 2+1=3, 1+4=5, 4+3=7)
5,2,3,4,1 (5+2=7, 2+3=5, 3+4=7, 4+1=5)

Cf. A051239, A051252.

A103839[n_] := Count[Map[lpf, Permutations[Range[n]]], 0]
lpf[x_] := Length[Select[asf[x], ! PrimeQ[#] &]];
asf[x_] := Module[{i}, Table[x[[i]] + x[[i + 1]], {i, Length[x] - 1}]];
Table[A103839[n], {n, 1, 9}] (* Robert Price, Oct 25 2018 *)

okperm(perm) = {for (k=1, #perm -1, if (! isprime(perm[k]+perm[k+1]), return (0));); return (1);}
a(n) = {nbok = 0; for (j=1, n!, perm = numtoperm(n, j); if (okperm(perm), nbok++);); return (nbok);} \\ Michel Marcus, Apr 08 2013

For n>1, a(n) = 2 * A051239(n).

More terms from Max Alekseyev, Jan 04 2008

a(25)-a(28) from Giovanni Resta, Apr 01 2014

A228626 Number of Hamiltonian cycles in the undirected simple graph G_n with vertices 1,...,n which has an edge connecting vertices i and j if and only if |i-j| is prime.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 4, 16, 60, 186, 433, 2215, 11788, 76539, 414240, 2202215, 9655287, 69748712, 444195809, 3703859949, 26688275292, 201673532931, 1265944917365, 11801735916539, 92511897525830, 753795624276096, 5237677221537738, 41074291450736424, 280906738160126067

Offset: 1

Zhi-Wei Sun, Aug 28 2013

Conjecture: a(n) > 0 for all n > 4. In other words, for each n = 5,6,... there is a permutation i_1,...,i_n of 1,...,n such that |i_1-i_2|, |i_2-i_3|, ..., |i_{n-1}-i_n| and |i_n-i_1| are all prime.
Note that this conjecture is different from the prime circle problem in A051252 though they look similar.
On August 30 2013, Yong-Gao Chen (from Nanjing Normal University) confirmed the conjecture for n > 12 as follows: If n = 2*k then G_n contains a Hamiltonian cycle (1,3,5,2,7,9,...,2k-5,2k-3,2k,2k-2,2k-4,2k-1,2k-6,2k-8,...,6,4);
if n = 2*k + 1 then G_n contains a Hamiltonian cycle
  (1,3,5,2,7,9,...,2k-5,2k,2k-3,2k-1,2k+1,2k-2,2k-4,...,6,4).
We have got Chen's approval to include his proof here.

			a(5) = 1 since G_5 contains the unique Hamiltonian cycle (1,4,2,5,3).
a(6) = 2 since G_6 contains exactly two Hamiltonian cycles: (1,3,5,2,4,6) and (1,4,2,5,3,6).
a(7) = 4 since G_7 contains exactly four Hamiltonian cycles: (1,3,5,2,7,4,6), (1,3,5,7,2,4,6), (1,4,2,7,5,3,6) and (1,4,7,2,5,3,6).
a(8) = 16 since G_8 contains exactly 16 Hamiltonian cycles: (1,3,5,2,7,4,6,8), (1,3,5,7,2,4,6,8), (1,3,6,4,2,7,5,8), (1,3,6,4,7,2,5,8), (1,3,6,8,5,2,7,4), (1,3,6,8,5,7,2,4), (1,3,8,5,2,7,4,6), (1,3,8,5,7,2,4,6), (1,4,2,7,5,3,6,8), (1,4,2,7,5,3,8,6), (1,4,2,7,5,8,3,6), (1,4,7,2,5,3,6,8), (1,4,7,2,5,3,8,6), (1,4,7,2,5,8,3,6), (1,6,4,2,7,5,3,8), (1,6,4,7,2,5,3,8).
a(9) > 0 since (1,3,5,7,9,2,4,6,8) is a Hamiltonian cycle in G_9.
a(10) > 0 since (1,3,5,2,4,6,9,7,10,8) is a Hamiltonian cycle in G_{10}.
a(11) > 0 since (1,3,5,10,8,11,9,2,7,4,6) is a Hamiltonian cycle in G_{11}.
a(12) > 0 since (1,3,8,10,5,2,7,4,6,11,9,12) is a Hamiltonian cycle in G_{12}.

Hong-Bin Chen, Hung-Lin Fu, Jun-Yi Guo, Beyond Hamiltonicity of Prime Difference Graphs, arXiv:2003.00729 [math.CO], 2020.
S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014. See Table II.
Index entries for sequences related to graphs, Hamiltonian

Cf. A000040, A051239, A051252, A185645, A227050, A242527, A242528.

Table[Length[FindHamiltonianCycle[Graph[Flatten[Table[If[PrimeQ[Abs[i - j]], i \[UndirectedEdge] j, {}], {i, 1, n}, {j, i + 1, n}]]], Infinity]], {n, 1, 15}] (* Robert Price, Apr 04 2019 *)

a(9)-a(17) from Alois P. Heinz, Aug 28 2013
a(18)-a(19) from Stanislav Sykora, May 30 2014
a(20)-a(29) from Max Alekseyev, Jul 04 2014

A064821 Number of ways of writing the numbers 1 .. n in a sequence so that the sum of any two adjacent numbers is a prime; reversing the sequence does not count as different.

Original entry on oeis.org

0, 1, 1, 4, 2, 8, 12, 30, 70, 664, 1072, 8768, 11648, 37108, 95772, 1059816, 2047488, 12111712, 22802028, 120779959, 337801784, 4361743860, 11425028900, 142573286216, 429917269469, 4138239848098, 16171519847028, 214845911686065

Offset: 1

N. J. A. Sloane, Oct 23 2001

If the sequence is d_1 d_2 ... d_n then the n-1 sums d_i + d_{i+1} are required to be primes.
I conjecture a(n) > 0 for all n.
Variant of A051239 with respect to a(1). - R. J. Mathar, Oct 02 2008

			For n = 4 there are 4 sequences: 1234, 1432, 3214, 3412.

Cf. A064821, A103839.

More terms from Jud McCranie, Oct 24 2001
a(22)-a(24) from Donovan Johnson, Aug 27 2010
a(25)-a(28) from Giovanni Resta, Jun 05 2020

A116980 Number of ways to arrange integers 1...n so that the sum of each adjacent pair is a triangular number, not counting reversals.

Original entry on oeis.org

1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 4, 19, 23, 16, 43, 59, 66, 127, 492, 886, 964, 2595, 11426, 36780, 78070, 131232, 423402, 1302893, 3356226, 6673924, 16604441, 32195439, 69328860

Offset: 0

Giovanni Resta, Apr 01 2006

nonn

			a(9)=1, since {3,7,8,2,4,6,9,1,5} and its reversal are the only permutations
of 1..9 with the given property. Here 3+7, 7+8, 8+2, 4+6, 6+9, 9+1 and 1+5 are all triangular numbers.

Cf. A051239.

a(29)-a(33) from Donovan Johnson, Aug 27 2010

a(0)=1 prepended by Alois P. Heinz, Oct 05 2020

A124939 Prime tetrahedron, read by rows.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 1, 6, 5, 1, 1, 10, 1, 12, 7, 1, 16, 3, 8, 1, 1, 18, 1, 22, 9, 1, 28, 13, 24, 1, 30, 11, 20, 17, 1, 1, 36, 1, 40, 19, 1, 42, 25, 34, 1, 46, 15, 14, 23, 1, 52, 21, 26, 27, 32, 1, 1, 58, 1, 60, 29, 1, 66, 31, 48, 1, 70, 33, 38, 35, 1, 72, 37, 64, 39, 44, 1, 78, 49, 54, 43

Offset: 1

Jonathan Vos Post, Nov 13 2006

Each triangular layer of the unique tetrahedron begins with 1, never uses any value other than 1 which has occurred already on this or earlier levels, always uses the least available integer such that the sum of each two consecutive entries is a prime. The number of values of the n-th level is the n-th triangular number A000217(n) = C(n+1,2) = n(n+1)/2 = 0+1+2+...+n. The number of values through the n-th level is the n-th tetrahedral number A000292(n) = C(n+2,3) = n(n+1)(n+2)/6.

			Tetrahedron begins
=================
1
=================
1
1..2
=================
1
1..4
1..6..5
=================
1
1.10
1.12..7
1.16..3..8
=================
1
1.18
1.22..9
1.28.13.24
1.30.11.20.17
=================

R. K. Guy, Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 106, 1994.
Kenney, M. J. "Student Math Notes." NCTM News Bulletin. Nov. 1986.

Eric Weisstein's World of Mathematics, Prime Triangle.

Cf. A000040, A000217, A000292, A036440 Number of ways of arranging row n of the Prime Pyramid, A051239, A051237 Lexicographically earliest Prime Pyramid, read by rows.

srch := proc(a) local res ; res := 2 ; while true do if isprime(res+op(-1,a)) and not ( res in a ) then RETURN(res) ; fi ; res := res+1 ; od ; end: a := [] ; for lvl from 1 to 10 do for row from 1 to lvl do for col from 1 to row do if col = 1 then anxt := 1 ; else anxt := srch(a) ; fi ; printf("%d,",anxt) ; a := [op(a), anxt] ; od ; od ; od ; # R. J. Mathar, Jan 13 2007

a(n) flattens the 3-D table so that level 1 (the apex, with only the value 1) occurs first, then level 2 (with values 1, 1, 2), then level 3 ... and for each level, reads that triangle by rows.

Corrected and extended by R. J. Mathar, Jan 13 2007

A294184 a(n) is the number of ways to arrange numbers from 1 to 2*n in a row, starting with 1, such that the sum of every two adjacent numbers is prime, but also considering the ends as adjacent.

Original entry on oeis.org

1, 2, 2, 4, 96, 1024, 2880, 81024, 770144, 6309300, 213812336, 6395634044, 165849732426, 8050337724850, 255709623233382

Offset: 1

Michel Marcus, Feb 11 2018

When the size of the row is odd, it is impossible to find such an arrangement, so that sequence is only defined for even-sized rows.

			a(1) = 1, because of [1, 2].
a(2) = 2, because of [1, 2, 3, 4] and [1, 4, 3, 2].
a(3) = 2, because of [1, 4, 3, 2, 5, 6] and [1, 6, 5, 2, 3, 4].

Situ Zhengmei, Prime ring, Chinese Math Blog.

Cf. A036440, A051252, A051239, A242527, A242528.

a(n) = 2*A051252(n), for n > 1. - Giovanni Resta, Feb 25 2020

a(9)-a(11) from Jackson Bahm, Feb 25 2020

a(12)-(15) from Giovanni Resta, using A051252, Feb 25 2020

cp's OEIS Frontend

A055265 a(n) is the smallest positive integer not already in the sequence such that a(n)+a(n-1) is prime, starting with a(1)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A051237 Lexicographically earliest prime pyramid, read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A103839 Number of permutations of (1,2,3,...,n) where each of the (n-1) adjacent pairs of elements sums to a prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A228626 Number of Hamiltonian cycles in the undirected simple graph G_n with vertices 1,...,n which has an edge connecting vertices i and j if and only if |i-j| is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A064821 Number of ways of writing the numbers 1 .. n in a sequence so that the sum of any two adjacent numbers is a prime; reversing the sequence does not count as different.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A116980 Number of ways to arrange integers 1...n so that the sum of each adjacent pair is a triangular number, not counting reversals.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A124939 Prime tetrahedron, read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions