A181715 -id:A181715 - cp's OEIS frontend

A181697 Length of the complete Cunningham chain of the first kind starting with prime(n).

5, 2, 4, 1, 3, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 6, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 5, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 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).
prime(n) is in A005384, i.e., a Sophie Germain prime, iff a(n)>1.
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 -> 5 -> 11 -> 23 -> 47 -> 95 = 5*19, so a(1) = 5, a(3) = 4, a(5) = 3, a(9) = 2, and a(15) = 1. - _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.
Wikipedia, Cunningham chain

Cf. A005602, A181715, A263879.

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}]

A285706 a(n) = number of iterations x -> A064216(x) needed to reach a nonprime number when starting from prime(n), a(1) = a(2) = 1.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 26 2017

nonn

Length (or size for the closed cycles: [2] and [3]) of the complete "slipping Cunningham chain of the second kind" starting with prime(n). That is, at the end of every step, the next prime q = 2p-1 "slips" by one step towards smaller primes as A064989(q).

After n = 1, 2 (primes 2 & 3) differs from A181715 for the first time at n=22, where a(22) = 2, while A181715(22) = 3, prime(22) = 79.

			See examples in A285701.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A000040, A064216, A064989, A181715, A246373, A285701.

Cf. A137288 (gives the positions of terms > 1 after its two initial terms).

Table[If[n <= 2, 1, -1 + Length@ NestWhileList[Apply[Times, FactorInteger[2 # - 1] /. {p_, e_} /; p > 2 :> NextPrime[p, -1]^e] &, Prime@ n, PrimeQ@ # &]], {n, 120}] (* Michael De Vlieger, Apr 26 2017 *)

A285706(n) = A285701(prime(n)); \\ The rest of code in A285701.

(define (A285706 n) (A285701 (A000040 n)))

a(n) = A285701(A000040(n)).

A285700 a(n) = Number of iterations x -> 2x-1 needed to get a nonprime number, when starting with x = n.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 26 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A000040, A005382 (positions of terms > 1), A010051, A181715, A285701.

Array[Length@ NestWhileList[2 # - 1 &, #, PrimeQ@ # &] - 1 &, 120] (* Michael De Vlieger, Apr 26 2017 *)

from sympy import isprime
def a(n): return 0 if isprime(n) == 0 else 1 + a(2*n - 1) # Indranil Ghosh, Apr 26 2017

(define (A285700 n) (if (zero? (A010051 n)) 0 (+ 1 (A285700 (+ n n -1)))))

If A010051(n) = 0 [when n is a nonprime], a(n) = 0, otherwise a(n) = 1 + a((2*n)-1).

a(A000040(n)) = A181715(n).

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

cp's OEIS Frontend

A181697 Length of the complete Cunningham chain of the first kind starting with prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A285706 a(n) = number of iterations x -> A064216(x) needed to reach a nonprime number when starting from prime(n), a(1) = a(2) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A285700 a(n) = Number of iterations x -> 2x-1 needed to get a nonprime number, when starting with x = n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

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

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.