A063378 -id:A063378 - cp's OEIS frontend

A063377 Sophie Germain degree of n: number of iterations of n under f(k) = 2k+1 before we reach a number that is not a prime.

0, 5, 2, 0, 4, 0, 1, 0, 0, 0, 3, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 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, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0

Offset: 1

Reiner Martin, Jul 14 2001

nonn

a(n) >= 1 means that n is prime; a(n) >= 2 means that n is a Sophie Germain prime. Is the Sophie Germain degree always finite? Is it unbounded?
A339579 is an essentially identical sequence from 1981. - N. J. A. Sloane, Dec 24 2020
From Michael S. Branicky, Dec 24 2020: (Start)
All n > 5 with a(n) >= 4 satisfy n == 9 (mod 10).
Proof.  Let f^k(n) denote iterates of 2*k + 1, with f^0(n) = n.
n != 0, 2, 4, 5, 6, or 8 (mod 10), otherwise f^0(n) is not prime, and a(n) = 0.
n != 7 (mod 10) otherwise f^1(n) = 2*n + 1 == 5 (mod 10), not prime, and a(n) <= 1.
n != 3 (mod 10) otherwise f^2(n) = 4*r + 3 == 5 (mod 10), not prime, and a(n) <= 2.
n != 1 (mod 10) otherwise f^3(n) = 8*r + 7 == 5 (mod 10), not prime, and a(n) <= 3.
(End)
From Peter Schorn, Jan 18 2021: (Start)
The Sophie Germain degree is always finite.
Proof. Let f^k(n) denote iterates of 2*k + 1 with closed form f^k(n) = 2^k * n + 2^k - 1.
There are three cases for n:
1. If n is not a prime then f^0(n) = n is composite.
2. If n = 2 then f^5(2) = 95 is composite.
3. If n is an odd prime then f^(n-1)(n) = 2^(n-1) * n + 2^(n-1) - 1 is divisible by n since 2^(n-1) == 1 (mod n) by Fermat's theorem.
(End)

			a(2)=5 because 2, 5, 11, 23, 47 are prime but 95 is not.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A005384, A063378, A093008, A093007, A292936, A339579.
For records see A339581.
See also Cunningham chains, A005602, A005603.

Table[Length[NestWhileList[2#+1&,n,PrimeQ[#]&]],{n,100}]-1 (* Harvey P. Dale, Aug 08 2020 *)

a(n) = {if (! isprime(n), return (0)); d = 1; k = n; while(isprime(p = 2*k+1), k = p; d++;); return (d);} \\ Michel Marcus, Jul 22 2013

From Michael S. Branicky, Dec 24 2020: (Start)
See proof above.
a(n) = 0 if n == 0, 2, 4, 5, 6, 8 (mod 10), and n != 2 or 5.
a(n) <= 1 if n == 7 (mod 10).
a(n) <= 2 if n == 3 (mod 10).
a(n) <= 3 if n == 1 (mod 10).
(End)

Term a(1) = 0 prepended by Antti Karttunen, Oct 09 2018.

A339579 a(n) = least nonnegative integer k such that n*2^k - 1 is composite.

Original entry on oeis.org

4, 3, 5, 2, 0, 4, 0, 1, 0, 0, 0, 3, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 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, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0

Offset: 1

N. J. A. Sloane, Dec 24 2020

nonn

Conjectured to grow without limit.

A063377 is an essentially identical sequence, although with a slightly different definition, different initial terms, and different offset.

Carl Pomerance, Problem 81:21 (= 321), in R. K. Guy problem list.

Antti Karttunen, Table of n, a(n) for n = 1..65537
R. K. Guy, editor, Western Number Theory Problems, 1985-12-21 & 23, Typescript, Jul 13 1986, Dept. of Math. and Stat., Univ. Calgary, 11 pages. Annotated scan of pages 1, 3, 7, 9, with permission.

See A339580 for records.

Cf. A063377, A063378, A339581.

A339579(n) = for(k=0,oo,my(t=(n*(2^k))-1); if((t>1)&&!isprime(t), return(k))); \\ Antti Karttunen, Dec 24 2020

For n >= 3, a(n) = A063377(n-1).

A339581 Indices of records in A063377.

Original entry on oeis.org

1, 2, 89, 1122659, 19099919, 85864769, 26089808579, 554688278429, 4090932431513069, 95405042230542329

Offset: 1

N. J. A. Sloane, Dec 24 2020

The records themselves begin 0,5,6,7,8,9,10,12,13,14.
a(11) <= 90616211958465842219 = A005602(15). Between a(10) and this upper bound could be another record which might not be listed in A005602.
a(n) == 9 mod 10 for n > 2 (see A063377). - Michael S. Branicky, Dec 24 2020

Carl Pomerance, Problem 81:21 (= 321), in R. K. Guy link.

R. K. Guy, editor, Western Number Theory Problems, 1985-12-21 & 23, Typescript, Jul 13 1986, Dept. of Math. and Stat., Univ. Calgary, 11 pages. Annotated scan of pages 1, 3, 7, 9, with permission.

Cf. A005602, A057331, A063377, A063378, A339579, A339580.

a(n) = A057331(n + 2) for n >= 2. - David A. Corneth, Dec 25 2020

a(6) corrected and a(7) found by David A. Corneth, Dec 24 2020.

a(8)-a(10) were taken from A057331 and the bound on a(11) was taken from A005602. - David A. Corneth and Amiram Eldar, Dec 25 2020

A321058 Indices of records in A067849.

Original entry on oeis.org

1, 2, 44, 561329, 9549959, 42932384, 13044904289, 277344139214, 2045466215756534, 47702521115271164

Offset: 1

Torlach Rush, Oct 26 2018

The corresponding record values are 2,4,6,7,8,9,10,12,13,14.
From David A. Corneth, Nov 10 2018: (Start)
Terms a(n) are of the form 3*k+2 for n > 1.
If 2^k - 1 is composite then a(n) is not divisible by any prime factor of 2^k-1 for n > k. So for example, gcd(a(n), 105) = 1 for n > 5. (End)
From Glen Whitney, Sep 14 2022: (Start)
Similarly to Corneth's observations, modulo any prime p, any residue for a(n) of the form 2^k - 1 mod p is forbidden for n greater than or equal to the number of such residues; for example a(n) may not be congruent to 0, 1, or 3 mod 7 for n >= 3.
For n > 2, if a(n) appears in this sequence, 2a(n) + 1 must appear in A057331. (End)

			2 is a term because A067849(2) = 4 > A067849(1) = 2.
44 is a term because A067849(44) = 6 > A067869(2) = 4.

Cf. A067849, A005602, A057331, A063378.

b(n) = {my(nb = 0, newn); while (isprime(newn=2*n+1), nb++; n = newn); nb;} \\ A067849
lista(nn) = {my(mmax = -1, mm); for (n=1, nn, if ((mm=b(n)) > mmax, mmax = mm; print1(n, ", ")););} \\ Michel Marcus, Nov 10 2018

a(7) from Amiram Eldar, Nov 10 2018

a(8)-a(10) from A057331 by Glen Whitney, Sep 14 2022

cp's OEIS Frontend

A063377 Sophie Germain degree of n: number of iterations of n under f(k) = 2k+1 before we reach a number that is not a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A339579 a(n) = least nonnegative integer k such that n*2^k - 1 is composite.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

A339581 Indices of records in A063377.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A321058 Indices of records in A067849.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions