title: How to find integer nth roots?
body: <p>I want to find the greatest integer less than or equal to the kth root of n. I tried</p>
  <pre><code>int(n**(1/k))
  </code></pre>
  <p>But for n=125, k=3 this gives the wrong answer! I happen to know that 5 cubed is 125.</p>
  <pre><code>&gt;&gt;&gt; int(125**(1/3))
  4
  </code></pre>
  <p>What's a better algorithm?</p>
  <p>Background: In 2011, this slip-up cost me beating Google Code Jam problem <a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000432f3b/0000000000432b31" rel="nofollow noreferrer"><em>Expensive Dinner</em></a>.</p>