50
7
Inspired by this question over at Mathematics.
The Problem
Let
n
be a natural number≥ 2
. Take the biggest divisor ofn
– which is different fromn
itself – and subtract it fromn
. Repeat until you get1
.
The Question
How many steps does it take to reach 1
for a given number n ≥ 2
.
Detailed Example
Let
n = 30
.
The greatest divisor of:
1. 30 is 15 --> 30 - 15 = 15
2. 15 is 5 --> 15 - 5 = 10
3. 10 is 5 --> 10 - 5 = 5
4. 5 is 1 --> 5 - 1 = 4
5. 4 is 2 --> 4 - 2 = 2
6. 2 is 1 --> 2 - 1 = 1
It takes 6 steps to reach 1
.
Input
- Input is an integer
n
, wheren ≥ 2
. - Your program should support input up to the language's maximum integer value.
Output
- Simply output the number of steps, like
6
. - Leading/trailing whitespaces or newlines are fine.
Examples
f(5) --> 3
f(30) --> 6
f(31) --> 7
f(32) --> 5
f(100) --> 8
f(200) --> 9
f(2016^155) --> 2015
Requirements
- You can get input from
STDIN
, command line arguments, as function parameters or from the closest equivalent. - You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.
- This is code-golf so shortest answer in bytes wins.
- Standard loopholes are disallowed.
This series can be found on OEIS as well: A064097
A quasi-logarithm defined inductively by
a(1) = 0
anda(p) = 1 + a(p-1)
ifp
is prime anda(n*m) = a(n) + a(m)
ifm,n > 1
.
clarify the input requirement in languages with native arbitrary precision integers? – Sparr – 2016-05-09T22:20:53.003
@Sparr I would say, you should at least support up to
2^32 - 1
. The rest is up to you and your system. Hope, this is what you meant with your question. – insertusernamehere – 2016-05-09T23:16:44.4603I like how the title sums it all up – Luis Mendo – 2016-05-10T21:33:14.857