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,3

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.

Links

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

Example

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

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

Prog

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

Crossrefs

Cf. A340008, A340418, A006577.

Sequence in context: A020806 A030210 A367110 * A384713 A098798 A392859

Adjacent sequences: A339988 A339989 A339990 * A339992 A339993 A339994

Keyword

nonn

Author

Ya-Ping Lu, Dec 25 2020

Status

approved