A339581 -id:A339581 - 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).

A339580 Indices of records in A339579.

Original entry on oeis.org

1, 3, 90, 1122660, 19099920, 85864770, 26089808580, 554688278430, 4090932431513070, 95405042230542330

Offset: 1

N. J. A. Sloane, Dec 24 2020

The records themselves begin 4,5,6,7,8,9,10,12,13,14.

a(11) <= 90616211958465842220.

			90 is in the sequence as A339579(90) = 6 (90*2^k - 1 is prime for k = 0..5 and composite for k = 6) and A339579(m) < 6 for m < 90. - _David A. Corneth_, Dec 24 2020

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

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. A063377, A124514, A125113, A339579, A339581.

a(n) = A339581(n) + 1 for n >= 2. - 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

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

A339580 Indices of records in A339579.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions