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
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.

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.