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

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