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

A109998 Non-Cunningham primes: primes isolated from any Cunningham chain under any iteration of 2p+-1 or (p+-1)/2.

Original entry on oeis.org

17, 43, 67, 71, 101, 103, 109, 127, 137, 149, 151, 163, 181, 197, 223, 241, 257, 269, 283, 311, 317, 349, 353, 373, 389, 401, 409, 433, 449, 461, 463, 487, 521, 523, 557, 569, 571, 599, 617, 631, 643, 647, 677, 701, 709, 739, 751, 769, 773, 787, 797, 821

Offset: 1

Alexandre Wajnberg, Sep 01 2005

The condition that neither 2p - 1 nor 2p + 1 be prime is equivalent to ((p-1) mod 3 = 0) or ((p+1) mod 3 = 0). For example, the prime p = 2^607 - 1 is not in this sequence because p + 1 mod 3 = 2. - Washington Bomfim, Oct 30 2009

			a(1) = 17 is here because 17 * 2 + 1 = 35, 17 * 2 - 1 = 33; (17+1)/2 = 9, (17-1)/2 = 8: four composite numbers.

Chris Caldwell's Prime Glossary, Cunningham chains.
Douglas S. Stones, On prime chains, arXiv:0908.2166 [math.NT] [From _Washington Bomfim_, Oct 30 2009, edited by _R. J. Mathar_, Mar 01 2010]

Cf. A005385, A005383, A060254, A005384, A005382, A068497, A059455, A059762, A057326, A023272, A023302, A059764, A057328, A023330, A005602, A064812, A005603.

nonCunninghamPrimes = {}; Do[p = Prime[n]; If[!PrimeQ[2p - 1] && !PrimeQ[2p + 1] && !PrimeQ[(p - 1)/2] && !PrimeQ[(p + 1)/2], AppendTo[nonCunninghamPrimes, p]], {n, 6!}]; nonCunninghamPrimes (* Vladimir Joseph Stephan Orlovsky, Mar 22 2009 *)

Corrected and extended by Ray Chandler, Sep 02 2005

Replaced link to cached arXiv URL with link to the abstract - R. J. Mathar, Mar 01 2010

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.

A110059 Smallest prime ending a complete Cunningham chain of the second kind (2x-1) of length n.

Original entry on oeis.org

11, 13, 5, 17041, 24481, 12338881, 1065601, 1985902081, 219416417281, 105230562877441, 1422461638625281, 444124661486837761, 3105111850422067201

Offset: 1

Alexandre Wajnberg, Sep 04 2005

nonn

"Complete" means that the chain is not part of a longer chain.

A005603 has the first prime of each chain.

			a(4)=17041 because 2131,4261,8521,17041 are prime, but the preceding and following numbers (1066,34081) are not.

Chris Caldwell's Prime Glossary, Cunningham chains.

Cf. A005382, A005384, A057326, A059761, A005603.

Some terms computed by Gilles Sadowski.

Edited by Don Reble, May 16 2006

A174568 Numbers n such that phi(n) + sigma(n) = sigma(n + phi(n)).

Original entry on oeis.org

2, 3, 7, 19, 31, 37, 79, 97, 99, 135, 139, 157, 198, 199, 211, 229, 271, 287, 307, 331, 337, 350, 367, 379, 439, 499, 539, 547, 577, 601, 607, 619, 661, 671, 691, 727, 811, 829, 877, 923, 937, 967, 997, 1009, 1069, 1171, 1237, 1254, 1279, 1297, 1399, 1429

Offset: 1

Michel Lagneau, Mar 22 2010

nonn

A005382 is included in this sequence : if p and 2p-1 primes, phi(p) = p-1, sigma(p)=p+1 and sigma(2p-1)=2p => phi(p) +sigma(p) = sigma(p+phi(p)). See the similar sequence A005384.

			2 is in the sequence because phi(2) + sigma(2) = 1 + 3 = 4, and sigma(2 + phi(2)) = sigma(3) = 4;
99 is in the sequence because phi(99) + sigma(99) = 60 + 156 = 216, and sigma(99 + phi(99)) = sigma(159) = 216.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.

Amiram Eldar, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

Cf. A005382, A005384, A057326, A057327, A057328, A057330, A005603.

[n: n in [1..1500] | (EulerPhi(n) + SumOfDivisors(n)) eq (SumOfDivisors(n + EulerPhi(n)))]; // Vincenzo Librandi, Jul 15 2015

with(numtheory):for n from 1 to 3000 do :if phi(n)+sigma(n) = sigma(n+phi(n)) then print(n):else fi:od:

Select[Range[1500],EulerPhi[#]+DivisorSigma[1,#]==DivisorSigma[1, #+ EulerPhi[ #]]&] (* Harvey P. Dale, Jul 05 2018 *)

A364091 a(n) is the first prime p such that the longest sequence of primes p = p_1, p_2, ... with |p_{k+1} - 2*p_k| = 1 has length n.

Original entry on oeis.org

13, 7, 11, 5, 3, 2, 16651, 15514861, 85864769, 26089808579, 665043081119, 554688278429, 758083947856951, 95405042230542329, 69257563144280941

Offset: 1

Robert Israel, Jul 04 2023

a(n) = A000040(k) where A263879(k) = n is the first appearance of n in A263879.

			a(4) = 5 because 5, 2*5 + 1 = 11, 2*11 + 1 = 23, 2*23 + 1 = 47 is a sequence of primes of length 4 while 2*47 - 1 = 93 and 2*47 + 1 = 95 are not primes, and 5 is the smallest prime that works.

Cf. A000040, A263879.

M:= 10: # for a(1) .. a(N)
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:
V:= Vector(M):
p:= 1: count:= 0:
for k from 1 while count < M do
  p:= nextprime(p);
  v:= f(p);
  if v <= M and V[v] = 0 then V[v]:= p; count:= count+1; fi
od:
convert(V,list);

from sympy import isprime, nextprime
def A364091(n):
    if 5 <= n <= 6: return 8-n
    q = 5
    while True:
        p, c = q, 1
        while isprime(p:=(p<<1)+(-1 if p%3==1 else 1)):
            c += 1
            if c > n:
                break
        if c == n:
            return q
        q = nextprime(q) # Chai Wah Wu, Jul 07 2023

a(n) = min(A005602(n), A005603(n)) for n >= 7.

A110089 Smallest prime beginning (through <2+1> or/and <2-1>) a complete Cunningham chain (of the first or the second kind) of length n.

Original entry on oeis.org

11, 3, 2, 509, 2, 89, 16651, 15514861, 85864769, 26089808579, 665043081119, 554688278429, 758083947856951, 95405042230542329, 69257563144280941

Offset: 1

Alexandre Wajnberg, Sep 04 2005

The word "complete" indicates each chain is exactly n primes long for the operator in function (i.e. the chain cannot be a subchain of another one); and the first and/or last term may be involved in a chain of the other kind (i.e. the chain may be connected to another one). a(1)-a(8) computed by Gilles Sadowski.

			a(1)=11 because 2, 3, 5 and 7 are included in longer chains than one prime long; and 11 (although included in a <2p+1> chain) has no prime connection through <2p-1>.
a(2)=3 because 3 begins (through 2p+1>) the first complete two primes chain: 3-> 7 (even if 3 and 7 are also part of two others chains, but through <2p-1>).
a(3)=2 because (although 2 begins also a five primes chain through <2p+1>) it begins, through <2p-1>, the first complete three primes chain encountered: 2->3->5.

Chris Caldwell's Prime Glossary, Cunningham chains.

Cf. A023272, A023302, A023330, A005384, A005385, A059452, A059455, A007700, A059759, A059760, A059761, A059762, A059763, A059764, A059765, A038397, A104349, A091314, A069362, A016093, A014937, A057326, A110059, A110056, A110038, A059766, A110027, A059764, A110025, A110024, A059763, A110022, A109998, A109946, A109927, A109835, A005603.

a(n) = min(A005602(n), A005603(n)). - R. J. Mathar, Jul 23 2008

a(8)-a(13) via A005602, A005603 from R. J. Mathar, Jul 23 2008

a(14)-a(15) via A005602, A005603 from Jason Yuen, Sep 03 2024

A110092 Smallest prime ending (through <2+1> or <2-1> separately) a complete Cunningham chain (of the first or the second kind) of length n.

Original entry on oeis.org

17, 59, 73, 4079, 47, 2879, 1065601

Offset: 1

Alexandre Wajnberg, Sep 04 2005

The word "complete" indicates each chain is exactly n primes long for the operator in function (i.e. the chain cannot be a subchain of another one); and the first and/or last term may not be involved in a chain of the other kind (i.e. the chain may not be connected to another one).

			a(1)=17 because 2, 3, 5, 7, 11 and 13 are part of longer chains whatever the operator; 17 is the first completely isolated prime.
a(2)=59 because it ends the first two primes chain not connected to another one: 29->59.

Chris Caldwell's Prime Glossary, Cunningham chains.

Cf. A023272, A023302, A023330, A005384, A005385, A059452, A059455, A007700, Cf. A059759, A059760, A059761, A059762, A059763, A059764, A059765, A038397, A104349, A091314, A069362, A016093, A014937, A057326, A110059, A110056, A110038, A059766, A110027, A059764, A110025, A110024, A059763, A110022, A109998, A109946, A109927, A109835, A005603.

Terms computed by Gilles Sadowski.

A110093 Smallest prime ending (through <2+1> or/and <2-1>) a complete Cunningham chain (of the first or the second kind) of length n.

Original entry on oeis.org

11, 7, 5, 4079, 47, 2879, 1065601

Offset: 1

Alexandre Wajnberg, Sep 04 2005

The word "complete" indicates each chain is exactly n primes long for the operator in function (i.e. the chain cannot be a subchain of another one); but the first and/or last term may be involved in a chain of the other kind (i.e. the chain may be connected to another one).

			a(1)=11 because 2, 3, 5 and 7 are not ending chains; or are part of chains longer than one prime; 11, although is part of a five primes <2p+1> chain, is isolated through <2p-1>.
a(2)=7 because 7 ends through <2p+1> the first two primes chain: 3->7 (even if both primes are also part of <2p-1> chains).

Chris Caldwell's Prime Glossary, Cunningham chains.

Cf. A023272, A023302, A023330, A005384, A005385, A059452, A059455, A007700, Cf. A059759, A059760, A059761, A059762, A059763, A059764, A059765, A038397, A104349, A091314, A069362, A016093, A014937, A057326, A110059, A110056, A110038, A059766, A110027, A059764, A110025, A110024, A059763, A110022, A109998, A109946, A109927, A109835, A005603.

Terms computed by Gilles Sadowski.

A176268 Primes of a Generalized Cunningham chain of length 9 by the function f(p) = 2 * p + 13.

Original entry on oeis.org

3467, 6947, 13907, 27827, 55667, 111347, 222707, 445427, 890867

Offset: 1

Eva-Maria Zschorn (e-m.zschorn(AT)zaschendorf.km3.de), Apr 13 2010

See comments and references of A176223 and A176247
Chain of 8 primes: 2, 17, 47, 107, 227, 467, 947, 1907
It is conjectured that arbitrarily long such chains exist

			3467 = prime(486), (3467 - 13)/ 2 = 1727 = 11 * 157 is composite
f(3467) = 6947 = prime(891), f(6947) = 13907 = prime(1644)
f(13907) = 27827 = prime(3040), f( 27827) = 55667 = prime(5649)
f(55667) = 111347 = prime(10565), f(111347) = 222707 = prime(19832)
f(222707) = 445427 = prime(37374), f(445427) = 890867 = prime(70612)
f(890867) = 1781747 = 11 * 161977
3467 is smallest prime for such a chain of 9 primes

Joe Buhler: Algorithmic Number Theory: Third International Symposium, ANTS-III, New York: Springer, 1998
David J. Darling: The Universal Book of Mathematics: From Abracadabra to Zeno's Paradoxes, Hoboken: John Wiley & Sons, 2004
Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde, Springer-Verlag GmbH & Co. KG, 2006

A000040, A005602, A005603, A176247

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

A109998 Non-Cunningham primes: primes isolated from any Cunningham chain under any iteration of 2p+-1 or (p+-1)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

A110059 Smallest prime ending a complete Cunningham chain of the second kind (2x-1) of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A174568 Numbers n such that phi(n) + sigma(n) = sigma(n + phi(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

A364091 a(n) is the first prime p such that the longest sequence of primes p = p_1, p_2, ... with |p_{k+1} - 2*p_k| = 1 has length n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Python

Formula

A110089 Smallest prime beginning (through <*2+1> or/and <*2-1>) a complete Cunningham chain (of the first or the second kind) of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A110092 Smallest prime ending (through <*2+1> or <*2-1> separately) a complete Cunningham chain (of the first or the second kind) of length n.

Views

Author

A110089 Smallest prime beginning (through <2+1> or/and <2-1>) a complete Cunningham chain (of the first or the second kind) of length n.

A110092 Smallest prime ending (through <2+1> or <2-1> separately) a complete Cunningham chain (of the first or the second kind) of length n.

A110093 Smallest prime ending (through <2+1> or/and <2-1>) a complete Cunningham chain (of the first or the second kind) of length n.