A363369 - OEIS

A363369

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

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, 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, 2, 2, 1, 2, 1, 2, 3, 3, 2, 2, 1, 3, 3, 2, 1, 3, 2, 2, 2

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

Each step is to any one of x+1 or x/p where p is a prime factor of x.

These steps are the game in A362416 and a(n) is the length of the shortest possible game starting at n.

a(n) = 1 iff n is a prime.

a(n) = 2 iff n is a semiprime or n+1 is a prime >= 5.

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).

LINKS

Kevin Ryde, Table of n, a(n) for n = 1..10000

Kevin Ryde, PARI/GP Code

FORMULA

a(n) = Min_{i = n+1 or any n/prime} a(i), for n >= 2.

EXAMPLE

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.

PROG

(PARI) See links.

CROSSREFS

Cf. A362416 (winning x+1,x/p), A001222 (bigomega).

Sequence in context: A077480 A327524 A059829 * A304465 A304687 A076558

Adjacent sequences: A363366 A363367 A363368 * A363370 A363371 A363372

KEYWORD

nonn,easy

AUTHOR

Kevin Ryde, May 30 2023

STATUS

approved