0
\$\begingroup\$

One day, when I was bored in maths class, I learned of a neat trick for solving the real cube root of a number!

Let's use the number \$79,507\$ as an example.

First, take digit in the one's place and compare it to this table:

\begin{array} {|r|r|} \hline \text{Extracted Digit} &\text{Resulting Digit} \\ \hline \text{1} &\text{1} \\ \text{2} &\text{8} \\ \text{3} &\text{7} \\ \text{4} &\text{4} \\ \text{5} &\text{5} \\ \text{6} &\text{6} \\ \text{7} &\text{3} \\ \text{8} &\text{2} \\ \text{9} &\text{9} \\ \text{0} &\text{0} \\ \hline \end{array}

In this example, the Resulting Digit will be \$3\$ since the extracted digit is \$7\$.

Next, remove all digits that are less than \$10^3\$:

$$ 79507 → 79 $$

Then, find the largest perfect cube that does not exceed the input:

$$ 64 < 79 $$

\$64=4^3\$, thus the next digit needed is \$4\$.

Finally, multiply the digit found in the previous step by \$10\$ and add the Resulting Digit found in the first step:

$$ 10*4+3=43 $$

Thus, the cube root of \$79,507\$ equals \$43\$.

However, there a neat quirk about this trick: it doesn't apply to only cubed numbers. In fact, it works with all \$n>1\$ where \$n\bmod2\ne0\$.

The steps mentioned above can be summed up in this generalization for an \$n\$ power:

  • Step 1) Take the digit in the one's place in the input. Compare it to the one's place digit of the \$n\$th powers of \$1\$ to \$10\$, then use the corresponding digit.

  • Step 2) Remove all digits of the input less than \$10^n\$. Compare the resulting number to the perfect powers definied in Step 1. Use the \$n\$th root of the largest perfect power less than said number. (Largest perfect power can exceed \$10^n\$)

  • Step 3) Multiply the number from Step 2 by 10 then add the number from Step 1. This will be the final result.

Task

Given two positive integers \$n\$ and \$m\$, return the \$n\$th root of \$m\$.

Input:

  • Two positive integers \$n\$ and \$m\$.

  • \$m\$ is guaranteed to be a perfect \$n\$th power of an integer.

  • \$n\$ is guaranteed to be odd and greater than \$2\$. (This method doesn't work if \$n\$ is even.)

Output:

  • The values calculated in steps 1 and 2.

  • The \$n\$th root of \$m\$.

  • Output can be on multiples lines or a list, whichever is more convenient.

Rules:

  • This is , so the fewer bytes, the better!

  • Standard I/O rules apply.

  • The output must be calculated using the aforementioned method.

  • No builtins allowed that already calculate this. A prime example being TI-BASIC's x√ command.

Examples:

Input      | Output
-------------------
3, 79507   | 3
           | 4
           | 43
3, 79507   | [3, 4, 43]
5, 4084101 | 1
           | 2
           | 21
5, 4084101 | [1, 2, 21]
\$\endgroup\$

closed as unclear what you're asking by xnor, Luis Mendo, Luis felipe De jesus Munoz, J42161217, Stephen May 7 at 15:19

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ Are we allowed to use a built-in root command for step 2? Or are we only allowed to compute numbers to the \$n\$th power and compare? \$\endgroup\$ – Robin Ryder May 7 at 14:03
  • 11
    \$\begingroup\$ Do x using y challenges are frowned upon usually as per meta consensus (as it is often difficult to enforce that they've gotten to x using y only). \$\endgroup\$ – Magic Octopus Urn May 7 at 14:07
  • 4
    \$\begingroup\$ Well... One could now compute \$x=m^{1/n}\$ with a built-in and output \$[floor(x/10),x\bmod 10]\$... \$\endgroup\$ – Arnauld May 7 at 14:42
  • 4
    \$\begingroup\$ My point is that using the required algorithm is still non-observable. \$\endgroup\$ – Arnauld May 7 at 14:46
  • 2
    \$\begingroup\$ And the sandbox didn't catch the issues...what else is new??? \$\endgroup\$ – Redwolf Programs May 7 at 15:55
3
\$\begingroup\$

05AB1E, 18 bytes

Saved 1 byte thanks to Kevin Cruijssen

mθ=²¹°÷Dݹm@O<=ìï=

Try it online!

\$\endgroup\$
  • \$\begingroup\$ As per general consensus, the challenge has been edited to require the printing of intermediate steps. \$\endgroup\$ – Tau May 7 at 14:37
  • \$\begingroup\$ ‹_ can be @ to save a byte. \$\endgroup\$ – Kevin Cruijssen May 7 at 14:37
  • \$\begingroup\$ @KevinCruijssen: What! I am 100% certain that didn't work when I tried it before :( \$\endgroup\$ – Emigna May 7 at 14:39
  • \$\begingroup\$ @Tau: Now prints intermediate results. \$\endgroup\$ – Emigna May 7 at 14:40
  • \$\begingroup\$ Not really in spec with the challenge, but just putting it out there: 9 bytes: zmò¤,D¨,, or zmòШsθr» \$\endgroup\$ – Kevin Cruijssen May 7 at 14:52
2
\$\begingroup\$

JavaScript (ES7),  58  56 bytes

Saved 11 many bytes thanks to @Emigna

Takes input as (m)(n). Returns the 2 intermediate values and the final result as an array.

m=>g=(n,k)=>k**n>m/10**n?[u=m**n%10,--k,k*10+u]:g(n,-~k)

Try it online!


JavaScript (Node.js), 62 bytes

This version uses BigInts as I/O to support larger inputs.

m=>g=(n,k=0n)=>k**n>m/10n**n?[u=m**n%10n,--k,k*10n+u]:g(n,++k)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ As per general consensus, the challenge has been edited to require the printing of intermediate steps. \$\endgroup\$ – Tau May 7 at 14:37
  • \$\begingroup\$ This fails when the final digit is a 0. For example f(1000,3) returns 0 instead of 10. \$\endgroup\$ – Robin Ryder May 7 at 15:03
  • \$\begingroup\$ @RobinRyder Should be fixed now. (However, the 58-byte version only support very small inputs.) \$\endgroup\$ – Arnauld May 7 at 15:08
1
\$\begingroup\$

R, 74 bytes

function(m,n)c(a<-match(m%%10,(1:9)^n%%10,0),b<-(m/10^n)^(1/n)%/%1,a+10*b)

Try it online!

match(m%%10,(1:9)^n%%10,0) compares the last digit of m to the reference table (and outputs 0 if no match is found), thus performing step 1.

(m/10^n)^(1/n)%/%1 gives the output of step 2.

\$\endgroup\$
  • \$\begingroup\$ clever use of nomatch, although of course match(...,(0:9)^n%%10)-1 would be just as golfy \$\endgroup\$ – Giuseppe May 7 at 15:52
  • \$\begingroup\$ @Giuseppe Yes, I had that version initially as well, but decided I liked the version with nomatch better. :-) \$\endgroup\$ – Robin Ryder May 7 at 16:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.