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

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

Offset

1,3

Comments

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

For prime(n) != 3, a(n) > 1 if and only if (prime(n)+1)/2 is prime (A005383).

Links

Table of n, a(n) for n=1..90.

Example

5 -> 3 -> 2 (prime(3) -> prime(2) -> prime(1)), hence a(1) = 0, a(2) = 1, a(3) = 2.
13 -> 7 -> 4 (prime(6) -> prime(4) -> 4), hence a(4) = 1, a(6) = 2.
73 -> 37 -> 19 -> 10 (prime(21) -> prime(12) -> prime(8) -> 10), hence a(8) = 1, a(12) = 2, a(21) = 3.

Mathematica

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

Prog

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

Crossrefs

Cf. A181697, A181715, A349670, A007814, A005383.

Sequence in context: A030382 A354614 A192004 * A120889 A322351 A092523

Adjacent sequences: A349668 A349669 A349670 * A349672 A349673 A349674

Keyword

nonn

Author

Jianing Song, Nov 24 2021

Status

approved