A339991 The number of steps that n requires to reach 1 under the map: m -> m/2 if m is even, m-> m^2 - 1 if m is an odd prime, otherwise m -> m - 1. a(n) = -1 if 1 is never reached.

0, 1, 4, 2, 8, 5, 9, 3, 4, 9, 15, 6, 15, 10, 11, 4, 10, 5, 22, 10, 11, 16, 11, 7, 8, 16, 17, 11, 23, 12, 18, 5, 6, 11, 12, 6, 20, 23, 24, 11, 24, 12, 21, 17, 18, 12, 19, 8, 9, 9, 10, 17, 31, 18, 19, 12, 13, 24, 27, 13, 32, 19, 20, 6, 7, 7, 21, 12, 13, 13, 27

Offset: 1

Author

Ya-Ping Lu, Dec 25 2020

Keywords

• nonn

Comments

Conjecture: a(n) is never equal to -1.

An even node (m) in the tree shown in Example can have up to three predecessors: 2*m, sqrt(m+1) if sqrt(m+1) is a prime, and m+1 if m+1 is a nonprime odd number. An odd node has only one predecessor: 2*m.

Examples

			The 39 starting numbers with a(n) <= 9 are given in the figure below.
10 50 7 49 96 145 288 133 264 260 258 512
  \  \ \ | /   \  /    \ /    /   /   /
   5 25 48     144     132  130  129 256
    \ | /        \       \    \   \ /
     24          72      66  65  128
       \          \       \   \  /
        12        36      33   64
          \        \       \  /
           6       18       32
             \      \      /
               3    9   16
                  \ | /
                    8
                    |
                    4
                    |
                    2
                    |
                    1
		

Crossrefs

Cf. A340008, A340418, A006577.

Programs

Maple

A339991 := proc(n)
    local a,x;
    x := n ;
    a := 0 ;
    while x > 1 do
        if type(x,even) then
            x := x/2 ;
        elif isprime(x) then
            x := x^2-1 ;
        else
            x := x-1 ;
        end if ;
        a := a+1 ;
    end do:
    a ;
end proc:
seq(A339991(n),n=1..50) ; # R. J. Mathar, Jun 27 2024

Mathematica

Array[-1 + Length@ NestWhileList[Which[EvenQ@ #, #/2, PrimeQ@ #, #^2 - 1, True, # - 1] &, #, # > 1 &] &, 71] (* Michael De Vlieger, Dec 28 2020 *)

PARI

f(n) = if (n%2, if (isprime(n), n^2-1, n-1), n/2);
a(n) = my(nb=0); while (n != 1, n = f(n); nb++); nb; \\ Michel Marcus, Dec 26 2020

Python

from sympy import isprime
for n in range(1, 1001):
    ct, m = 0, n
    while m > 1:
        if m%2 == 0: m //= 2
        elif isprime(m) == 1: m = m*m - 1
        else: m -= 1
        ct += 1
    print(ct)