As a predicate function, we have,

```
>>> def is_perfect(x):
from math import sqrt as root
return not root(x) % 1
>>> is_perfect(4)
True
>>> is_perfect(9)
True
>>> is_perfect(25)
True
>>> is_perfect(36)
True
>>> is_perfect(32)
False
>>>
```

As a predicate function, we have,

```
>>> def is_perfect(x):
from math import sqrt as root
return not root(x) % 1
>>> is_perfect(4)
True
>>> is_perfect(9)
True
>>> is_perfect(25)
True
>>> is_perfect(36)
True
>>> is_perfect(32)
False
>>>
```

3 Likes

The logical progression now will be to verify a perfect cube.

```
>>> 343 ** (1/3)
6.999999999999999
>>>
```

How do we get around the floating point error, here?

Yes, we can fudge it, allowing for 10 ** -14 precision, but the logic would be more overhead. Even using logarithms will mean dealing with floats.

So what if we were to use a different approach and see how many prime numbers will divide in to `x`

?

```
>>> p = [2, 3, 5, 7, 11, 13 ,17, 19]
>>> n = 343
>>> f = [q for q in [r for r in p if not n % r]]
>>> f
[7]
>>>
```

`f`

above is the list of prime factors of `343`

.

Since there is only one factor, then 343 must not be achievable by any multiplication not using `7`

. To verify it is a cube, we cube it and see if it gives us back our `n`

.

```
>>> if f[0] ** 3 == n:
print ("{} is a perfect cube".format(n))
343 is a perfect cube
>>>
```

Something for down the road, but I just had to throw in this bit of fun.

And, yes, I do realize we’re not done here. Not by a long shot.

Did a little digging and found this site…

http://burningmath.blogspot.com/2013/09/how-to-know-or-check-if-number-is.html

```
>>> n = 216
>>> f = [q for q in [r for r in p if not n % r]]
>>> f
[2, 3]
>>>
```

Oops; there are two factors, not one. Not to worry. `2 * 3`

is `6`

```
>>> from functools import reduce
>>> if reduce(lambda a, b: a * b, f) ** 3 == n:
print ("{} is a perfect cube".format(n))
216 is a perfect cube
>>>
```

```
>>> n = 85 ** 3
>>> f = [q for q in [r for r in p if not n % r]]
>>> if reduce(lambda a, b: a * b, f) ** 3 == n:
print ("{} is a perfect cube".format(n))
614125 is a perfect cube
>>>
```

It follows the effectiveness of this method is limited by the size of our prime list. We cannot verify cubes of much larger than 42 with the primes under 100. Depending upon how large the number is, we may need to memoize all the primes needed as potential factors. That will of course add to the time and space complexity by some exponential factor.

```
>>> def is_perfect_cube(n):
from functools import reduce
p = [
2,3,5,7,
11,13,17,19,
23,29,
31,37,
41,43,47,
51,53,57,59,
61,67,
71,73,79,
83,
91,93,97
]
f = [q for q in [r for r in p if not n % r]]
return reduce(lambda a, b: a * b, f) ** 3 == n
>>> is_perfect_cube(52 ** 3)
False
>>> is_perfect_cube(42 ** 3)
True
>>>
```

3 Likes

@appylpye, @patrickd314, any insights to offer here on how to extend the range of this function? Is there another approach or are we more or less saddled with this one? Is there a P generator that will give us a *next_prime*?

One also realizes that no break point has been figured into this code so that would be a major concern on large values.

Following is a try at the function:

```
def cube_root(n):
# estimate the cube root as an int
est = n // 2
prev_diff = max(n, 1)
while True:
# assign new_est the average of est and n / est
# new_est = (est + n / est) / 2
new_est = (est + n // (est * est)) // 2
# check how much the estimate has changed
curr_diff = abs(est - new_est)
# if the change has stopped decreasing, break and return the result
if curr_diff >= prev_diff:
break
# otherwise keep refinining the estimate
prev_diff = curr_diff
est = new_est
return new_est
def is_perfect_cube(n):
cr = cube_root(n)
cr_int = int(cr)
# range from under to over the cube
for i in (-1, 0, 1):
if (cr_int + i) ** 3 == n:
return True
return False
# test for a small number
n = 2
cube = n ** 3
print(cube_root(cube))
print(is_perfect_cube(cube - 1))
print(is_perfect_cube(cube))
print(is_perfect_cube(cube + 1))
# test for a large number
n = 700711099987765007
cube = n ** 3
print(cube_root(cube))
print(is_perfect_cube(cube - 1))
print(is_perfect_cube(cube))
print(is_perfect_cube(cube + 1))
```

Output:

```
2
False
True
False
700711099987765007
False
True
False
```

It seems to work.

*EDIT 1 (May 18, 2019):*

The above was designed to extend the range to large numbers. It is broken concerning checking `1`

for its status as a perfect cube.

… will fine tune it later today, unless someone else volunteers to do so first.

*EDIT 2 (May 18, 2019):*

Have fixed it; see new version.

3 Likes

Cubes are not squares, that’s for sure! (I have a wonderful proof for this statement, but it will not fit in this post.)

Thanks for the challenge, and the introduction to the **reduce()** function, which I’m still trying to wrap my brain around. I think that you are doing with it what I do in the function triplets(), below.

The flow is:

check if digital root is 0, 1, 8 or 9 (per your citation, above.)

if so, generate a dictionary of its prime factors,`{prime_factor : num_occurrences}`

check if each and every prime factor occurs a number of times that is divisible by 3

… if not, reject

… if so, return the product of each prime_factor**(num_of_occurrences // 3)

Here goes:

```
def prime_factors(n):
"""
return a dictionary of prime factors of n
"""
factor_dict = {}
div = 2
# new_n = n
while div**2 <= n:
while n % div == 0:
if not div in factor_dict:
factor_dict[div] = 0
factor_dict[div] += 1
n //= div
div += 1
if n > 1: # final factor checked is prime
factor_dict[n] = 1
return factor_dict
def triplets(factor_dict):
"""check if each and every prime factor in
factor_dict is present a number of times
evenly divisible by three. If so, return
the product of each factor raised to the power
of the (number of its occurrences // 3)
"""
for key in factor_dict:
if factor_dict[key] % 3:
return False
l = 1
for key in factor_dict:
num_key = factor_dict[key]//3
l *= (key**num_key)
return l
def digital_root(n):
""" return the digital root of n
"""
if 0 <= n < 10:
return n
return digital_root(n // 10 + n % 10)
def cube_rt(n):
""" Test if digital root of n is 0, 1, 8 or 9
If so send to triplets()
If not, return 'not a cube'
"""
if not digital_root(n) in [0, 1, 8, 9]:
return "{} is not a cube".format(n)
factor_dict = prime_factors(n)
p = triplets(factor_dict)
if not p:
return "{} is not a cube".format(n)
return "{} is a perfect cube, whose cube root is {}.".format(n,p)
#if __name__ == "__main__":
# import sys
# choice = "0"
# while not choice in "qnQN":
# num = input("Enter the number which you would like to test: ")
# if num.isdigit():
# num = int(num)
# print(cube_rt(num))
# choice = input("\nDo another? (y/n) ")
# sys.exit()
for n in [8000, 15625, 40323, 132651, 941192, 103823, 42875]:
print(cube_rt(n))
# Output:
8000 is a perfect cube, whose cube root is 20.
15625 is a perfect cube, whose cube root is 25.
40323 is not a cube
132651 is a perfect cube, whose cube root is 51.
941192 is a perfect cube, whose cube root is 98.
103823 is a perfect cube, whose cube root is 47.
42875 is a perfect cube, whose cube root is 35.
```

3 Likes

Excellent! Thanks for weighing in.

It’s akin to a Newtonian Approximation, of a sort. I do remember learning a similar technique about thirty years ago, but as it were, forgot it.

If you are willing to enter an upper bound, you can use the venerable Sieve of Eratosthenes. It does require instantiating a list of [True] * upper_bound.

```
def sieve_gen(n):
prime_lst = []
big_l = [True for num in range(n)] # Each number (index) becomes True
p, idx = 0, 0
new_prime = 2
while p < n:
for idx in range(new_prime, len(big_l)): # look for next True, begins at 2
if big_l[idx] == True:
new_prime = idx # ... which is the next prime
yield new_prime
stride = new_prime # ... and reset stride
break
for idx in range(new_prime, len(big_l), stride):
big_l[idx] = False # "mark" all multiples of most recent prime
p += 1
prime = sieve_gen(100)
for i in range(100):
try:
print(next(prime))
except StopIteration:
print("That's all, folks!")
break
```

I’ve seen something of this nature at one point in time. Hardly remember it, though. By triplets I take it you mean something like this…

```
(3 + 3 + 3) + (3 + 3 + 3) + (3 +3 + 3)
```

?

Interesting approach. Thanks for weighing in.

My approach was a kind of seat-of-the-pants experiment that partially proved out. Obviously there are limits. Glenn has addressed very large numbers. How does your approach work on those types of numbers?

But for the ubiquitous *unity* being a perfect square, cube, &c.

When we examine the time/space complexity, what would be the difference between the three approaches above?

My theory is that regardless how many factors we derive, their multiple will be `n`

. `reduce`

takes a callback function that applies the multiply operator on all terms in the list, similar to factorial, which reduces down to a single value.

Similarily, with `reduce`

we can apply other operators on a list to arrive at a sum, quotient, or other final value.

I meant that a factor occurs an *exact multiple of three times*:

For instance, `40500**3 = 66430125000000`

```
66430125000000 = 2^6 * 3^12 * 5^9
... so the "triplet" number for 2 is 2, for 3 is 4, and for 5 is 3
... and 2^2 * 3^4 * 5^3 = 40500
... which is the cube root of 66430125000000
```

If any prime factor occurs a number of times not divisible by three, the number is not a cube.

(Both this approach and the use of digital root were inspired by the reference you cited.)

My approach is pretty fast (no perceptible delay) up to the cube of a seven to eight digit number, then slows down quickly. `appylpye's`

shows no more than an eyeblink up to the cube of a *400 - 500 digit number* (and I think could be optimized to converge even faster), so nothing to be gained by actually measuring times. Mine, of course, requires the computation and retention of a dictionary of prime factors, but `appylpye's`

just uses a divide and conquer with no more than a few numbers in memory at any time: the clear winner.

(BTW, playing around with these functions, I noticed that your function (if I implemented it correctly, which I may not have done) gives incorrect results for certain inputs, the lowest of which were the cubes of 4, 8, and 9.)

2 Likes

Following is a corrected version; The fix is to begin with an estimated cube root of `1`

:

```
def cube_root(n):
# estimate the cube root of n as an int
# est = n // 2 # failed when n == 1; revised as below
est = 1
prev_diff = max(n, 1)
while True:
# assign new_est the average of est and n // (est * est)
new_est = (est + n // (est * est)) // 2
# check how much the estimate has changed
curr_diff = abs(est - new_est)
# if the change has stopped decreasing, break and return the result
if curr_diff >= prev_diff:
break
# otherwise keep refinining the estimate
prev_diff = curr_diff
est = new_est
return new_est
def is_perfect_cube(n):
cr = cube_root(n)
cr_int = int(cr)
for i in (0, 1):
if (cr_int + i) ** 3 == n:
return True
return False
# test for some small numbers
for n in range(11):
print(n, is_perfect_cube(n))
# test for some large numbers
large_number = 700711099987765007
gigantic_perfect_cube = large_number ** 3
for n in range(gigantic_perfect_cube - 2, gigantic_perfect_cube + 3):
print(n, is_perfect_cube(n))
```

Output:

```
0 True
1 True
2 False
3 False
4 False
5 False
6 False
7 False
8 True
9 False
10 False
344046379234296109086163514834657351029597422926455341 False
344046379234296109086163514834657351029597422926455342 False
344046379234296109086163514834657351029597422926455343 True
344046379234296109086163514834657351029597422926455344 False
344046379234296109086163514834657351029597422926455345 False
```

2 Likes

On that we must concur. Nothing less than exceptional, as expected.

Hopefully learners who read this thread will see that some solutions work some of the time, but not always; some solutions work all the time but get more complex as they go; and some solutions work all the time and do not get more complex as they go. The optimal solution isn’t always the simplest to comprehend.

2 Likes

The following consolidates it into a single function. The code at the end tests the function for several million numbers, therefore it takes a while to complete execution. The testing is based on the notion that failure is most likely to constitute either false negatives for numbers that are actually perfect cubes or false positives for numbers that are either one below or one above a perfect cube.

```
def is_perfect_cube(n):
# estimate the cube root of n as an int
est_cr = n // 2 + 1
prev_diff = max(n, 1)
while True:
# assign new_est_cr the average of est_cr and n // est_cr ** 2
new_est_cr = (est_cr + n // est_cr ** 2) // 2
# check how much the estimate has changed
curr_diff = abs(est_cr - new_est_cr)
# if the change has stopped decreasing, break
if curr_diff >= prev_diff:
break
# otherwise keep refining the estimate
prev_diff = curr_diff
est_cr = new_est_cr
if new_est_cr ** 3 == n:
# n is a perfect cube
return True
# n is not a perfect cube
return False
### testing
import random
print("begin testing")
failed = False
# test for numbers 0 to 1000000
cubes = [n ** 3 for n in range(101)]
for n in range(1000001):
if is_perfect_cube(n):
if n not in cubes:
print("false positive: {:d}".format(n))
failed = True
else:
if n in cubes:
print("false negative: {:d}".format(n))
failed = True
# test for some large numbers
for i in range(1000000):
n = random.randint(1000000, 10000000)
n_cubed = n ** 3
if not is_perfect_cube(n_cubed):
print("false negative: {:d}".format(n_cubed))
failed = True
if is_perfect_cube(n_cubed - 1):
print("false positive: {:d}".format(n_cubed))
failed = True
if is_perfect_cube(n_cubed + 1):
print("false positive: {:d}".format(n_cubed))
failed = True
print("end testing")
if failed:
print("failed")
else:
print("passed")
```

Output:

```
begin testing
end testing
passed
```

2 Likes

Which page, tbh I have not read. I saw the words *prime factors* and copied the URL and went headlong into my own idea. Now that you have demonstrated two approaches I will definitely go back and read the page.

About puts a bow on it, methinks. Bookmarked, for sure.

2 Likes