50
\$\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\$
  • \$\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

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\$
  • \$\begingroup\$ You don't need the parenthesis around n-> \$\endgroup\$ – FlipTack Jan 18 '17 at 18:54
1
\$\begingroup\$

Stax, 9 7 bytes

Åiw^Å♫┌

Run and debug it

These two operations are identical.

  1. Take the biggest divisor of n – which is different from n itself – and subtract it from n.
  2. Let d be the smallest prime divisor of n. Calculate n * (d - 1) / d.

I like #2 better, so let's count how many times we can do that one instead. So at each step, we decrement the smallest prime factor. Let's work an example starting with 30.

Step    n   Factors             Operation
0       30  [2, 3, 5]           Replace 2 with 1
1       15  [1, 3, 5] = [3, 5]  Replace 3 with 2
2       10  [2, 5]              Replace 2 with 1
3       5   [1, 5] = [5]        Replace 5 with 4
4       4   [4] = [2, 2]        Replace 2 with 1
5       2   [1, 2] = [2]        Replace 2 with 1
6       1   [1] = []            End of the line

From the example we can see a recursive definition for steps(x) that solves the problem. Presented here in python-ish pseudo-code.

def steps(n):
    pf = primeFactors(n)
    return sum(steps(d - 1) for d in pf) + 1

The stax program, unpacked into ascii looks like this.

Z       push a zero under the input
|fF     for each prime factor of the input, run the rest of the program
  v     decrement the prime factor
  G     run the *whole* program from the beginning
  +^    add to the running total, then increment

Run this one

\$\endgroup\$
  • \$\begingroup\$ Looks like we have a new winner. A short question: Is there a meta agreement that characters count as bytes on Stax? I would say these are 7 characters and 13 bytes. \$\endgroup\$ – insertusernamehere Aug 17 '18 at 17:17
  • \$\begingroup\$ You can read about the character encoding stax uses here. If you doubt the byte count, you can download the program using the down arrow button, and count the bytes yourself. It will show you that the program is 7 bytes. To verify, you can re-upload the program and run it to verify the behavior is the same. \$\endgroup\$ – recursive Aug 17 '18 at 19:19
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\$

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.