Can you find the cube root of a positive integer using a recursively defined sequence?

Suppose you are given a positive integer #n# whose cube is irrational, but close to an even integer #2k#.

Consider the cubic polynomial with zeros:

#k+root(3)(n)#, #" "k+omega root(3)(n)" "# and #" "k+omega^2 root(3)(n)#

where #omega = -1/2+sqrt(3)/2i# is the primitive complex cube root of #1#.

#(x-k-root(3)(n))(x-k-omega root(3)(n))(x-k-omega^2 root(3)(n))#

#= (x-k)^3-n#

#= x^3-3kx^2+3k^2x-(k^3+n)#

So the zeros satisfy:

#x^3 = 3kx^2-3k^2x+(k^3+n)#

Define a sequence of integers recursively by:

#{ (a_0 = 0), (a_1 = 1), (a_2 = 3k), (a_(n+3) = 3ka_(n+2)-3k^2a_(n+1)+(k^3+n)a_n) :}#

Then the ratio between successive pairs of terms will tend to #k+root(3)(n)#.

Example

Note that #4^3 = 64#. So let's try #n=67# and #k=2# to find approximations to #root(3)(67)# ...

Our sequence definition becomes:

#{ (a_0 = 0), (a_1 = 1), (a_2 = 6), (a_(n+3) = 6a_(n+2)-12a_(n+1)+75a_n) :}#

The first few terms of the sequence are:

#0, 1, 6, 24, 147, 1044, 6300, 36297, 220482, 1359828, 8235459#

We find:

#8235459/1359828 ~~ 6.06#

So:

#root(3)(67) ~~ 6.06-2 = 4.06#

Notes

There is a problem with this method that makes it much less efficient than the corresponding method for square roots: Though the roots #k + omega root(3)(n)# and #k + omega^2 root(3)(n)# are somewhat smaller than the one we want #k + root(3)(n)# they are still relatively large. In the case of the similar method for square roots, #a-sqrt(n)# is much smaller than #a+sqrt(n)#, so the convergence is much faster.

Much more efficient than a single sequence method is a two sequence method using Newton's method.

Given a positive integer #n# whose cube root we want to find, let:

#f(x) = x^3-n#

Then;

#f'(x) = 3x^2#

Given any approximation #a_i# to #root(3)(n)#, a better approximation is:

#a_(i+1) = a_i - (f(a_i))/(f'(a_i))#

Given that we want to use integer sequences, consider #a_i = p_i/q_i# and find:

#p_(i+1)/q_(i+1) = p_i/q_i - (f(p_i/q_i))/(f'(p_i/q_i))#

#color(white)(p_(i+1)/q_(i+1)) = p_i/q_i - ((p_i/q_i)^3-n)/(3(p_i/q_i)^2)#

#color(white)(p_(i+1)/q_(i+1)) = p_i/q_i - (p_i^3-nq_i^3)/(3p_i^2q_i)#

#color(white)(p_(i+1)/q_(i+1)) = (3p_i^3)/(3p_i^2q_i) - (p_i^3-nq_i^3)/(3p_i^2q_i)#

#color(white)(p_(i+1)/q_(i+1)) = (2p_i^3+nq_i^3)/(3p_i^2q_i)#

So define:

#{ (p_(i+1) = 2p_i^3+nq_i^3), (q_(i+1) = 3p_i^2q_i) :}#

For example, to find #root(3)(2)#, let #p_0 = q_0 = 1# and find:

#{ (p_1 = 2p_0^3+nq_0^3 = 2(color(blue)(1))^3+color(blue)(2)(color(blue)(1))^3 = 2+2 = 4), (q_1 = 3p_0^2q_0 = 3(color(blue)(1))^2(color(blue)(1)) = 3) :}#

#{ (p_2 = 2p_1^3+nq_1^3 = 2(color(blue)(4))^3+color(blue)(2)(color(blue)(3))^3 = 128+54 = 182), (q_2 = 3p_1^2q_1 = 3(color(blue)(4))^2(color(blue)(3)) = 144) :}#

#{ (p_3 = 2p_2^3+nq_2^3 = 2(color(blue)(182))^3+color(blue)(2)(color(blue)(144))^3 = 12057136+5971968 = 18029104), (q_3 = 3p_2^2q_2 = 3(color(blue)(182))^2(color(blue)(144)) = 14309568) :}#

We find:

#root(3)(2) ~~ 18029104/14309568 ~~ 1.2599#

That does not seem very efficient. How about if we start with #p_0 = 5# and #q_0 = 4# - much closer to the real value.

Then:

#{ (p_1 = 2p_0^3+nq_0^3 = 2(color(blue)(5))^3+color(blue)(2)(color(blue)(4))^3 = 250+128 = 378), (q_1 = 3p_0^2q_0 = 3(color(blue)(5))^2(color(blue)(4)) = 300) :}#

#{ (p_2 = 2p_1^3+nq_1^3 = 2(color(blue)(378))^3+color(blue)(2)(color(blue)(300))^3 = 108020304+54000000 = 162020304), (q_2 = 3p_1^2q_1 = 3(color(blue)(378))^2(color(blue)(300)) = 128595600) :}#

So:

#root(3)(2) ~~ 162020304/128595600 ~~ 1.25992105#

That's much more efficient. So the accuracy of the first approximation is important.