58
\$\begingroup\$

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

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

47 Answers 47

1
2
2
\$\begingroup\$

BQN, 24 bytes

{1:0;1+𝕊𝕩-⊢´↕⊸(⊣/˜0=|)𝕩}

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+𝕊𝕩-⊢´↕⊸(⊣/˜0=|)𝕩}
{                       }  Anonymous block function
 1:                        If the argument is 1:
   0                         Return 0
    ;                      Otherwise:
                       𝕩     Apply the following tacit function to the argument:
             ↕⊸(      )        Use range(argument) as the left arg to this binary function:
                     |         Mod (i.e. take 𝕩 mod each number in range(𝕩))
                   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
        𝕩-                  Subtract it from the argument
       𝕊                    Call this function on that value recursively
     1+                     Add 1 to the result
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ -5 by replacing return with an assignment \$\endgroup\$
    – att
    Jul 13 at 5:31
  • \$\begingroup\$ thanks @att, but I'd rather have it work on any C89 compiler \$\endgroup\$
    – c--
    Jul 18 at 3:30
1
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\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, 2016 at 13:46
1
\$\begingroup\$

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!

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

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.

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

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

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.

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

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!

\$\endgroup\$
1
  • \$\begingroup\$ You don't need the parenthesis around n-> \$\endgroup\$
    – FlipTack
    Jan 18, 2017 at 18:54
1
\$\begingroup\$

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

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

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

Husk, 9 bytes

LU¡Ṡ-ȯ→hḊ

Try it online!

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

Haskell, 42 bytes

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

Try it online!

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

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

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

Brachylog, 15 bytes

;.{fkt;?-ṅ}ⁱ⁾1∧

Try it online!

Explanation

;.{       }ⁱ⁾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
\$\endgroup\$
1
\$\begingroup\$

Excel VBA, 121 110 bytes

Sub a()
o=[A1]
For i=o-1To 1Step-1
If WorksheetFunction.Lcm(o,i)=o 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 WorksheetFunction.Lcm(o, i) = o 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

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

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

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

APL, 21 bytes

{1=⍵:0⋄1+∇⍵-⍵⌈.∨⍳⍵-1}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You have an extra space at the start of your code which can be removed \$\endgroup\$
    – pxeger
    Jul 12 at 13:12
1
2

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.