Segue on a perfect topic

#1

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
Plz help in this code
#2

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
#3

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

#4

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
#5

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
#6

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.

#7

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
#8

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.

#9

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
#10

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
#11

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
#12

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
#13

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