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
By Euler's product formula
where φ denotes Euler's totient function and p varies only over prime numbers.
Combining both, we deduce the 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
From this property, we obtain the 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.