Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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,changed
%O 1,4
%A _Kevin Ryde_, May 30 2023