Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #14 Dec 19 2024 11:46:19
%S 0,1,1,2,1,2,1,3,2,2,1,2,1,2,2,2,1,2,1,3,2,2,1,3,2,2,3,2,1,2,1,3,2,2,
%T 2,2,1,2,2,2,1,2,1,3,3,2,1,3,2,3,2,2,1,3,2,3,2,2,1,2,1,2,3,3,2,2,1,3,
%U 2,2,1,2,1,2,3,3,2,2,1,3,3,2,1,3,2,2,2
%N Number of steps x -> x+1 or x/prime required to go from n to 1.
%C Each step is to any one of x+1 or x/p where p is a prime factor of x.
%C These steps are the game in A362416 and a(n) is the length of the shortest possible game starting at n.
%C a(n) = 1 iff n is a prime.
%C a(n) = 2 iff n is a semiprime or n+1 is a prime >= 5.
%C a(n) <= bigomega(n) since steps x/prime can divide out each prime successively (though often x+1 steps help make a shorter path to 1).
%H Kevin Ryde, <a href="/A363369/b363369.txt">Table of n, a(n) for n = 1..10000</a>
%H Kevin Ryde, <a href="/A363369/a363369.gp.txt">PARI/GP Code</a>
%F a(n) = Min_{i = n+1 or any n/prime} a(i), for n >= 2.
%e For n=80, steps 80 -> 40 -> 41 -> 1 (being /2, +1, /41) reach 1 after 3 steps and are the fewest possible so a(80) = 3.
%o (PARI) \\ See links.
%Y Cf. A362416 (winning x+1,x/p), A001222 (bigomega).
%K nonn,easy
%O 1,4
%A _Kevin Ryde_, May 30 2023