cp's OEIS Frontend

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.

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