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

Question

Inspired by this question over at Mathematics.

---

The Problem

Let n be a natural number ≥ 2. Take the biggest divisor of n – which is different from n itself – and subtract it from n. Repeat until you get 1.

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, where n ≥ 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 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n > 1.

• Sparr: clarify the input requirement in languages with native arbitrary precision integers?
• insertusernamehere: @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.
• Luis Mendo: I like how the title sums it all up

Answer 1

BQN, 24 bytes

{1:0;1+Sx-⊢ ́↕⊸(⊣/ ̃0=|)x}

Anonymous function that takes a number and returns the number of steps. Try it at BQN online!

The algorithm works for any number in theory. In practice, since it constructs a range from 0 to N-1, it runs out of memory for large inputs. For inputs above \2ドル^{32}-1\$, BQN refuses to even make an array that big; but fortunately, the OP has commented that those inputs do not need to be handled.

Explanation

{1:0;1+Sx-⊢ ́↕⊸(⊣/ ̃0=|)x}
{ } Anonymous block function
 1: If the argument is 1:
 0 Return 0
 ; Otherwise:
 x Apply the following tacit function to the argument:
 ↕⊸( ) Use range(argument) as the left arg to this binary function:
 | Mod (i.e. take x mod each number in range(x))
 0= Compare each with 0
 ⊣/ ̃ Keep only the ones that compared equal to 0 (perfect divisors)
 ⊢ ́ Get the last element of the list of divisors
 x- Subtract it from the argument
 S Call this function on that value recursively
 1+ Add 1 to the result

Answer 2

C (clang), 45 bytes

g;l(f){for(g=f;f%--g;);return f<3?:1+l(f-g);}

inspired by this answer to a similar question.

Try it online!

• att: -5 by replacing return with an assignment

Answer 3

Pyth, (削除) 17 (削除ここまで) 16 bytes

L?tbhy-b*F+1tPb0

Try it online! (The y.v at the end is for function calling)

---

Original 17 bytes:

L?tb+1y-b*F+1tPb0

Try it online! (The y.v at the end is for function calling)

(I actually answered that question with this Pyth program.)

• Maltysen: I didn't actually bother going through your program, but if you're using the recursive definition in the OP, u is probably shorter than actual recursion.

Answer 4

Pyke, 11 bytes (noncompeting)

D3Phf-oRr;o

This uses a new behaviour where if there is an exception raised after a goto, it restores the state from before the goto (except variable definitions) and continues. In this case it is equivalent to the following python code:

# Implicit input and variable setup
inp = input()
o = 0
# End implicit
try:
 while 1:
 inp -= factors(inp)[0] # If factors is called on the value 1, it returns an empty
 # list which when the first element tries to be accessed
 # raises an exception
 o += 1 # Using `o` returns the current value of `o` and increments it
except:
 print o # This in effect gets the number of times the loop went

This is all possible using Pyke without a while loop construction - yay goto!

Try it here!

Answer 5

JavaScript (ES6), (削除) 70 (削除ここまで) 54 bytes

f=(n,i=2)=>n<i?0:n%i?f(n,i+1):n>i?f(i)+f(n/i):1+f(n-1)

Implementation of the provided recursive formula, but now updated to use recursion to find the divisor too.

Answer 6

Perl, 57 + 1 (-p flag) = 58 bytes

$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{

Usage:

> echo 31 | perl -pe '$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{'

Ungolfed:

while (<>) {
# code above added by -p
 # $_ has input value
 # $\ has undef (or 0)
 my $n = $_;
 while ($n > 1) {
 my $d = 1;
 for (2 .. ($n / 2)) {
 if ($n % $_ == 0) {
 $d = $n / $_;
 last;
 }
 }
 $n -= $d;
 $\++;
 }
} {
# code below added by -p
 print; # prints $_ (undef here) and $\
}

Answer 7

Clojure, (削除) 98 (削除ここまで) 96 bytes

#(loop[n % i -1](if n(recur(first(for[j(range(dec n)0 -1):when(=(mod n j)0)](- n j)))(inc i))i))

uses for :when to find the largest divisor, loops until no such value larger than one is found.

Answer 8

Java (JDK 10), 60 bytes

n->{int c=0,d;for(;n>1;c++,n-=d)for(d=n;n%--d>0;);return c;}

Try it online!

• FlipTack: You don't need the parenthesis around n->

Answer 9

x86, (削除) 24 (削除ここまで) 23 bytes

Straightforward implementation of problem. Input in ecx, output in edi.

I wonder if there's a way to test if n > 1 in less than 3 bytes...

-1 by using cdq to zero edx. This requires the input to be a positive signed number (<=2^31-1), which I think is reasonable.

.section .text
.globl main
main:
 mov 100,ドル %ecx # n = 100
start:
 xor %edi, %edi # result = 0
loop1:
 mov %ecx, %ebx # d = n
loop2: 
 dec %ebx # --d
 mov %ecx, %eax 
 cdq 
 div %ebx # n % d 
 test %edx, %edx
 jnz loop2 # do while (n % d) 
 inc %edi # ++result
 sub %ebx, %ecx # n -= d 
 cmp 1,ドル %ecx
 ja loop1 # do while (n > 1)
 
 ret

Hexdump:

00000039 31 ff 89 cb 4b 89 c8 99 f7 f3 85 d2 75 f6 47 29 |1...K.......u.G)|
00000049 d9 83 f9 01 77 ec c3 |....w..|

Answer 10

Japt v1.4.5, 8 bytes

Had to switch to Japt v1.4.5 and sacrifice a byte to get around a bug with the â method in v1.4.6+. @μk ×ばつ}f would work for the same bytes count in those versions, but that's just a golfed version of ETH's solution.

@Uμâ¬Ì}f

Try it

Answer 11

Husk, 9 bytes

LU¡Ṡ-ȯ→hḊ

Try it online!

Answer 12

Haskell, 42 bytes

f 1=0
f n=1+f(n-maximum(gcd n<$>[1..n-1]))

Try it online!

Answer 13

Batch, (削除) 139 (削除ここまで) 136 bytes (Uses LF line delimiters)

@set/an=%1-1
:]
@for /l %%n in (1 1 %n%)do @((cmd/c"set/a1/((n+1)%%%%n)")||set[=%%n)>x 2>y
@set/at+=1,n-=[
@if %n% NEQ 0 goto]
@echo %t%

n should be supplied as the first command line argument %1.
n is limited to 32-bit integers.

---

If passing arbitrary command line arguments is allowed, the code above can be shortened by another 6 bytes

124 (code) + 6 (extra argument length) = 130 bytes

%2n=%1-1
:]
@for /l %%n in (1 1 %n%)do @((cmd/c"%21/((n+1)%%%%n)")||%2[=%%n)>x 2>y
%2t+=1,n-=[
@if %n% NEQ 0 goto]
@echo %t%

Run it like code.bat <n> @set/a

Answer 14

Brachylog, 15 bytes

;.{fkt;?-ṅ}i)1∧

Try it online!

Explanation

;.{ }i)1∧ Iterate <Output> times until you get 1
 f Get the factors of the input, ordered
 kt Take the penultimate one
 ;?- Subtract the input
 ṅ Negate

Answer 15

dc, 39 bytes

0[1+rd[d3R1-d_4R%0<t]dstxr-d_3R1<l]dslx

Try it online!

Takes input as number on top of stack, and leaves result as top of stack

Answer 16

Excel VBA, (削除) 121 (削除ここまで) (削除) 110 (削除ここまで) 107 bytes

Sub a
o=[A1]
For i=o-1To 1Step-1
If o=WorksheetFunction.Lcm(o,i)Then[A1]=o-i:[B1]=[B1]+1:a
Next
End
End Sub

This presumes you start with a new, blank sheet (what you get when you open a new file). Input is in cell A1. Output is in cell B1. VBA will add spaces automatically then that code is pasted in. It is equivalent to this formatted and commented version:

Sub a()
 o = [A1] 'Store the starting value to save bytes later
 For i = o - 1 To 1 Step -1 'Start at 1 less than the starting value and count down
 If o = WorksheetFunction.Lcm(o, i) Then 'If the LCM is the starting value then the current value is a divisor
 [A1] = o - i 'Subtract the current value from the starting value and set it as the new starting value
 [B1] = [B1] + 1 'Increase the count by 1
 a 'Recurse
 End If
 Next
 End 'You only get here if the for loop was skipped meaning o=1 (since "For i=0 to 1 Step -1" will just skip) so we can end all code now
End Sub

The maximum integer value in VBA is 32767 and the program above output 21 given that input as shown in the GIF below (with an added 1 second pause between each calculation).

GIF

• Taylor Raine: You can drop the () in the sub definition, and drop a byte by rearranging the if statement to read as If o=WorksheetFunction.Lcm(o, i)Then ...

Answer 17

APL, 21 bytes

{1=⍵:0⋄1+∇⍵-⍵⌈.∨⍳⍵-1}

• pxeger: You have an extra space at the start of your code which can be removed

Answer 18

PARI/GP, 61 bytes

Try it online!

f(1)=0;
f(n)=if(n==1,0,f(n-divisors(n)[#(divisors(n))-1])+1);

Answer 19

PowerShell, 75 bytes

param($i)$a=0;while($i-gt1){$i=$i-(($i-1)..1|%{($_)[$i%$_-ne0]})[0];$a++}$a

Try it online!