A179767 a(n) is the smallest prime of the form 4k + 3 such that the first n iterations of the map p -> 4p + 3 are prime with the next iteration being composite.

3, 19, 7, 179, 1447, 32059, 55171, 17231, 32611, 644823367, 8870650619, 10808693851, 26813406071

Offset

0,1

Comments

This sequence is finite and complete. Proof:

Suppose a(9) = p exists. Then, we obtain the sequence of 10 primes:

E = {4p + 3 -> 16p + 15 -> 64p + 63 ->...-> (2^20)p + (2^22 - 1)}.

The prime divisors or 2^(2*q) - 1 for q = 1,2,...,11 are

(2^2 - 1) -> {3};

(2^4 - 1) -> {3, 5};

(2^6 - 1) -> {3, 7};

(2^8 - 1) -> {3, 5, 17};

(2^10 - 1) -> {3, 11, 31};

(2^12 - 1) -> {3, 5, 7, 13};

(2^14 - 1) -> {3, 43, 127};

(2^16 - 1) -> {3, 5, 17, 257};

(2^18 - 1) -> {3, 7, 19, 73};

(2^20 - 1) -> {3, 5, 11, 31, 41};

(2^22 - 1) -> {3, 23, 89, 683}.

But p == r (mod 32) where r is element of the set {3, 7, 11, 15, 19, 23, 27, 31}, and one of the ten numbers of E is divisible by r. For example, 27 | (2^18)p + 2^18 - 1 if p == 27 (mod 32).

Remark: the map p -> 4p + 1 is not interesting because the corresponding sequence contains only two numbers: a(0) = 5 and a(1) = 13 if we consider only 2 iterations {4p + 1 -> 16p + 5 -> 64p + 21}: if p==0 (mod 3) => 64p + 21 is composite, if p==1 (mod 3) => 16p + 5 is composite and if p==2 (mod 3) => 4p + 1 is composite.

From Michael S. Branicky, Mar 19 2021: (Start)

Proof of finiteness is incorrect. Flaw is last sentence: "For example, ...". Specifically, 27 does not divide quantity unless 27 | k where p = 32*k + 27.

No further terms < 10^11. (End)

Links

Table of n, a(n) for n=0..12.

Example

a(0) = 3 because 4*3 + 3 = 15 is composite => 0 iteration;
a(1) = 19 because 4*19 + 3 = 79 is prime => 1 iteration;
a(2) = 7 -> 31 -> 127 are primes => 2 iterations;
a(3) = 179 -> 719 -> 2879 -> 11519 are primes => 3 iterations;
a(8) = 32611 -> 130447 -> 521791 -> 2087167 -> 8348671 -> 33394687 -> 133578751 -> 534315007 -> 2137260031 are primes => 8 iterations.

Maple

with(numtheory):for m from 0 to 8 do: ii:=0:for i from 1 to 50000 do : n:=ithprime(i):if
  irem(n, 4) = 3 then nn:=n: id:=0:k:=0:for it from 1 to 8 do: p:=4*nn+3: if type
  (p, prime)=true and id=0 then k:=k+1:nn:=p:else id:=1:fi:od:if k=m and ii=0 then
  ii:=1:print(n):else fi:else fi:od:od:

Prog

(Python)
from sympy import isprime
def iters(p):
  c = 0
  while isprime(4*p + 3): p, c = 4*p + 3, c + 1
  return c
def a(n):
  k = 0
  while True:
    p, k = 4*k + 3, k + 1
    if isprime(p) and iters(p) == n: return p
print([a(n) for n in range(9)]) # Michael S. Branicky, Mar 19 2021

Crossrefs

Sequence in context: A114365 A084559 A272815 * A244605 A213602 A145688

Adjacent sequences: A179764 A179765 A179766 * A179768 A179769 A179770

Keyword

nonn,more,hard

Author

Michel Lagneau, Jan 10 2011

Extensions

a(9)-a(12) from Michael S. Branicky, Mar 19 2021

Status

approved