A036440 -id:A036440 - 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

A051239 Number of ways to arrange integers 1 through n so that the sum of each adjacent pair is prime, not counting reversals.

Original entry on oeis.org

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

Jud McCranie

Similar to A036440, but not requiring 1 to be first and n to be last.

			a(5)=2 since 1,4,3,2,5 and 3,4,1,2,5 have the property that the sum of each adjacent pair is prime.

Cf. A036440, A051237.

For n>1, a(n) = A103839(n)/2.

More terms from Max Alekseyev, Jan 04 2008

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

A124886 3-almost prime triangle, read by rows.

Original entry on oeis.org

1, 1, 7, 1, 11, 9, 1, 17, 3, 5, 1, 19, 8, 4, 14, 1, 26, 2, 6, 12, 15, 1, 27, 18, 10, 20, 30, 22, 1, 29, 13, 31, 21, 23, 40, 28, 1, 41, 25, 38, 32, 34, 16, 36, 39, 1, 43, 33, 35, 57, 42, 24, 44, 48, 50

Offset: 1

Jonathan Vos Post, Nov 12 2006

This is to 3-almost primes (A014612) as A124883 is to semiprimes (A001358). The n-th row is of length n. Each value is the smallest previously unused natural number such that every pair of adjacent values in the triangle is 3-almost prime (A014612). Consider row 2. Starting with T(1,2) = 1, the least integer we can add to 1 and get a 3-almost prime is 7, since 1 + 8 = 8 = 2^3 is 3-almost prime. Consider row 3. Starting with T(1,3) = 1, the least integer we can add to 1 and get a 3-almost prime is 7, but we've already used that. The least unused integer that works is 11, since 1 + 11 = 12 = 2^2 * 3 is 3-almost prime. If we cross out ones from the triangle read by rows, what remains is a permutation of the natural number greater than 1. That is, every nonnegative integer appears in the triangle. The second column T(n,2) is monotone increasing.

			Triangle begins:
  1
  1  7
  1 11  9
  1 17  3  5
  1 19  8  4 14
  1 26  2  6 12 15
  1 27 18 10 20 30 22
  1 29 13 31 21 23 40 28
  1 41 25 38 32 34 16 36 39
  1 43 33 35 57 42 24 44 48 50

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

Eric Weisstein's World of Mathematics, Prime Triangle.

Cf. A001358, A014612, A036440, A051237, A124883.

T(n,1) = 1 for all natural numbers n. For n>1 and 1T(n,i) for iT(r,s) for rA014612}.

A124883 Semiprime triangle, read by rows.

Original entry on oeis.org

1, 1, 3, 1, 5, 4, 1, 8, 2, 7, 1, 9, 6, 15, 10, 1, 13, 12, 14, 11, 22, 1, 20, 18, 16, 17, 21, 25, 1, 24, 27, 19, 30, 28, 23, 26, 1, 32, 33, 29, 36, 38, 31, 34, 35, 1, 37, 40, 42, 43, 39, 46, 41, 44, 47, 1, 45, 48, 58, 53, 62, 49, 57, 54, 52, 59

Offset: 1

Jonathan Vos Post, Nov 11 2006

			The n-th row is of length n. Each value is the smallest previously unused natural number such that the sum of every pair of adjacent values in the triangle is a semiprime (A001358).
Consider row 2. Starting with T(1,2) = 1, the least integer we can add to 1 and get a semiprime is 3, since 1 + 3 = 4 = 2^2 is semiprime. Consider row 3. Starting with T(1,3) = 1, the least integer we can add to 1 and get a semiprime is 1, but we've already used that. The next is 3, but we've used that. The least unused integer that works is 5, since 1 + 5 = 6 = 2 * 3 is semiprime. If we cross out ones from the triangle read by rows, what remains is a permutation of the natural number greater than 1. That is, every nonnegative integer appears in the triangle. The second column T(n,2) is monotone increasing.
Triangle begins:
  1;
  1,  3;
  1,  5,  4;
  1,  8,  2,  7;
  1,  9,  6, 15, 10;
  1, 13, 12, 14, 11, 22;
  1, 20, 18, 16, 17, 21, 25;
  1, 24, 27, 19, 30, 28, 23, 26;
  1, 32, 33, 29, 36, 38, 31, 34, 35;
  1, 37, 40, 42, 43, 39, 46, 41, 44, 47;
  1, 45, 48, 58, 53, 62, 49, 57, 54, 52, 59;
  ...

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

Eric Weisstein's World of Mathematics, Prime Triangle.

Cf. A001358, A036440, A051237.

T(n,1) = 1 for all natural numbers n. For n>1 and 1T(n,i) for iT(r,s) for rA001358}.

Terms corrected by Alois P. Heinz, Apr 08 2025

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

A051239 Number of ways to arrange integers 1 through n so that the sum of each adjacent pair is prime, not counting reversals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A124886 3-almost prime triangle, read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A124883 Semiprime triangle, read by rows.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A124939 Prime tetrahedron, read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula