21
\$\begingroup\$

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
\$\endgroup\$
  • 5
    \$\begingroup\$ Obligatory OEIS link: A155043 \$\endgroup\$ – Sp3000 May 23 '16 at 9:48
  • \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender May 23 '16 at 17:24

23 Answers 23

1
\$\begingroup\$

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.
\$\endgroup\$
6
\$\begingroup\$

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!

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

C, 52 bytes

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

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.
\$\endgroup\$
3
\$\begingroup\$

Julia, 31 bytes

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

Straightforward recursive implementation.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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;}
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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... \$\endgroup\$ – Adnan May 23 '16 at 11:01
  • \$\begingroup\$ @LuisMendo Yeah, it's because the D0Q# part is after the increment of the counter. The [Ð>#Ñg-¼]¾ code should work for 0 though :). \$\endgroup\$ – Adnan May 23 '16 at 11:42
  • \$\begingroup\$ @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. \$\endgroup\$ – Emigna May 23 '16 at 12:55
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Mathcad, [tbd] bytes

enter image description here


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

\$\endgroup\$
1
\$\begingroup\$

MATL, 13 bytes

tX`t:\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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Haskell, 43 40 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!

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

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.

\$\endgroup\$
1
\$\begingroup\$

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)))))))
\$\endgroup\$
  • \$\begingroup\$ Hello, and welcome to PPCG! Great post! Can you explain your solution please? (P.S. I love Lisp!) \$\endgroup\$ – NoOneIsHere May 24 '16 at 15:36
  • \$\begingroup\$ @NoOneIsHere Edited in \$\endgroup\$ – kronicmage May 24 '16 at 21:25
0
\$\begingroup\$

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

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

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

\$\endgroup\$
0
\$\begingroup\$

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}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

C#, 63 bytes

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

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)
\$\endgroup\$

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.