login
A349671
Number of iterations x -> (x+1)/2 needed to get 2 or a composite number, when starting with prime(n).
1
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).
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
KEYWORD
nonn
AUTHOR
Jianing Song, Nov 24 2021
STATUS
approved