# Divisor reduction

A divisor of a number n is any number that evenly divides n, including 1 and n itself. The number of divisors d(n) is how many divisors a number has. Here's d(n) for the first couple n:

n    divisors    d(n)
1    1           1
2    1, 2        2
3    1, 3        2
4    1, 2, 4     3
5    1, 5        2
6    1, 2, 3, 6  4


We can repeatedly subtract the number of divisors from a number. For example:

16                  = 16
16 - d(16) = 16 - 5 = 11
11 - d(11) = 11 - 2 = 9
9 - d( 9) =  9 - 3 = 6
6 - d( 6) =  6 - 4 = 2
2 - d( 2) =  2 - 2 = 0


In this case it took 5 steps to get to 0.

Write a program or function that given a nonnegative number n returns the number of steps it takes to reduce it to 0 by repeated subtraction of the number of divisors.

Examples:

0, 0
1, 1
6, 2
16, 5
100, 19
100000, 7534

• Obligatory OEIS link: A155043 – Sp3000 May 23 '16 at 9:48
• Related. – Martin Ender May 23 '16 at 17:24

# Jelly, 10 9 bytes

1 byte thanks to Dennis ♦.

Port of my answer in Pyth.

ÆDLạµÐĿL’


Try it online!

Test suite.

## Explanation

_ÆDLÐĿL’
ÐĿ    Repeat the following until result no longer unique:
ÆD             Yield the array of the divisors
L            Yield the length of the array
_               Subtract that from the number
L   Number of iterations
’  Minus one.


# Python, 49 bytes

f=lambda n:n and-~f(sum(n%~x<0for x in range(n)))


orlp helped save a byte! And Sp3000 saved two more. Thanks!

• Should be able to shorten things by moving the -~ into n%-~k, and removing the lower bound of the range. – orlp May 23 '16 at 13:43

# C, 52 bytes

g,o;l(f){for(g=o=f;o;f%o--||--g);return f?1+l(g):0;}


# Pyth, 10 bytes

tl.ulf%NTS


Test suite.

## Explanation

tl.ulf%NTS
tl.ulf%NTSNQ  implicit variables at the end
Q  obtain the input number
.u      N   repeat the following until result no longer unique:
S        generate range from 1 to N
f            filter for:
%NT             T in that range, which N%T is truthy (not zero)
l             length of that list
that means, we found the number of "non-divisors" of N
tl            number of iterations, minus 1.


## Julia, 31 bytes

f(n)=n<1?0:f(sum(n%(1:n).>0))+1


Straightforward recursive implementation.

# MATL, 14 bytes

t~?x@q.]t:\zT


Try it online!

### Explanation

            T  % Infinite loop
t~?    ]       % Duplicate number. Is it non-zero?
x@q.        % If so: delete number, push iteration index minus 1, break loop
t:\    % Duplicate, range, modulo (remainder). Divisors give a 0 remainder
z   % Number of non-zero elements; that is, of non-divisors


## JavaScript (ES6), 64 51 bytes

f=n=>n&&[...Array(m=n)].map((_,i)=>m-=n%++i<1)|f(m)+1


Don't ask me why I was unnecessarily using tail recursion.

# Java, 147 93

a->{int k,i,n=new Integer(a),l=0;for(;n!=0;n-=k)for(l+=k=i=1;i<n;)if(n%i++==0)++k;return l;}

• Why n=new Integer(100000) instead of n=100000? – dorukayhan May 23 '16 at 22:10

## Hoon, 93 76 bytes

|=
r/@
?~
r
0
+($(r (sub r (lent (skim (gulf 1^r) |=(@ =(0 (mod r +<))))))))  Ungolfed: |= r/@ ?~ r 0 =+ (skim (gulf 1^r) |=(@ =(0 (mod r +<)))) +($(r (sub r (lent -))))


Returns a function that takes an atom, r. Create an intermediate value that contains all the devisors of r (Make list [1..n], keep only the elements where (mod r i) == 0). If r is zero return zero, else return the incremented value of recursing with r equal r-(length divisors).

The code as-is takes a stupid amount of time to evaluate for n=100.000, entirely because finding the devisors for big numbers makes a giant list and maps over it. Memoizing the divisors gets the correct output for n=10.000, but I didn't bother waiting around for 100.000

## 05AB1E, 12 10 bytes

Code:

[Ð>#Ñg-¼]¾


Explanation:

[           # start infinite loop
Ð          # triplicate current number
>#        # increase by 1 and break if true
Ñg      # get number of divisors
-     # subtract number of divisors from number
¼    # increase counter
]   # end loop
¾  # print counter


Try it online

Edit: 2 bytes saved and a bug with input 0 fixed thanks to @Adnan

• Very nice! I tried to golf it a bit, and got it down to 10 bytes: [Ð>#Ñg-¼]¾. There has to be a way to get it shorter though... – Adnan May 23 '16 at 11:01
• @LuisMendo Yeah, it's because the D0Q# part is after the increment of the counter. The [Ð>#Ñg-¼]¾ code should work for 0 though :). – Adnan May 23 '16 at 11:42
• @Adnan: I tried a version based on generating all counts upto n and going from index to value at index and counting up, but didn't manage to get it shorter that way. – Emigna May 23 '16 at 12:55

## R, 50 bytes

Pretty simple implementation. Try it online

z=scan();i=0;while(z>0){z=z-sum(z%%1:z<1);i=i+1};i


# Mathcad, [tbd] bytes Mathcad byte equivalence scheme is yet to be determined. Using a rough keystroke equivalence, the program uses about 39 "bytes". Note that the while and for programming operators only take one keyboard operation each to input (ctl-] and ctl-shft-#, respectively) - indeed, they can only be entered this way from the keyboard.

What you see is exactly what gets put down on a Mathcad worksheet. Mathcad evaluates the equations/programs and puts the output on the same sheet (eg, after the '=' evaluation operator or on the plot).

# MATL, 13 bytes

tXt:\ztt]Nq&


Try it online

Explanation:

t               % Duplicate input
X      ]      % while loop, consumes 1 input
t:\z         % calculates n-d(n), by counting number non-divisors
tt       % dupe twice, for while loop condition, next iteration and to keep in stack
Nq&   % get stack size, decrement, display that value


## Mathematica, 35 bytes

If[#<1,0,#0[#-0~DivisorSigma~#]+1]&


Making use of good old DivisorSigma. @MartinBüttner notes the following alternatives:

If[#<1,0,#0[#-DivisorSum[#,1&]]+1]&
f@0=0;f@n_:=f[n-DivisorSum[n,1&]]+1


## Haskell, 4340 39 bytes

g 0=0;g n=1+g(sum$min 1.mod n<$>[1..n])


Simple recursive approach. Usage example: g 16 -> 5.

Edit: @Lynn saved 3 4 bytes. Thanks!

• How about g(sum$signum.mod n<$>[1..n])? – Lynn May 23 '16 at 21:43
• Oh, and min 1 is actually one byte shorter than signum, even – Lynn May 24 '16 at 10:51

## PowerShell v2+, 74 67 bytes

param($n)for($o=0;$n-gt0){$a=0;1..$n|%{$a+=!($n%$_)};$n-=$a;$o++}$o


Seems pretty lengthy in comparison to some of the other answers...

Takes input $n, enters a for loop with the condition that $n is greater than 0. Each loop iteration we set helper $a, then loop through every number from 1 up to $n. Each inner loop we check against every number to see if it's a divisor, and if so we increment our helper $a (using Boolean negation and implicit cast-to-int). Then, we subtract how many divisors we've found $n-=$a and increment our counter $o++. Finally, we output $o. Takes a long time to execute, since it's a significant for-loop construct. For example, running n = 10,000 on my machine (1yr old Core i5) takes almost 3 minutes. # Racket - 126 bytes Down to 98 bytes 91 bytes An extremely naive solution - could probably be cut down a lot with a decent algorithm and some lisp tricks that I don't know (define(g x[c 0][d 0][i 2])(cond[(= x 0)c][(= i x)(g d(+ 1 c))][(=(modulo x i)0)(g x c d(+ 1 i))][else(g x c(+ 1 d)(+ 1 i))]))  Edit: explanation by request. As I said, this is an extremely naive recursive solution and can be much much shorter. (define (g x [c 0] [d 0] [i 2]) ;g is the name of the function - arguments are x (input), c (counter for steps), d (non-divisor counter), i (iterator) (cond [(= x 0) c] ;once x gets to 0 c is outputted [(= i x) (g d (+ 1 c))] ;if iterator reaches x then we recurse with d as input and add 1 to c [(= (modulo x i) 0) (g x c d (+ 1 i))] ;checks if iterator is non divisor, then adds it to d and increments iterator [else(g x c (+ 1 d) (+ 1 i))])) ;otherwise just increments iterator  Edit 2: 98 byte version with a less dumb algorithm (still pretty dumb though and can be shorter) (define(g x)(if(< x 1)0(+ 1(g(length(filter(λ(y)(>(modulo x y)0))(cdr(build-list x values))))))))  Explanation: (define (g x) ;function name g, input x (if (< x 1) 0 ;returns 0 if x < 1 (base case) (+ 1 ;simple recursion - adds 1 to output for each time we're looping (g (length ;the input we're passing is the length of... (filter (λ (y) (> (modulo x y) 0)) ;the list where all numbers which are 0 modulo x are 0 are filtered out from... (cdr (build-list x values)))))))) ;the list of all integers up to x, not including 0  Edit 3: Saved 7 bytes by replacing (cdr(build-list x values)) with (build-list x add1) (define(g x)(if(< x 1)0(+ 1(g(length(filter(λ(y)(>(modulo x y)0))(build-list x add1)))))))  • Hello, and welcome to PPCG! Great post! Can you explain your solution please? (P.S. I love Lisp!) – NoOneIsHere May 24 '16 at 15:36 • @NoOneIsHere Edited in – kronicmage May 24 '16 at 21:25 # ><>, 52+2 = 54 bytes The input number needs to be present on the stack at program start, so there's +2 bytes for the -v flag. Try it online! :0)?v~ln;>~$-]
03[}\::
@@:$< v?=0:-1}+{~$?@@01%@:


4 annoying bytes wasted on alignment issues. Bah.

This one works by building the sequence from n to 0 on the stack. Once 0 has been reached, pop it and ouput the length of the remaining stack.

By the way , it runs in O(n^2) time, so I wouldn't try n = 100000...

• -v is one byte, not two. – NoOneIsHere May 24 '16 at 22:33

## ><>, 36 + 3 = 39 bytes

:?v~ln; >~&
:}\0&
+&>1-:?!^:{:}$%0)&  The implementation's relatively straightforward, with each iteration being sum(n%k>0 for k in range(1,n-1)). +3 bytes for the -v flag, per meta. Try it online! # Ruby, 42 bytes f=->n{n<1?0:1+f[n-(1..n).count{|i|n%i<1}]}  There's a stack overflow error on the largest test case 100000, so here's an iterative version within 49 bytes. Takes a while, though, considering the O(N^2) complexity. ->n{c=0;c+=1 while 0<n-=(1..n).count{|i|n%i<1};c}  # Perl 5, 40 bytes sub f{@_?(1,f((1)x grep@_%$_,1..@_)):()}


Input and output are as lists of the requisite number of copies of 1.

# C#, 63 bytes

int F(int n)=>n<1?0:F(Enumerable.Range(1,n).Count(i=>n%i>0))+1;


## Actually, 17 bytes

";╗R╜%░l;"£╬klD


Try it online! (note: last test case times out on TIO)

Explanation:

";╗R╜%░l;"£╬klD
"          "£╬     while top of stack is truthy, call the function:
;╗                  push a copy of n to reg0
R                 range(1,n+1) ([1,n])
  ░l             push the number of values where the following is truthy:
╜%                  k mod n
(this computes the number of non-divisors of n)
;            make a copy
klD  push entire stack as list, count number of items, subtract 1
(the result is the number of times the function was called)


# Husk, 9 bytes

←LU¡Ṡ-oLḊ


Try it online!

# Japt, 8 bytes

©ÒßU-â l


Try it

Or 9 bytes without recursion:

©@µâ l}f1


Try it