A063377 -id:A063377 - cp's OEIS frontend

A063378 Smallest number whose Sophie Germain degree (see A063377) is n.

4, 7, 3, 11, 5, 2, 89, 1122659, 19099919, 85864769, 26089808579, 665043081119, 554688278429, 4090932431513069, 95405042230542329

Offset: 0

Reiner Martin, Jul 14 2001

Also known as Cunningham chains of length n of the first kind.

For each positive integer n, is there some integer with Sophie Germain degree of n?

			Using f(x)=2x+1, 11 -> 23 -> 47 -> 95, which is composite; thus a(3)=11.

Warut Roonguthai, Yves Gallot's Proth.exe and Cunningham Chains

Cf. A005384, A063377.

NextPrim[n_] := Block[{k = n + 1}, While[ !PrimeQ[k], k++ ]; k]; f[n_] := Block[{k = 2}, While[ Length[ NestWhileList[2# + 1 &, k, PrimeQ]] != n + 1, k = NextPrim[k]]; k]; Table[f[n], {n, 1, 8}]

More terms from Jud McCranie, Jul 20 2001

Edited and extended by Robert G. Wilson v, Nov 21 2002

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

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).

A093007 First nonprime number reached when iterating n under x->2*x+1.

Original entry on oeis.org

1, 95, 15, 4, 95, 6, 15, 8, 9, 10, 95, 12, 27, 14, 15, 16, 35, 18, 39, 20, 21, 22, 95, 24, 25, 26, 27, 28, 119, 30, 63, 32, 33, 34, 35, 36, 75, 38, 39, 40, 335, 42, 87, 44, 45, 46, 95, 48, 49, 50, 51, 52, 215, 54, 55, 56, 57, 58, 119, 60, 123, 62, 63, 64, 65, 66, 135

Offset: 1

Reinhard Zumkeller, Mar 14 2004

nonn

			n = 41 = A000040(13) -> 2*41+1 = 83 = A000040(23) -> 2*83+1 = 167 = A000040(39) -> 2*167+1 = 335 = 67*5, therefore a(41) = 335, A063377(41) = 3.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000040, A000120, A038699, A063377, A070939, A093009.

Table[NestWhile[2#+1&,n,PrimeQ],{n,70}] (* Harvey P. Dale, Sep 25 2012 *)

n>1: A070939(a(n)) = A070939(n) + A063377(n), A000120(a(n)) = A000120(n) + A063377(n).

Definition corrected by Harvey P. Dale, Sep 25 2012

A323161 Lexicographically earliest sequence such that a(i) = a(j) => f(i) = f(j) for all i, j, where f(n<=3) = -n, f(n) = 0 if n-1 is an odd prime, and f(n) = floor((n-1)/2) for all other numbers.

Original entry on oeis.org

1, 2, 3, 4, 5, 4, 6, 4, 7, 7, 8, 4, 9, 4, 10, 10, 11, 4, 12, 4, 13, 13, 14, 4, 15, 15, 16, 16, 17, 4, 18, 4, 19, 19, 20, 20, 21, 4, 22, 22, 23, 4, 24, 4, 25, 25, 26, 4, 27, 27, 28, 28, 29, 4, 30, 30, 31, 31, 32, 4, 33, 4, 34, 34, 35, 35, 36, 4, 37, 37, 38, 4, 39, 4, 40, 40, 41, 41, 42, 4, 43, 43, 44, 4, 45, 45, 46, 46, 47, 4, 48, 48, 49, 49, 50, 50, 51, 4, 52, 52, 53, 4, 54, 4

Offset: 1

Antti Karttunen, Jan 06 2019

nonn

For all i, j: A322809(i) = A322809(j) <=> a(i+1) = a(j+1).
For all i, j: a(i) = a(j) => b(i) = b(j), where b can be, but is not limited to, any of the following sequences: A029834, A049084, A062590, A063377, A064891, A078442 (A049076), A175663, A175682, A269668, A292936, A323162, many of which are related to counting primes in certain kinds of chains or iterations.
Why does this work? Consider the function f given in the definition: based on its properties, we can deduce from the value of f(n) the following information about n:
  (A) If f(n) = -2, then n is 2, the only even prime,
  (B) If f(n) = -3, then n is 3, the first odd prime,
  (C) If f(n) is zero, then n is an even composite preceded by a prime, but we don't know which even composite exactly,
  (D) If f(n) > 0 and f(1+2*f(n)) = f(2+2*f(n)), then n is either (D1) an odd composite number, or (D2) an even composite number preceded by an odd composite number, and the said composite number in both cases is 1 + 2*f(n),
  (E) If f(n) > 0 and f(1+2*f(n)) <> f(2+2*f(n)), then n is an odd prime > 3, specifically, 1 + 2*f(n).
As this sequence is a restricted growth sequence transform of the said function f, we have a(i) = a(j) <=> f(i) = f(j) for all i, j, thus, even without knowing the value of n, but just a(n), we can find the value of f(n) by searching for the minimal k such that a(k) = a(n), then compute f(k) with that k. Furthermore, any function g defined as g(n) = h(f(n)) [where h is any function], clearly satisfies
  a(i) = a(j) => g(i) = g(j), for all i, j. [*]
For instances of such functions g, we can consider many sequences like those sequences b(n) listed above, that have g(n) = 0 for all composite numbers, and g(p) > 0 for all primes p. This is usually the pattern, but there are exceptions, like A323162, which is the characteristic function of A005381, composites n such that n-1 is also composite. These are precisely the numbers that occur twice in this sequence, while all other numbers (including primes), occur just once, that is, reside in their own singular equivalence classes. Thus, it is not guaranteed that all sequences g matching to this sequence (i.e. those satisfying the implication *), even if not false positives in strict sense, would necessarily have some consistent relation to primes, instead, they might contain any random values at the positions given by A093515. However, in the current OEIS, such sequences are exceedingly rare.

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

Cf. A305801, A305900, A322809.
Cf. A005381 (numbers that occur twice in this sequence), A093515 (numbers > 1 that occur just once).
Cf. A010051, A029834, A049076, A049084, A062590, A063377, A064891, A078442, A175663, A175682, A269668, A292936, A323162 (some of the matched sequences).

up_to = 10000;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A323161aux(n) = if(n<=3,-n,if(isprime(n-1),0,((n-1)>>1))); \\ This implements the function f of the definition.
v323161 = rgs_transform(vector(up_to,n,A323161aux(n)));
A323161(n) = v323161[n];

a(1) = 1; for n > 1, a(n) = 1 + A322809(n-1).

A324642 Number of iterations of map x -> x + A002110(A235224(x)) required to reach a composite when starting from x = n. Here A002110(A235224(x)) gives the least primorial number > x.

Original entry on oeis.org

2, 1, 1, 0, 4, 0, 2, 0, 0, 0, 3, 0, 2, 0, 0, 0, 3, 0, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 5, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 4, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 5, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 3, 0, 2, 0, 0

Offset: 1

Antti Karttunen, Mar 11 2019

nonn

			For n=1, it is not a composite number, so we add a next larger primorial (A002110) to it, which is 2, and we see that 3 is also noncomposite, thus we add to that the next larger primorial, which is 6, but now 3+6 = 9 is composite, which we reached in two iteration steps, thus a(1) = 2.
For n = 97, the iteration goes as: 97 -> 307 -> 2617 -> 32647 -> 543157 -> 10242847 -> 233335717 -> 6703028947 -> 207263519077, and only the last term shown is composite, thus a(97) = 8. Written in primorial base (A049345), the terms in that trajectory look as: 3101, 13101, 113101, 1113101, 11113101, 111113101, 1111113101, 11111113101 and 111111113101.

Cf. A002110, A049345 (A324550), A235224.

Cf. also A063377, A324656.

A002110(n) = prod(i=1,n,prime(i));
A235224(n, p=2) = if(nA235224(n\p, nextprime(p+1)));
A324642(n) = { my(k=0); while((1==n)||isprime(n), n += A002110(A235224(n)); k++); (k); };

If n is composite, a(n) = 0, and for noncomposite n, a(n) = 1 + a(n+A002110(A235224(n))).

A093008 Smallest number of 1's to append to the binary representation of n such that primes become nonprimes and nonprimes become primes.

Original entry on oeis.org

1, 5, 2, 2, 4, 1, 1, 1, 1, 2, 3, 3, 1, 1, 1, 2, 1, 1, 1, 1, 1, 4, 2, 3, 2, 1, 3, 4, 2, 1, 1, 2, 1, 2, 1, 1, 1, 3, 1, 2, 3, 7, 1, 1, 3, 4, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 3, 12, 1, 3, 1, 2, 1, 4, 1, 5, 1, 1, 1, 2, 1, 7, 1, 1, 1, 2, 2, 1, 1, 3, 1, 2, 2, 5, 6, 1, 23, 4, 6, 1, 2, 3, 3, 2, 1, 1, 1, 1, 1, 10

Offset: 1

Reinhard Zumkeller, Mar 14 2004

nonn

n>1: a(n) = A063377(n) + A040081(n+1).

Cf. A093009.

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

A063378 Smallest number whose Sophie Germain degree (see A063377) is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A339581 Indices of records in A063377.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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

A093007 First nonprime number reached when iterating n under x->2*x+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A323161 Lexicographically earliest sequence such that a(i) = a(j) => f(i) = f(j) for all i, j, where f(n<=3) = -n, f(n) = 0 if n-1 is an odd prime, and f(n) = floor((n-1)/2) for all other numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A324642 Number of iterations of map x -> x + A002110(A235224(x)) required to reach a composite when starting from x = n. Here A002110(A235224(x)) gives the least primorial number > x.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A093008 Smallest number of 1's to append to the binary representation of n such that primes become nonprimes and nonprimes become primes.

Views

Author

Keywords

Comments

Crossrefs

A339580 Indices of records in A339579.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula