How many steps does it take from n to 1 by subtracting the greatest divisor?

Jelly, 9 bytes

ÆṪÐĿÆFL€S

Try it online! or verify all test cases.

Background

The definition of sequence A064097 implies that

definition

By Euler's product formula

Euler's product formula

where φ denotes Euler's totient function and p varies only over prime numbers.

Combining both, we deduce the property

first property

where ω denotes the number of distinct prime factors of n.

Applying the resulting formula k + 1 times, where k is large enough so that φk+1(n) = 1, we get

second property

From this property, we obtain the formula

formula

where the last equality holds because ω(1) = 0.

How it works

ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.

05AB1E, 13 11 bytes

Code:

[DÒ¦P-¼D#]¾

Explanation:

[        ]   # An infinite loop and...
       D#        break out of the loop when the value is equal to 1.
 D           # Duplicate top of the stack (or in the beginning: duplicate input).
  Ò          # Get the prime factors, in the form [2, 3, 5]
   ¦         # Remove the first prime factor (the smallest one), in order to get 
               the largest product.
    P        # Take the product, [3, 5] -> 15, [] -> 1.
     -       # Substract from the current value.
      ¼      # Add one to the counting variable.
          ¾  # Push the counting variable and implicitly print that value.

Uses CP-1252 encoding. Try it online!.


Pyth, 11 bytes

fq1=-Q/QhPQ

Test suite

A straightforward repeat-until-true loop.

Explanation:

fq1=-Q/QhPQ
               Implicit: Q = eval(input())
f              Apply the following function until it is truthy,
               incrementing T each time starting at 1:
         PQ    Take the prime factorization of Q
        h      Take its first element, the smallest factor of Q
      /Q       Divide Q by that, giving Q's largest factor
    -Q         Subtract the result from Q
   =           Assign Q to that value
 q1            Check if Q is now 1.