Operational countdown

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.

• Can we return/print all the steps instead of counting them? – Adám Dec 3 '20 at 21:30
• Can our solutions work "in theory" but fail due to floating point issues? – caird coinheringaahing Dec 3 '20 at 21:31
• @cairdcoinheringaahing, that's our general consensus, isn't it? – Shaggy Dec 3 '20 at 22:58
• 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 – caird coinheringaahing Dec 3 '20 at 23:04
• 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 – AZTECCO Dec 4 '20 at 0:51

R, 7774 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).

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

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

• Made a couple of somewhat suspect incremental golfs to arrive at this for 16 bytes. – Unrelated String Dec 3 '20 at 23:32
• @UnrelatedString Oh, those are nice! I always forget Ḋ and forks, so not so suspect for me. :-) Thank you! – xash Dec 3 '20 at 23:42
• 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! – Unrelated String Dec 3 '20 at 23:48

APL (Dyalog Extended), 4036 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\}$$

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

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


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!

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

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!

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  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. 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  Charcoal, 34 31 bytes ⊞υＮＷ⌊υ⊞υ⌊Φι№⟦ＸκＬι×κＬι⁺κＬι⟧ιＩ⊖Ｌυ  Try it online! Link is to verbose version of code. Explanation: ⊞υＮ  Input n and push it to the predefined empty list. Ｗ⌊υ  Repeat until the list contains zero. ⊞υ⌊Φι№⟦ＸκＬι×κＬι⁺κＬι⟧ι  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. Ｉ⊖Ｌυ  Output the final number of iterations, which is one less than the length of the list. 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! 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

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

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!

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