The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #19 Jun 27 2024 11:38:09
%S 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,
%T 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,
%U 18,19,12,13,24,27,13,32,19,20,6,7,7,21,12,13,13,27
%N 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.
%C Conjecture: a(n) is never equal to -1.
%C 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.
%e The 39 starting numbers with a(n) <= 9 are given in the figure below.
%e 10 50 7 49 96 145 288 133 264 260 258 512
%e \ \ \ | / \ / \ / / / /
%e 5 25 48 144 132 130 129 256
%e \ | / \ \ \ \ /
%e 24 72 66 65 128
%e \ \ \ \ /
%e 12 36 33 64
%e \ \ \ /
%e 6 18 32
%e \ \ /
%e 3 9 16
%e \ | /
%e 8
%e |
%e 4
%e |
%e 2
%e |
%e 1
%p A339991 := proc(n)
%p local a,x;
%p x := n ;
%p a := 0 ;
%p while x > 1 do
%p if type(x,even) then
%p x := x/2 ;
%p elif isprime(x) then
%p x := x^2-1 ;
%p else
%p x := x-1 ;
%p end if ;
%p a := a+1 ;
%p end do:
%p a ;
%p end proc:
%p seq(A339991(n),n=1..50) ; # _R. J. Mathar_, Jun 27 2024
%t Array[-1 + Length@ NestWhileList[Which[EvenQ@ #, #/2, PrimeQ@ #, #^2 - 1, True, # - 1] &, #, # > 1 &] &, 71] (* _Michael De Vlieger_, Dec 28 2020 *)
%o (Python)
%o from sympy import isprime
%o for n in range(1, 1001):
%o ct, m = 0, n
%o while m > 1:
%o if m%2 == 0: m /= 2
%o elif isprime(m) == 1: m = m*m - 1
%o else: m -= 1
%o ct += 1
%o print(ct)
%o (PARI) f(n) = if (n%2, if (isprime(n), n^2-1, n-1), n/2);
%o a(n) = my(nb=0); while (n != 1, n = f(n); nb++); nb; \\ _Michel Marcus_, Dec 26 2020
%Y Cf. A340008, A340418, A006577.
%K nonn
%O 1,3
%A _Ya-Ping Lu_, Dec 25 2020