A349670 Number of iterations x -> (x-1)/2 needed to get 1, 2 or a composite number, when starting with prime(n).

0, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Author

Jianing Song, Nov 24 2021

Keywords

• nonn

Comments

a(n) is the least k such that (prime(n) + 1)/2^k - 1 is 1, 2 or a composite number. It follows that a(n) <= v2(prime(n) + 1), v2 = A007814.

For prime(n) != 5, a(n) > 1 if and only if prime(n) is a safe prime (A005385).

Examples

			47 -> 23 -> 11 -> 5 -> 2 (prime(15) -> prime(9) -> prime(5) -> prime(3) -> prime(1)), hence a(1) = 0, a(3) = 1, a(5) = 2, a(9) = 3, a(15) = 4.
7 -> 3 -> 1 (prime(4) -> prime(2) -> 1), hence a(2) = 1, a(4) = 2.
59 -> 29 -> 14 (prime(17) -> prime(10) -> 14), hence a(10) = 1, a(17) = 2.
		

Crossrefs

Cf. A181697, A181715, A349671, A007814, A005385.

Programs

Mathematica

a[n_] := -1 + Length @ NestWhileList[(# - 1)/2 &, Prime[n], OddQ[#] && PrimeQ[#] &]; Array[a, 90] (* Amiram Eldar, Nov 27 2021 *)

PARI

a(n) = my(p=prime(n), k=0); while(isprime(m = (p+1)>>k - 1) && m != 2, k++); k