login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of steps x -> x+1 or x/prime required to go from n to 1.
2

%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