A181697 -id:A181697 - cp's OEIS frontend

A181715 Length of the complete Cunningham chain of the second kind starting with prime(n).

3, 2, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1

Offset: 1

M. F. Hasler, Nov 17 2010

nonn

Number of iterations x -> 2x-1 needed to get a composite number, when starting with prime(n).
Dickson's conjecture implies that, for every positive integer r, there exist infinitely many n such that a(n) = r. - Lorenzo Sauras Altuzarra, Feb 12 2021
a(n) is the least k such that 2^k * (prime(n)-1) + 1 is composite. Note that a(n) is well defined since 2^(p-1) * (p-1) + 1 is divisible by p for odd primes p. - Jianing Song, Nov 24 2021

			2 -> 3 -> 5 -> 9 = 3^2, so a(1) = 3 and a(2) = 2. - _Jonathan Sondow_, Oct 30 2015

T. D. Noe, Table of n, a(n) for n = 1..10000
G. Löh, Long chains of nearly doubled primes, Math. Comp., 53 (1989), 751-759.
Michael Penn, Romanian Mathematical Olympiad Problem, Youtube video, 2020.
Wikipedia, Cunningham chain

Cf. A000040, A005382, A005408, A005602, A005603, A181697, A263879, A285700, A285706, A057326, A057327, A057328, A057329, A057330, A064812.

Cf. A137288 (positions of terms > 1).

a := proc(n)
   local c, l:
   c, l := 0, ithprime(n):
   while isprime(l) do c, l := c+1, 2*l-1: od:
   c:
end: # Lorenzo Sauras Altuzarra, Feb 12 2021

Table[p = Prime[n]; cnt = 1; While[p = 2*p - 1; PrimeQ[p], cnt++]; cnt, {n, 100}] (* T. D. Noe, Jul 12 2012 *)
Table[-1 + Length@ NestWhileList[2 # - 1 &, Prime@ n, PrimeQ@ # &], {n, 98}] (* Michael De Vlieger, Apr 26 2017 *)

a(n)= n=prime(n); for(c=1,1e9, is/*pseudo*/prime(n=2*n-1) || return(c))

a(n) < prime(n) for n > 1; see Löh (1989), p. 751. - Jonathan Sondow, Oct 28 2015
max(a(n), A181697(n)) = A263879(n) for n > 2. - Jonathan Sondow, Oct 30 2015
a(n) = A285700(A000040(n)). - Antti Karttunen, Apr 26 2017

Escape clause added to definition by N. J. A. Sloane, Feb 19 2021

Escape clause deleted from definition by Jianing Song, Nov 24 2021

A075712 Rearrangement of primes into Germain groups (or Cunningham chains).

Original entry on oeis.org

2, 5, 11, 23, 47, 3, 7, 13, 17, 19, 29, 59, 31, 37, 41, 83, 167, 43, 53, 107, 61, 67, 71, 73, 79, 89, 179, 359, 719, 1439, 2879, 97, 101, 103, 109, 113, 227, 127, 131, 263, 137, 139, 149, 151, 157, 163, 173, 347, 181, 191, 383, 193, 197, 199, 211, 223, 229, 233

Offset: 1

Zak Seidov, Oct 03 2002

In each group, p(i+1) = 2*p(i)+1.

The groups are also known as Cunningham chains of the first kind.

			The groups are:
{2, 5, 11, 23, 47},
{3, 7},
{13},
{17},
{19},
{29, 59},
{31},
{37},
{41, 83, 167},
{43},
{53, 107},
{61},
{67},
{71},
{73},
{79},
{89, 179, 359, 719, 1439, 2879},
{97},
{101},
{103},
{109},
{113, 227},
{127},
{131, 263},
{137},
{139},
...

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A005384, A059452, A059453, A059455, A059456, A053176.
See also A181697.
See A059456 for initial terms, A338945 for lengths.

Block[{a = {2}, j = 1, k, p}, Do[k = j; If[PrimeQ@ a[[-1]], AppendTo[a, 2 a[[-1]] + 1], While[! FreeQ[a, Set[p, Prime[k]]], k++]; j++; Set[a, Append[a[[1 ;; -2]], p]]], 10^3]; a] (* Michael De Vlieger, Nov 17 2020 *)

first(n) = my(res=List([2,5,11,23,47])); forprime(p=3, oo, if(!isprime((p-1)>>1), listput(res,p); c = 2*p+1; while(isprime(c), listput(res,c); c=2*c+1)); if(#res>n,return(res))); res \\ David A. Corneth, Nov 13 2021

Edited by N. J. A. Sloane, Nov 13 2021

More terms from David A. Corneth, Nov 13 2021

A263879 Length k of the longest chain of primes p_1, p_2, ..., p_k such that p_1 is the n-th prime and p_{i+1} equals 2p_i + 1 or 2p_i - 1 for all i < k, the +/- sign depending on i.

Original entry on oeis.org

6, 5, 4, 2, 3, 1, 1, 3, 2, 2, 2, 2, 3, 1, 1, 2, 1, 1, 1, 1, 1, 3, 2, 6, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 5, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 2, 1, 1, 1, 4, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 2, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 4, 1, 1, 1

Offset: 1

Jonathan Sondow, Oct 28 2015

nonn

If the +/- signs are all + or all -, then p_1, p_2, ..., p_k is a Cunningham chain of the first or second kind, respectively.
If p_1 > 3, then the +/- signs must be all + or all -, because if e = +1 or -1, then one of p, 2*p + e, 2*(2*p + e) - e is divisible by 3; see Löh (1989), p. 751.
Cunningham chains of the first and second kinds of length > 1 cannot begin with the same prime p > 3, because one of the numbers p, 2*p-1, 2*p+1 is divisible by 3.

			2, 3, 5, 11, 23, 47 is the longest such chain of primes starting with 2. Their indices are 1, 2, 3, 5, 9, 15, respectively, so a(1) = 6, a(2) = 5, a(3) = 4, a(5) = 3, a(9) = 2, and a(15) = 1.

R. K. Guy, Unsolved Problems in Number Theory, A7.

Robert Israel, Table of n, a(n) for n = 1..10000
G. Löh, Long chains of nearly doubled primes, Math. Comp., 53 (1989), 751-759.
Wikipedia, Cunningham chain

Cf. A005384, A005602, A181697, A181715.

f:= proc(n) option remember; local x;
  if n mod 3 = 1 then x:= 2*n-1 else x:= 2*n+1 fi;
  if isprime(x) then 1 + procname(x) else 1 fi;
end proc:
f(2):= 6: f(3):= 5:
map(f, [seq(ithprime(i),i=1..100)]); # Robert Israel, Jul 04 2023

A263879 = Join[{6, 5},
  Table[p = Prime[n]; cnt = 1;
   While[PrimeQ[2*p + 1] || PrimeQ[2*p - 1],
    cnt++ && If[PrimeQ[2*p + 1], p = 2*p + 1, p = 2*p - 1 ]];
   cnt, {n, 3, 100}]]

from sympy import prime, isprime
def A263879(n):
    if n <= 2: return 7-n
    p, c = prime(n), 1
    while isprime(p:=(p<<1)+(-1 if p%3==1 else 1)):
        c += 1
    return c # Chai Wah Wu, Jul 07 2023

a(n) = max(A181697(n), A181715(n)) for n > 2.

a(n) < prime(n) for n > 2; see Löh (1989), p. 751.

A377120 a(n) = number of iterations of x -> 2 x + 3 to reach a nonprime, starting with prime(n) .

Original entry on oeis.org

4, 1, 4, 3, 1, 3, 2, 2, 1, 2, 1, 1, 1, 3, 6, 2, 1, 1, 6, 1, 2, 1, 1, 2, 5, 1, 1, 1, 1, 3, 2, 1, 5, 2, 1, 1, 2, 1, 3, 3, 1, 1, 1, 2, 4, 2, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 2, 1, 5, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 3, 1, 2, 1, 1, 1, 1, 2, 1

Offset: 1

Clark Kimberling, Oct 31 2024

nonn

Guide to related sequences:
mapping     initial prime    sequence
x -> 2x + 1        2         A181697
x -> 2x + 3        2         this sequence
x -> 2x + 5        2         A377510
x -> 2x + 7        2         A377511
x -> 2x - 1        2         A181715
x -> 2x - 3        5         A377512
x -> 2x - 5       11         A377513
x -> 2x - 7       11         A377514

			prime(1) = 2 -> 7 -> 17 -> 37 -> 77 = 7*11, so a(1) = 4.

Cf. A000040, A181697, A181715, A377510, A377511, A377512, A377513, A377514.

Table[p = Prime[n]; c = 1; While[p = 2*p + 3; PrimeQ[p], c++]; c, {n, 200}]

A064812 Smallest prime p such that the infinite sequence {p, p'=2p-1, p''=2p'-1, ...} begins with a string of exactly n primes.

Original entry on oeis.org

5, 3, 2, 2131, 1531, 33301, 16651, 15514861, 857095381, 205528443121, 1389122693971, 216857744866621, 758083947856951, 107588900851484911, 69257563144280941

Offset: 1

David Terr, Oct 21 2002

nonn

Chains of length n of nearly doubled primes.

Smallest prime beginning a complete Cunningham chain of length n of the second kind. (For the first kind see A005602.) - Jonathan Sondow, Oct 30 2015

			a(3) = 2 because 2 is the smallest prime such that the sequence {2, 3, 5, 9, ...} begins with exactly 3 primes, where each term in the sequence is twice the preceding term minus 1.

G. Löh, Long chains of nearly doubled primes, Math. Comp., 53 (1989), 751-759.
Wikipedia, Cunningham chain

A better version of A005603.
Cf. (A005382 and A005383), A057326, A057327, A057328, A057329, A057330, A005602.
Cf. A002808, A006450, A049076-A049081, A050436, A076237-A076239, A050436-A050439, A065860, A181697, A263879.

A214280 Total number of primes which can be reached via Cunningham chains, starting with prime(n), not counting this starting prime.

Original entry on oeis.org

7, 6, 3, 1, 2, 0, 0, 2, 1, 1, 1, 1, 2, 0, 0, 1, 0, 0, 0, 0, 0, 2, 1, 5, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 4, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 3, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 1

Offset: 1

Alex Ratushnyak, Jul 09 2012

Other definition: Count of the binary descendants of the n-th prime. Prime q is a binary descendant of prime p if  2*p-1 <= q <= 2*p+1.
a(n) is  the total count of direct binary descendants of the n-th prime plus their binary descendants, and so on.
q=(p-1)*2 + b*2 + 1, where b is either 0 or 1. Thus if p>2 then in base 2: q is p with a digit inserted before the least significant digit.
It is conjectured there are arbitrarily big terms (see the MathWorld link).
If p==2 (mod 3), then only 2p+1 (==2 (mod 3) again) may be prime; 2p-1 will be divisible by 3. For p==1 (mod 3), only 2p-1 (==1 (mod 3) again) can be prime. Therefore, there can be no alternance in the +1/-1 choice (except for starting primes 2 and 3) when looking at all possible descendants. This leads to the formula by T. D. Noe.  - M. F. Hasler, Jul 13 2012

			prime(3)=5 has one binary descendant 11, which has one b.d. 23, which has one b.d. 47. Because 47 has no binary descendants, a(3)=3.
prime(4)=7 has one binary descendant 13, which has no binary descendants, so a(4)=1.
As explained in the comment, for n>2 this equals the maximum length of either of the Cunningham chains, i.e., iterations of x->2x+1 resp. x->2x-1 before getting a composite. For prime(2)=3, the first map yields (3)->7->(15) and the second map yields (3)->5->(9), so there are 2 primes, but one has to add the a(4)+a(3)=3+1 descendants of these 2 primes, whence a(2)=2+4=6.
Starting with prime(1)=2, the "2x-1" map yields 3, to which one must add its a(2)=6 descendants. They already include the prime 5 = 2*2+1 and its descendants. Thus, a(1)=1+6=7.

Jens Kruse Andersen and Eric W. Weisstein, MathWorld: Cunningham Chain

Cf. A000040.
Cf. A005383 - primes of the form prime*2-1.
Cf. A005385 - primes of the form prime*2+1.
Cf. A214342 - count of the decimal descendants.
Cf. A181697, A181715 (two kinds of Cunningham chains).

des[n_] := {If[PrimeQ[2*n-1], s = AppendTo[s, 2*n-1]; des[2*n-1]]; If[PrimeQ[2*n+1], s = AppendTo[s, 2*n+1]; des[2*n+1]]}; Table[s = {}; des[Prime[n]]; Length[Union[s]], {n, 100}] (* T. D. Noe, Jul 11 2012 *)

a(n) = max(A181697(n), A181715(n)) - 1 for n > 2. - T. D. Noe, Jul 12 2012

A349670 Number of iterations x -> (x-1)/2 needed to get 1, 2 or a composite number, when starting with prime(n).

Original entry on oeis.org

0, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Jianing Song, Nov 24 2021

nonn

a(n) is the least k such that (prime(n) + 1)/2^k - 1 is 1, 2 or a composite number. It follows that a(n) <= v2(prime(n) + 1), v2 = A007814.

For prime(n) != 5, a(n) > 1 if and only if prime(n) is a safe prime (A005385).

			47 -> 23 -> 11 -> 5 -> 2 (prime(15) -> prime(9) -> prime(5) -> prime(3) -> prime(1)), hence a(1) = 0, a(3) = 1, a(5) = 2, a(9) = 3, a(15) = 4.
7 -> 3 -> 1 (prime(4) -> prime(2) -> 1), hence a(2) = 1, a(4) = 2.
59 -> 29 -> 14 (prime(17) -> prime(10) -> 14), hence a(10) = 1, a(17) = 2.

Cf. A181697, A181715, A349671, A007814, A005385.

a[n_] := -1 + Length @ NestWhileList[(# - 1)/2 &, Prime[n], OddQ[#] && PrimeQ[#] &]; Array[a, 90] (* Amiram Eldar, Nov 27 2021 *)

a(n) = my(p=prime(n), k=0); while(isprime(m = (p+1)>>k - 1) && m != 2, k++); k

A349671 Number of iterations x -> (x+1)/2 needed to get 2 or a composite number, when starting with prime(n).

Original entry on oeis.org

0, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1

Offset: 1

Jianing Song, Nov 24 2021

nonn

a(n) is the least k such that (prime(n) - 1)/2^k + 1 is 2 or a composite number. It follows that a(n) <= v2(prime(n) - 1), v2 = A007814.

For prime(n) != 3, a(n) > 1 if and only if (prime(n)+1)/2 is prime (A005383).

			5 -> 3 -> 2 (prime(3) -> prime(2) -> prime(1)), hence a(1) = 0, a(2) = 1, a(3) = 2.
13 -> 7 -> 4 (prime(6) -> prime(4) -> 4), hence a(4) = 1, a(6) = 2.
73 -> 37 -> 19 -> 10 (prime(21) -> prime(12) -> prime(8) -> 10), hence a(8) = 1, a(12) = 2, a(21) = 3.

Cf. A181697, A181715, A349670, A007814, A005383.

a[n_] := -1 + Length @ NestWhileList[(# + 1)/2 &, Prime[n], # == 1 || (OddQ[#] && PrimeQ[#]) &]; Array[a, 90] (* Amiram Eldar, Nov 27 2021 *)

a(n) = my(p=prime(n), k=0); while(isprime(m = (p-1)>>k + 1) && m != 2, k++); k

A320342 Maximum term in Cunningham chain of the first kind generated by the n-th prime.

Original entry on oeis.org

47, 7, 47, 7, 47, 13, 17, 19, 47, 59, 31, 37, 167, 43, 47, 107, 59, 61, 67, 71, 73, 79, 167, 2879, 97, 101, 103, 107, 109, 227, 127, 263, 137, 139, 149, 151, 157, 163, 167, 347, 2879, 181, 383, 193, 197, 199, 211, 223, 227, 229, 467, 479, 241, 503, 257, 263, 269, 271, 277, 563, 283, 587, 307, 311, 313, 317, 331, 337, 347, 349

Offset: 1

Pierandrea Formusa, Dec 10 2018

nonn

No term is a Sophie Germain prime.

A181697 is the sequence of the lengths of the chains in the name.

			a(1)=47 as prime(1)=2 and the Cunningham chain generated by 2 is (2,5,11,23,47), with maximum item 47.

Cf. A181697.

a[n_] := NestWhile[2#+1&, n, PrimeQ, 1, Infinity, -1]; a/@Prime@Range@70  (* Amiram Eldar, Dec 11 2018 *)

def cunningham_chain(p,t):
    # returns the Cunningham chain generated by p of type t (1 or 2)
    from sympy.ntheory import isprime
    if not(isprime(p)):
        raise Exception("Invalid starting number! It must be prime")
    if t!=1 and t!=2:
        raise Exception("Invalid type! It must be 1 or 2")
    elif t==1: k=t
    else: k=-1
    cunn_ch=[]
    cunn_ch.append(p)
    while isprime(2*p+k):
        p=2*p+k
        cunn_ch.append(p)
    return(cunn_ch)
from sympy import prime
n=71
r=""
for i in range(1,n):
    cunn_ch=(cunningham_chain(prime(i),1))
    last_item=cunn_ch[-1]
    r += ","+str(last_item)
print(r[1:])

cp's OEIS Frontend

A181715 Length of the complete Cunningham chain of the second kind starting with prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A075712 Rearrangement of primes into Germain groups (or Cunningham chains).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A263879 Length k of the longest chain of primes p_1, p_2, ..., p_k such that p_1 is the n-th prime and p_{i+1} equals 2*p_i + 1 or 2*p_i - 1 for all i < k, the +/- sign depending on i.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A377120 a(n) = number of iterations of x -> 2 x + 3 to reach a nonprime, starting with prime(n) .

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A064812 Smallest prime p such that the infinite sequence {p, p'=2p-1, p''=2p'-1, ...} begins with a string of exactly n primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A214280 Total number of primes which can be reached via Cunningham chains, starting with prime(n), not counting this starting prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A349670 Number of iterations x -> (x-1)/2 needed to get 1, 2 or a composite number, when starting with prime(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A349671 Number of iterations x -> (x+1)/2 needed to get 2 or a composite number, when starting with prime(n).

A263879 Length k of the longest chain of primes p_1, p_2, ..., p_k such that p_1 is the n-th prime and p_{i+1} equals 2p_i + 1 or 2p_i - 1 for all i < k, the +/- sign depending on i.