20
\$\begingroup\$

Given a non negative integer number \$n\$ output how many steps to reach zero using radicals, divisions or subtractions.

The algorithm

  • Get digits count ( \$d\$ ) of \$n\$.

  • Try the following operations in order:
    $$\sqrt[d]{n}$$ $$n/d$$ $$n-d$$

  • Take the first integer result not equal to \$n\$. Floating point errors must be avoided !

  • Repeat the process with the value obtained until you reach 0.

Example

1500 -> 8

1500 -> 4 digits , ( / ) => 375 // step 1
375 -> 3 digits , ( / ) => 125 // step 2
125 -> 3 digits , ( √ ) => 5 // step 3
5 -> 1 digits , ( - ) => 4 // step 4
4 -> 1 digits , ( - ) => 3 // step 5
3 -> 1 digits , ( - ) => 2 // step 6
2 -> 1 digits , ( - ) => 1 // step 7
1 -> 1 digits , ( - ) => 0 // step 8

Input: a non negative integer number. You don't have to handle inputs not supported by your language (obviously, abusing this is a standard loophole)

Output: the number of steps to reach 0

Test cases

n -> steps

0 -> 0
1 -> 1
2 -> 2
4 -> 4
10 -> 6
12 -> 7
16 -> 5
64 -> 9
100 -> 19
128 -> 7
1000 -> 70
1296 -> 7
1500 -> 8
5184 -> 8
10000 -> 133
21550 -> 1000
26720 -> 100
1018080 -> 16
387420489 -> 10

Rules

  • Input/output can be given by any convenient method.
  • You can print it to STDOUT, return it as a function result or error message/s.
  • Either a full program or a function are acceptable.
  • Standard loopholes are forbidden.
  • Answers must not fail due to floating point errors.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

Sandbox: https://codegolf.meta.stackexchange.com/a/20518/84844

\$\endgroup\$
  • \$\begingroup\$ Can we return/print all the steps instead of counting them? \$\endgroup\$ – Adám Dec 3 '20 at 21:30
  • 9
    \$\begingroup\$ Can our solutions work "in theory" but fail due to floating point issues? \$\endgroup\$ – caird coinheringaahing Dec 3 '20 at 21:31
  • \$\begingroup\$ @cairdcoinheringaahing, that's our general consensus, isn't it? \$\endgroup\$ – Shaggy Dec 3 '20 at 22:58
  • 1
    \$\begingroup\$ Checking meta, it appears we don't actually have a consensus whether floating point issues can be ignored or not @Shaggy. The closest I can find is this which states (about answers failing for \$\log_10(1000) = 3\$): "it's just a useful edge-case that happens to show that many existing answers were never truly valid". So I guess the closest thing we have to a consensus is that answers must be correct, even in the case of floating points \$\endgroup\$ – caird coinheringaahing Dec 3 '20 at 23:04
  • \$\begingroup\$ Sorry for the delay, I don't know what to say.. I don't like that.. It's a countdown and it has finite states, plus the main part of the challenge is about "is integer or not?" . I prefer to have answers that works de-facto and not theoretically. But if so many people want to allow that floating point issues to be valid it may be fine.. I'm so uncertain though \$\endgroup\$ – AZTECCO Dec 4 '20 at 0:51

13 Answers 13

7
\$\begingroup\$

R, 77 74 73 bytes

-3 bytes thanks to Giuseppe and -1 byte thanks to MarcMush.

f=function(n,d=nchar(n),k=1:n)`if`(d<2,n,1+f(match(n,c(k^d,k*d,k+d))%%n))

Try it online!

Recursive function; avoids floating point issues. The vector k contains all integers from 1 to n. Concatenate k^d, k*d and k+d (yielding a vector of length 3n) and find the position p of the first occurrence of n. Then \$f(n)=1+f(p \mod n)\$. The recursion is initialized by noting that \$f(n)=n\$ for all 1-digit integers (hence the conditioning on d<2).

Works for all the test cases (although 21550 could require you to increase the stack limit on some machines).

\$\endgroup\$
  • 3
    \$\begingroup\$ Very nice trick to avoid the floating-point problems \$\endgroup\$ – Dominic van Essen Dec 3 '20 at 23:16
  • 2
    \$\begingroup\$ 74 bytes -- shorter than the floating point approach! \$\endgroup\$ – Giuseppe Dec 3 '20 at 23:50
  • \$\begingroup\$ @Giuseppe Very smart, thanks! \$\endgroup\$ – Robin Ryder Dec 4 '20 at 8:00
  • 3
    \$\begingroup\$ you can check d<2 instead of n<10 for -1 byte \$\endgroup\$ – MarcMush Dec 4 '20 at 13:46
  • \$\begingroup\$ @MarcMush Well spotted, thanks! \$\endgroup\$ – Robin Ryder Dec 4 '20 at 14:05
6
\$\begingroup\$

Brachylog, 19 16 bytes

-3 thanks to @Unrelated String

Ḋ|⟨ℕ{√₎|/|-}l⟩↰<

Try it online!

A recursive function. If n ≥ 10, the three operations are tried. For n < 10 we need n steps to 0. With this we don't have to check that step(n) ≠ n, as it only occurs when there is one digit.

Ḋ|⟨ℕ{√₎|/|-}l⟩↰<
Ḋ                if n is in 0…9, return n
 |               otherwise
  ⟨f    h   g⟩   [f(n), g(n)] h
   ℕ        l    [n, digits] and n is a natural number
    {√₎|/|-}     try (root, divide, subtract) one after the other
                 (results that are not natural numbers will
                  get filtered in the next step with ℕ)
              ↰  recurse
               < get a number that is strictly larger, thus +1
\$\endgroup\$
  • 1
    \$\begingroup\$ Made a couple of somewhat suspect incremental golfs to arrive at this for 16 bytes. \$\endgroup\$ – Unrelated String Dec 3 '20 at 23:32
  • 1
    \$\begingroup\$ @UnrelatedString Oh, those are nice! I always forget and forks, so not so suspect for me. :-) Thank you! \$\endgroup\$ – xash Dec 3 '20 at 23:42
  • 1
    \$\begingroup\$ The suspect part is more "moving the into the fork" (which works fine because also constrains it to be an integer) and "pretending that < means 'increment'" (which works fine because there's no further logic after it). You're welcome! \$\endgroup\$ – Unrelated String Dec 3 '20 at 23:48
5
\$\begingroup\$

APL (Dyalog Extended), 40 36 32 bytes (SBCS)

-6 thanks to ovs.

Anonymous tacit prefix function. Requires zero-based indexing (⎕IO←0).

0∘{×⍵:(1+⍺)∇⊃⍵(…⍤⊣∩√⍨,÷,-)≢⍕⍵⋄⍺}

Try it online!

0∘{} "dfn" bound with 0 as left argument (, initial step count ― right argument, \$n\$ is ):

×⍵: if \$n>0\$ (lit. "if \$\text{sgn}(n)\$")

⍕⍵ stringify \$n\$

 tally the number of characters (digits)

⍵() apply the following tacit function to that, with \$n\$ as left argument:

  √⍨\$\root d\of n\$

  , followed by

  ÷\$\frac nd\$

  , followed by

  -\$n-d\$

   intersection of that and

⍳⍤⊣\$\{1,2,3,…,n-1\}\$

 the first element

()∇ recurse on that, with the following as new left argument:

  1+⍺ one plus the current step count


If d←≢⍕⍵ we have the expression ⍵(⍳⍤⊣∩√⍨,÷,-)d which could be written in traditional mathematical notation as:

$$\{1,2,3,…,n-1\}∩\Big\{\root d\of n,\frac nd,n-d\Big\}≡\Big\{\root d\of n,\frac nd,n-d\Big\}\setminus\{n\}$$

\$\endgroup\$
  • \$\begingroup\$ I think 1+⌊10⍟⍵ can be replaced with ⍴⍕⍵ for -4 bytes. \$\endgroup\$ – ovs Dec 3 '20 at 21:54
  • \$\begingroup\$ @ovs Nice. Thanks \$\endgroup\$ – Adám Dec 3 '20 at 21:55
  • \$\begingroup\$ 34 bytes with ⎕IO←0 by intersecting the three results with \$\{0, 1, \cdots, n-1\}\$. \$\endgroup\$ – ovs Dec 4 '20 at 15:33
4
\$\begingroup\$

JavaScript (ES7),  73  68 bytes

f=n=>(d=(n+'').length)<2?n:1+f((k=n**(1/d)+.5|0)**d-n?n%d?n-d:n/d:k)

Try it online!

Or 60 bytes if floating point errors are acceptable.

Commented

f = n =>                 // f is a recursive function taking the input n
  (d = (n + '').length)  // d is the number of digits in n
  < 2 ?                  //   if there's only one digit:
    n                    //     stop the recursion and return n
                         //     (because only n - 1 is valid at this point)
  :                      //   else:
    1 +                  //     increment the final result
    f(                   //     and do a recursive call:
      (                  //
        k = n ** (1 / d) //       define k as the d-th root of n
        + .5 | 0         //       rounded to the closest integer
      )                  //       
      ** d - n ?         //       if k ** d is not equal to n:
        n % d ?          //         if d is not a divisor of n:
          n - d          //           use n - d
        :                //         else:
          n / d          //           use n / d
      :                  //       else:
        k                //         use k
    )                    //     end of recursive call
\$\endgroup\$
4
\$\begingroup\$

Python 3.8, 112 \$\cdots\$ 97 96 bytes

Saved 7 a whopping 15 bytes thanks to Arnauld!!!
Saved a byte thanks to Danis!!!

f=lambda n:n and-~f([t:=round(n**(1/(d:=len(str(n))))),n//d,t,n-d][(t**d!=n)+2*(n%d>0)|3*(d<2)])

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 102 bytes \$\endgroup\$ – Arnauld Dec 4 '20 at 0:46
  • \$\begingroup\$ 97 bytes \$\endgroup\$ – Arnauld Dec 4 '20 at 1:05
  • \$\begingroup\$ @Arnauld That's amazing - thanks! :D \$\endgroup\$ – Noodle9 Dec 4 '20 at 1:17
  • \$\begingroup\$ you can remove +.5 and place int to write round, this will save 1 byte \$\endgroup\$ – a25bedc5-3d09-41b8-82fb-ea6c353d75ae Dec 4 '20 at 8:41
  • \$\begingroup\$ @Danis Nice one - thanks! :-) \$\endgroup\$ – Noodle9 Dec 4 '20 at 9:40
4
\$\begingroup\$

Julia 0.7, 68 62 bytes

inspired by Robin's answer in R

-6 bytes and more reasonable in terms of time and memory usage (can be computed on TIO)

f(n,d=ndigits(n))=n>0&&1+f(filter(r->n in(r+d,r*d,r^d),0:n)[])

Try it online!

Old answer, 68 bytes

port of Robin's answer in R

f(n,d=ndigits(n),R=1:n)=d<2?n:1+f(findlast(==(n),[R.+d;R*d;R.^d])%n)

curiously, TIO can't compute f(387420489) due to the 9GB array needed

Try it online!

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

Jelly, 19 bytes

*,×;+
ç€DL$œi⁸ḢµƬTL

Try it online!

How it works

*,×;+ - Helper link. Takes two integers k and d on the left and right
*     - k * d
  ×   - k × d
 ,    - [k * d, k × d]
    + - k + d
   ;  - [k * d, k × d, k + d]

ç€DL$œi⁸ḢµƬTL - Main link. Takes n on the left
         µ    - Group the previous links into a monad f(n):
    $         -   To n:
  D           -     Cast to digits
   L          -     Length
 €            -   Over each k = 1, 2, 3, ..., n:
ç             -     Call the helper link with k on the left and the digit length on the right
       ⁸      -   n
     œi Ḣ     -   Find the index of the first triple containing n
          Ƭ   - Until reaching a fixed point, repeatedly apply f(n)

                Both 1 and 0 are fixed points of f(n)
                As Ƭ returns [n, f(n), f(f(n)), ..., 1] for n > 0
                and [0] for n = 0, 1 being a fixed point offsets the 
                included n at the start. However, taking the length here
                would return 1 for n = 0 instead of 0

           T  - Find the indices of non-zero elements. As every element
                is non-zero unless n = 0, this yields [1, 2, ..., l]
                for n > 0 and [] for n = 0, where l is the output
            L - Length
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 134 bytes

.+
,$&,$&$*
+`,(.)*,(1*?)((?=\2+$)(?<=(?=(?<-1>(?=((1*)(?=\2\5+$)1)(\4*$))\6)+1$)\2).*|(?<-1>)(?<-1>\2)+|(?<-1>1)+)$(?(1)1)
1,$.2,$2
1

Try it online! Link includes faster test cases. Explanation:

.+
,$&,$&$*

Create a working area consisting of the result (initially 0), the input, and the input converted to unary.

+`

Repeat until the input has been reduced to zero ...

,(.)*,(1*?)(

count the number of digits d in the value n, and then find the smallest value that satisfies one of ...

(?=\2+$)(?<=(?=(?<-1>(?=((1*)(?=\2\5+$)1)(\4*$))\6)+1$)\2).*|

... its dth power is n, or ...

(?<-1>)(?<-1>\2)+|

... its product with d is n, or ...

(?<-1>1)+)

... its sum with d is n, and ...

$(?(1)1)

ensure that it was in fact d and not some smaller integer, and ...

1,$.2,$2

increment the output and replace n and its unary with the result.

1

Convert the output to decimal.

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

05AB1E, 39 bytes

[D0Q#DUgVXYzmXY/XY-).Δ©D2.òsòQ®XÊ&}ò¼}¾

Try it online!

Why can't you try it online? Because there's a bug with the TIO where raising numbers to floats which are actually whole numbers runs infinitely.

Explained

[D0Q#DUgVXYzmXY/XY-).Δ©D2.òsòQ®XÊ&}ò¼}¾
[                                           # Start an infinite loop with the input already on the stack.
 D0Q#                                       #   End the loop if the result from two lines above is 0
     DU                                     #   Store the top of the stack in variable X
       gV                                   #   And store its length in variable Y
         XYzm                               #   Push the Yth root of X
             XY/                            #   Push X / Y
                XY-                         #   Push X - Y
                   )                        #   And wrap that into a list
                    .Δ                      #   From that list, get the first item where:
                      ©D2.ò                 #       The item, when rounded to 2 decimal places
                           sòQ              #       Equals the item rounded to the nearest integer
                              ®XÊ&          #       And where it doesn't equal variable X
                                  }         #
                                   ò        #   Round that result to the nearest integer
                                    ¼}      #   Increment the counter variable, which keeps track of how many iterations we've gone through
                                      ¾     # Push the counter variable and implicitly print
                  
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 34 31 bytes

⊞υNW⌊υ⊞υ⌊Φι№⟦XκLι×κLι⁺κLι⟧ιI⊖Lυ

Try it online! Link is to verbose version of code. Explanation:

⊞υN

Input n and push it to the predefined empty list.

W⌊υ

Repeat until the list contains zero.

⊞υ⌊Φι№⟦XκLι×κLι⁺κLι⟧ι

For all integers less than n, take the dth power and the product and sum with d, and push the lowest integer where one of the results is n to the list.

I⊖Lυ

Output the final number of iterations, which is one less than the length of the list.

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

C (gcc) with -lm, 121 120 bytes

  • -1 thanks to ceilingcat

To get the number of digits, I used the floor of log10+1 of the value. Each iteration runs through the operations until the result is an integer that doesn't match the current value; when the result is 0 the number of steps is returned.

f(i,c,o,l){float a;for(c=0;i;i=a,c++)for(o=0,l=log10(i)+1,a=.1;fmod(a,1)||a==i;)a=o++?o>2?i-l:(i+0.)/l:pow(i,1./l);i=c;}

Try it online!

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

Stax, 47 bytes

ǃô▄↑"è≈■É↑├µxαêöV*┐┘ÆwaYM╙¿9⌠╛o-ºtΓ⌡╔ΔZj♦○Qæº`

Run and debug it

Accomodates for floating point innacuracies.

Explanation

, put input on main stack

{...w loop till falsy value

X store current interation in register X

c$% get number length

bbbb duplicate number 4 times

u#aa get floating point root

|N get integer root

-Au<{sd}{d}?~ if difference < 0.1, take the integer root otherwise float

/~ get n/d

-~ get n-d

Lr convert all those to array, reverse

{...}j find first value which satisfies:

cx=! not equal to current iteration

_c1u*@=* and not equal to its floor

ciYd save iteration index in Y

y^ output final index

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you add explanation please? \$\endgroup\$ – AZTECCO Dec 4 '20 at 16:12
  • 1
    \$\begingroup\$ @AZTECCO added in. \$\endgroup\$ – Razetime Dec 4 '20 at 17:47
1
\$\begingroup\$

Add++, 82 bytes

D,f,@,BDbLddARdV$€*$G$€+@G$€Ω^BcB]A€ΩedbLRz£*bUBZ@B]A$þ=bU
x:?
Wx,`x,$f>x,`y,+1
Oy

Try it online!

\$\endgroup\$
  • \$\begingroup\$ What O.o ? can you explain please? \$\endgroup\$ – AZTECCO Dec 5 '20 at 2:42

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.