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

In https://socratic.org/s/aJdvbsx7 I derive a method for finding square roots by use of a recursively defined sequence.

Note that the recursively defined tribonacci sequence has the property that the ratio between consecutive terms tends to the tribonacci constant, which is the real zero of #x^3-x^2-x-1#, namely #1/3 (1 + root(3)(19 - 3 sqrt(33)) + root(3)(19 + 3 sqrt(33)))#.

Can we find a method to allow the calculation of the cube root of any positive integer using a recursively defined sequence?

2 Answers
George C.
Oct 27, 2017

Yes, but it's not particularly efficient.

Explanation:

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.

George C.
Dec 17, 2017

Much more efficient method using two sequences...

Explanation:

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.

Related questions
Impact of this question
1718 views around the world
You can reuse this answer
Creative Commons License