A349670 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

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

LINKS

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

EXAMPLE

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.

MATHEMATICA

a[n_] := -1 + Length @ NestWhileList[(# - 1)/2 &, Prime[n], 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, A349671, A007814, A005385.

Sequence in context: A112465 A112468 A207194 * A086275 A066855 A175685

Adjacent sequences: A349667 A349668 A349669 * A349671 A349672 A349673

KEYWORD

nonn

AUTHOR

Jianing Song, Nov 24 2021

STATUS

approved