There Is No Spoon There Is No Spoon - 5 days ago 5
Python Question

Determining Practical Numbers

So I am given a fraction and must determine if the denominator is a practical number. Description of a practical number: What is a practical number?
I already have a function that returns all the factors of the number:


def factorFinder(x):
#Pre: Valid Integer for students
#Post: Returns list of factors for that number
#Takes the number of students as argument and returns all factors for that number
lst = []
for i in range(1, x+1):
if x % i == 0:
lst.append(i)
return(lst)



and a function that given a list of factors as arguments returns a list of sums of all its sublists:


import itertools
def sumsOfSublists(lst):
# Pre: a non-empty list
# Post: returns a list of sums of all possible list sublists of length >= 2
# given a list, returns a sorted list containing sums of
# all combinations of sublists of length 2..list_length
sumList = []
for i in range(2, len(lst)+1):
zlist = list(itertools.combinations(lst,i))
for el in zlist:
sumList.append(sum(el))
return sorted(sumList)


I don't know how to go about testing if the number is practical or not. I don't really understand the concept of a "practical number" even after reading about it on multiple websites. So I guess really, this is more of a math question if anything.

Answer

I reformulate your wiki-article and hope that it is helpful to you - because as AChampion has said - you have already done all the heavy lifting ;)

n is is a practical number if:

  • let l = [1, 2, ... n-1] // all number smaller than n
  • let divs = [i for i in range(1,n) if n%i==0] // all divisors of n (I associate a factor is prime cause of the term factorization of a number, so probably you should change factor to divisor in your question)
  • Now you have to write all numbers of l as sum of numbers from divs, where you can use all numbers of divs one or zero times

for example n = 12 is a practical number because:

  • l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
  • divs = [1, 2, 3, 4, 6]
  • l[0] = divs[0], l[1] = divs[1], ... , l[10] = divs[0]+divs[3]+divs[4]=1+4+6=11 // l[1] = divs[0]+divs[0] is not allowed because you may use each number of divs only once

In opposite n = 3 is not a practical number because:

  • l = [1, 2]
  • divs = [1]
  • l[0] = divs[0], l[1] = mööööp

Here is also a straightforward implementation of my explanation (but you can also keep the nice work you have already done!):

from itertools import combinations

def isPracticalNumber(n):
    l = [i for i in range(1, n)]
    divs = [i for i in range(1, n) if n % i == 0]
    possibleSums = set()
    for i in range(1, len(divs)+1):
        combinationsOfLengthI = combinations(divs, i)
        for combi in combinationsOfLengthI:
            possibleSums.add(sum(combi))

    return all([i in possibleSums for i in l])

if __name__ == '__main__':
    print(isPracticalNumber(12)) # True
    print(isPracticalNumber(3)) # False

    practicalNumbers = [1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72, 78, 80, 84, 88, 90, 96, 100, 104, 108, 112, 120, 126, 128, 132, 140, 144, 150]
    calculatedPracticalNumbers = [i for i in range(1, 151) if isPracticalNumber(i)]
    print(len(calculatedPracticalNumbers) == len(practicalNumbers) and all([i in practicalNumbers for i in calculatedPracticalNumbers]))
Comments