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 is an integer n, where n ≥ 2.
  • Your program should support input up to the language's maximum integer value.


  • Simply output the number of steps, like 6.
  • Leading/trailing whitespaces or newlines are fine.


f(5)        --> 3
f(30)       --> 6
f(31)       --> 7
f(32)       --> 5
f(100)      --> 8
f(200)      --> 9
f(2016^155) --> 2015


  • 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 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.

  • \$\begingroup\$ clarify the input requirement in languages with native arbitrary precision integers? \$\endgroup\$ – Sparr May 9 '16 at 22:20
  • \$\begingroup\$ @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. \$\endgroup\$ – insertusernamehere May 9 '16 at 23:16
  • 3
    \$\begingroup\$ I like how the title sums it all up \$\endgroup\$ – Luis Mendo May 10 '16 at 21:33

33 Answers 33


Jelly, 9 bytes


Try it online! or verify all test cases.


The definition of sequence A064097 implies that


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


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.
|improve this answer|||||
  • \$\begingroup\$ Now that is a super clever approach ! \$\endgroup\$ – Abr001am May 13 '16 at 15:59

05AB1E, 13 11 bytes




[        ]   # 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!.

|improve this answer|||||
  • 13
    \$\begingroup\$ Remove the first prime factor (the smallest one), in order to get the largest product How clever! :-) \$\endgroup\$ – Luis Mendo May 9 '16 at 13:58
  • \$\begingroup\$ I see, you are the language developer \$\endgroup\$ – Display Name May 11 '16 at 12:56
  • \$\begingroup\$ @SargeBorsch Yes, that is correct :) \$\endgroup\$ – Adnan May 11 '16 at 16:10
  • \$\begingroup\$ [¼Ñü-¤ÄD#]¾ - I was close to shaving off a byte with pairwise, oh well... \$\endgroup\$ – Magic Octopus Urn Jan 18 '17 at 18:57
  • \$\begingroup\$ -1 byte: [Ð#Ò¦P-¼]¾. Ð is better than DD. \$\endgroup\$ – Grimmy May 22 '19 at 13:13

Pyth, 11 bytes


Test suite

A straightforward repeat-until-true loop.


               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.
|improve this answer|||||
  • \$\begingroup\$ that's a really nice trick with filter. \$\endgroup\$ – Maltysen May 9 '16 at 20:49
  • 3
    \$\begingroup\$ I don't understand why this outputs the number of times the function ran. Is this an undocumented feature of f? \$\endgroup\$ – corsiKa May 10 '16 at 20:35
  • \$\begingroup\$ @corsiKa f without a second argument iterates over all positive integers starting from 1 and returns the first value that gives true on the inner statement. This value happens to be unused in this program, so it returns the number of times that it ran. Not undocumented, just unorthodox :) If it helps, you can think of this as a for loop like: for(int i=1; some_condition_unrelated_to_i; i++) { change_stuff_that_affects_condition_but_not_i;} \$\endgroup\$ – FryAmTheEggman May 13 '16 at 15:30
  • \$\begingroup\$ @corsiKa It's documented in the character reference on the right side of the online interpreter. With only one argument (f <l:T> <none>), f is First input where A(_) is truthy over [1, 2, 3, 4...]. \$\endgroup\$ – Dennis May 13 '16 at 15:31
  • \$\begingroup\$ Ah I understand it now. It uses that input but never uses the input in the calculation. That explains @Maltysen comment of "that's a really nice trick" because you only care about the iteration count not using that count anywhere in your filter. I love those ah-ha moments!: ) \$\endgroup\$ – corsiKa May 13 '16 at 15:48

Python 2, 50 49 bytes

f=lambda n,k=1:2/n or n%(n-k)and f(n,k+1)or-~f(k)

This isn't going to finish that last test case any time soon...

Alternatively, here's a 48-byte which returns True instead of 1 for n=2:

f=lambda n,k=1:n<3or n%(n-k)and f(n,k+1)or-~f(k)
|improve this answer|||||

Jelly, 10 bytes


Try it online! or verify most test cases. The last test cases finishes quickly locally.

How it works

ÆfḊPạµÐĿi2  Main link. Argument: n (integer)

Æf          Factorize n, yielding a list of primes, [] for 1, or [0] for 0.
  Ḋ         Dequeue; remove the first (smallest) element.
   P        Take the product.
            This yields the largest proper divisor if n > 1, 1 if n < 2.
    ạ       Yield the abs. value of the difference of the divisor (or 1) and n.
     µ      Convert the chain to the left into a link.
      ÐĿ    Repeatedly execute the link until the results are no longer unique.
            Collect all intermediate results in a list.
            For each starting value of n, the last results are 2 -> 1 -> 0 (-> 1).
        i2  Compute the 1-based index of 2.
|improve this answer|||||

Retina, 12

  • 14 bytes saved thanks to @MartinBüttner

This assumes input given in unary and output given in decimal. If this is not acceptable then we can do this for 6 bytes more:

Retina, 18

  • 8 bytes saved thanks to @MartinBüttner

Try it online - 1st line added to run all testcases in one go.

Sadly this uses unary for the calculations, so input of 2016155 is not practical.

  • The first stage (2 lines) simply converts the decimal input to unary as a string of 1s
  • The second stage (1 line) calculates the largest factor of n using regex matching groups and lookbehinds to and effectively subtracts it from n. This regex will match as many times as is necessary to reduce the number as far as possible. The number of regex matches will be the number of steps, and is output by this stage.
|improve this answer|||||

Pyth - 15 14 13 bytes

Special casing 1 is really killing me.


Try it online here.

tl                One minus the length of
 .u               Cumulative fixed point operator implicitly on input
  -N              N -
   /N             N /
    h             Smallest prime factor
     +PN2         Prime factorization of lambda var, with two added to work with 1
|improve this answer|||||
  • 1
    \$\begingroup\$ One thing I always forget.... brute force is often the golfiest approach \$\endgroup\$ – Leaky Nun May 9 '16 at 13:34
  • \$\begingroup\$ What do you mean with special casing 1? \$\endgroup\$ – Adnan May 9 '16 at 13:40
  • 1
    \$\begingroup\$ @Adnan the prime factorization of 1 is [], which causes an error when I take the first element. I have to special case it to make it return 1 again so the .u fixed-point ends. I found a better way than .x try-except which is what saved me those 2 bytes. \$\endgroup\$ – Maltysen May 9 '16 at 13:41
  • \$\begingroup\$ It only needs to accept numbers >= 2 (>1). \$\endgroup\$ – Solomon Ucko May 9 '16 at 22:49
  • \$\begingroup\$ @SolomonUcko you're misunderstanding, the .u fixed-point will eventually reach 1 for all input, at which point it will have to be special cased. \$\endgroup\$ – Maltysen May 9 '16 at 22:53

JavaScript (ES6), *44 38

Edit 6 bytes saved thanks @l4m2

(* 4 striked is still 4)

Recursive function


Less golfed

f=(n, d=n-1)=>{
  if (n>1)
    if(n % d != 0)
      return f(n, d-1) // same number, try a smaller divisor
      return f(n-d)+1  // reduce number, increment step, repeat
    return 0




[5,30,31,32,100,200].forEach(x=>console.log(x+' -> '+f(x)))
<pre id=O></pre>

|improve this answer|||||
  • \$\begingroup\$ Nice, but I think you should spend the two bytes needed to make f(1) == 0. \$\endgroup\$ – Neil May 11 '16 at 11:39
  • \$\begingroup\$ @Neil thinking again: no. "Let n be a natural number ≥ 2 ..." \$\endgroup\$ – edc65 May 11 '16 at 14:18
  • \$\begingroup\$ I need new glasses. \$\endgroup\$ – Neil May 12 '16 at 13:44
  • \$\begingroup\$ Why not f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0? \$\endgroup\$ – l4m2 Apr 13 '18 at 3:50
  • \$\begingroup\$ @l4m2 right, why not? Thanks \$\endgroup\$ – edc65 Apr 13 '18 at 14:55

Mathematica, 36 bytes


An unnamed function takes the same bytes:


This is a very straightforward implementation of the definition as a recursive function.

|improve this answer|||||

Octave, 59 58 55 bytes

function r=f(x)r=0;while(x-=x/factor(x)(1));r++;end;end

Updated thanks to Stewie Griffin, saving 1 byte

Further update, saving three more bytes by using result of factorization in while-check.

Sample runs:

octave:41> f(5)
ans =  3
octave:42> f(30)
ans =  6
octave:43> f(31)
ans =  7
octave:44> f(32)
ans =  5
octave:45> f(100)
ans =  8
octave:46> f(200)
ans =  9
|improve this answer|||||
  • \$\begingroup\$ is the last end necessary in octave ? \$\endgroup\$ – Abr001am May 9 '16 at 20:36
  • \$\begingroup\$ It is. I noticed it was not in matlab from your answers, but Octave expects it (as I learned from trying yours in Octave). \$\endgroup\$ – dcsohl May 9 '16 at 20:43

Haskell, 59 bytes

f 1=0;f n=1+(f$n-(last$filter(\x->n`mod`x==0)[1..n`div`2]))


Prelude> f 30
Prelude> 6

It may be a little inefficient for big numbers because of generating the list.

|improve this answer|||||
  • 1
    \$\begingroup\$ List comprehension and <1 instead of ==0 saves a few bytes: f 1=0;f n=1+f(n-last[a|a<-[1..ndiv2],mod n a<1]) \$\endgroup\$ – Angs Apr 13 '18 at 15:25

Julia, 56 50 45 39 bytes


This is a recursive function that accepts an integer and returns an integer.


function f(n)
    if n < 2
        # No decrementing necessary
        return 0
        # As Dennis showed in his Jelly answer, we don't need to
        # divide by the smallest prime factor; any prime factor
        # will do. Since `factor` returns a `Dict` which isn't
        # sorted, `first` doesn't always get the smallest, and
        # that's okay.
        return f(n - n ÷ first(factor(n))[1]) + 1

Try it online! (includes all test cases)

Saved 6 bytes thanks to Martin Büttner and 11 thanks to Dennis!

|improve this answer|||||

PowerShell v2+, 81 bytes


Brutest of brute force.

Takes input $a, enters a for loop until $a is less than or equal to 1. Each loop we go through another for loop that counts down from $a until we find a divisor (!($a%$i). At worst, we'll find $i=1 as a divisor. When we do, increment our counter $j, subtract our divisor $a-=$i and set $i=0 to break out of the inner loop. Eventually, we'll reach a condition where the outer loop is false (i.e., $a has reached 1), so output $j and exit.

Caution: This will take a long time on larger numbers, especially primes. Input of 100,000,000 takes ~35 seconds on my Core i5 laptop. Edit -- just tested with [int]::MaxValue (2^32-1), and it took ~27 minutes. Not too bad, I suppose.

|improve this answer|||||

Matlab, 58 bytes

function p=l(a),p=0;if(a-1),p=1+l(a-a/min(factor(a)));end
|improve this answer|||||

Japt, 12 bytes (non-competing)

@!(UµUk Å×}a

Test it online! Non-competing because it uses a bunch of features that were added way after the challenge was posted.

How it works

@   !(Uµ Uk Å  ×   }a
XYZ{!(U-=Uk s1 r*1 }a
                       // Implicit: U = input integer
XYZ{               }a  // Return the smallest non-negative integer X which returns
                       // a truthy value when run through this function:
         Uk            //   Take the prime factorization of U.
            s1         //   Slice off the first item.
                       //   Now we have all but the smallest prime factor of U.
               r*1     //   Reduce the result by multiplication, starting at 1.
                       //   This takes the product of the array, which is the
                       //   largest divisor of U.
      U-=              //   Subtract the result from U.
    !(                 //   Return !U (which is basically U == 0).
                       //   Since we started at 0, U == 1 after 1 less iteration than
                       //   the desired result. U == 0 works because the smallest
                       //   divisor of 1 is 1, so the next term after 1 is 0.
                       // Implicit: output result of last expression

This technique was inspired by the 05AB1E answer. A previous version used ²¤ (push a 2, slice off the first two items) in place of Å because it's one byte shorter than s1  (note trailing space); I only realized after the fact that because this appends a 2 to the end of the array and slices from the beginning, it in fact fails on any odd composite number, though it works on all given test cases.

|improve this answer|||||

Python 3, 75, 70, 67 bytes.

g=lambda x,y=0:y*(x<2)or[g(x-z,y+1)for z in range(1,x)if x%z<1][-1]

This is a pretty straight forward recursive solution. It takes a VERY long time for the high number test cases.

|improve this answer|||||

><>, 32 bytes


Expects the input number, n, on the stack.

This program builds the complete sequence on the stack. As the only number that can lead to 1 is 2, building the sequence stops when 2 is reached. This also causes the size of the stack to equal the number of steps, rather than the number of steps +1.

|improve this answer|||||

Ruby, 43 bytes


Find the smallest number i such that x divides x-i and recurse until we reach 1.

|improve this answer|||||

Haskell, 67 bytes

Here's the code:

a&b|b<2=0|a==b=1+2&(b-1)|mod b a<1=1+2&(b-div b a)|1<2=(a+1)&b

And here's one reason why Haskell is awesome:

f = (2&)

(-->) :: Eq a => a -> a -> Bool
(-->) = (==)

h=[f(5)        --> 3
  ,f(30)       --> 6
  ,f(31)       --> 7
  ,f(32)       --> 5
  ,f(100)      --> 8
  ,f(200)      --> 9
  ,f(2016^155) --> 2015

Yes, in Haskell you can define --> to be equivalent to ==.

|improve this answer|||||

Matlab, 107 bytes

  • Non-competing, this is not the iterative translation of my last submission, just another direct algerbraic method, it sums up all binary-logs of all prime factors, kinda ambiguous to illustrate.
  • I will golf this more when i have time.
|improve this answer|||||

MATL, 17 16 bytes


Try it Online


        % Implicitly grab input
`       % Do while loop
    ttt % Make three copies of top stack element
    Yf  % Compute all prime factors
    l)  % Grab the smallest one
    /   % Divide by this to get the biggest divisor
    -   % Subtract the biggest divisor
    t   % Duplicate the result
    q   % Subtract one (causes loop to terminate when the value is 1). This
        % is functionally equivalent to doing 1> (since the input will always be positive) 
        % with fewer bytes
]       % End do...while loop
v       % Vertically concatenate stack contents (consumes entire stack)
n       % Determine length of the result
q       % Subtract 1 from the length
        % Implicitly display result
|improve this answer|||||

C99, 62 61 bytes

1 byte golfed off by @Alchymist.


Call as f(x,&y), where x is the input and y is the output.

|improve this answer|||||
  • \$\begingroup\$ If you test a%--b then you can avoid the b-- at the end. A whole one byte saving. \$\endgroup\$ – Alchymist May 11 '16 at 15:06

Julia, 39 36 bytes


Try it online!

|improve this answer|||||

Clojure, 116 104 bytes

(fn[n](loop[m n t 1](let[s(- m(last(filter #(=(rem m %)0)(range 1 m))))](if(< s 2)t(recur s (inc t))))))

-12 bytes by filtering a range to find multiples, then using last one to get the greatest one

Naïve solution that basically just solves the problem as it's described by the OP. Unfortunately, finding the greatest divisor alone takes up like half the bytes used. At least I should have lots of room to golf from here.

Pregolfed and test:

(defn great-divider [n]
  ; Filter a range to find multiples, then take the last one to get the largest
     (filter #(= (rem n %) 0)
             (range 1 n))))

(defn sub-great-divide [n]
  (loop [m n
         step 1]
    (let [g-d (great-divider m) ; Find greatest divisor of m
          diff (- m g-d)] ; Find the difference
      (println m " is " g-d " --> " m " - " g-d " = " diff)
      (if (< diff 2)
        (recur diff (inc step))))))

(sub-great-divide 30)

30  is  15  -->  30  -  15  =  15
15  is  5  -->  15  -  5  =  10
10  is  5  -->  10  -  5  =  5
5  is  1  -->  5  -  1  =  4
4  is  2  -->  4  -  2  =  2
2  is  1  -->  2  -  1  =  1
|improve this answer|||||
  • 1
    \$\begingroup\$ @insertusernamehere No, unfortunately, because those are all valid identifiers. I've removed all the possible whitespace. If I want to golf it further, I'll need to rework the algorithm. \$\endgroup\$ – Carcigenicate Jan 18 '17 at 17:38

Perl 6, 35 bytes

{+({$_ -first $_%%*,[R,] ^$_}...1)}

Try it online!

How it works

{                                 }   # A bare block lambda.
                    [R,] ^$_          # Construct range from arg minus 1, down to 0.
        first $_%%*,                  # Get first element that is a divisor of the arg.
    $_ -                              # Subtract it from the arg.
   {                        }...1     # Do this iteratively, until 1 is reached.
 +(                              )    # Return the number of values generated this way.
|improve this answer|||||

Pyth, 17 16 bytes


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

Original 17 bytes:


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

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

|improve this answer|||||
  • \$\begingroup\$ 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. \$\endgroup\$ – Maltysen May 9 '16 at 13:46

Pyke, 11 bytes (noncompeting)


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
    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
    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!

|improve this answer|||||

JavaScript (ES6), 70 54 bytes


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

|improve this answer|||||

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



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


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 / $_;
        $n -= $d;
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
|improve this answer|||||

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.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.