Practical numbers: Difference between revisions

====Original version – with language-independent (MH) comments on type semantics====

A variant of this code with '''actual Python type hints for the compiler''', in lieu of the language-independent Hindley-Milner type comments for the reader shown here has been helpfully added below, by another user, for comparison.

For example, where an MK type comment (for the central function below) reads:

<code># sumOfAnySubset :: [Int] -> Int -> Bool</code>

the additional variant, show below the original code here gives an actual Python type hint:

<code>def sumOfAnySubset(xs: List[int]) -> Callable[[int], bool]:</code>

The affordances of these two approaches differ – one aims for clarity for the human reader,

the other for formal type-checking by the Python compiler.

(Nothing, of course, excludes the option of using both)

<lang Python>'''Practical numbers'''

from itertools import accumulate, chain, groupby, product

from math import floor, sqrt

from operator import mul

from functools import reduce

# isPractical :: Int -> Bool

def isPractical(n):

'''True if n is a Practical number

(a member of OEIS A005153)

'''

ds = properDivisors(n)

return all(map(

sumOfAnySubset(ds),

range(1, n)

))

# sumOfAnySubset :: [Int] -> Int -> Bool

def sumOfAnySubset(xs):

'''True if any subset of xs sums to n.

'''

def go(n):

if n in xs:

return True

else:

total = sum(xs)

if n == total:

return True

elif n < total:

h, *t = reversed(xs)

d = n - h

return d in t or (

d > 0 and sumOfAnySubset(t)(d)

) or sumOfAnySubset(t)(n)

else:

return False

return go

# ------------------------- TEST -------------------------

# main :: IO ()

def main():

'''Practical numbers in the range [1..333],

and the OEIS A005153 membership of 666.

'''

xs = [x for x in range(1, 334) if isPractical(x)]

print(

f'{len(xs)} OEIS A005153 numbers in [1..333]\n\n' + (

spacedTable(

chunksOf(10)([

str(x) for x in xs

])

)

)

)

print("\n")

for n in [666]:

print(

f'{n} is practical :: {isPractical(n)}'

)

# ----------------------- GENERIC ------------------------

# chunksOf :: Int -> [a] -> [[a]]

def chunksOf(n):

'''A series of lists of length n, subdividing the

contents of xs. Where the length of xs is not evenly

divible, the final list will be shorter than n.

'''

def go(xs):

return [

xs[i:n + i] for i in range(0, len(xs), n)

] if 0 < n else None

return go

# primeFactors :: Int -> [Int]

def primeFactors(n):

'''A list of the prime factors of n.

'''

def f(qr):

r = qr[1]

return step(r), 1 + r

def step(x):

return 1 + (x << 2) - ((x >> 1) << 1)

def go(x):

root = floor(sqrt(x))

def p(qr):

q = qr[0]

return root < q or 0 == (x % q)

q = until(p)(f)(

(2 if 0 == x % 2 else 3, 1)

)[0]

return [x] if q > root else [q] + go(x // q)

return go(n)

# properDivisors :: Int -> [Int]

def properDivisors(n):

'''The ordered divisors of n, excluding n itself.

'''

def go(a, x):

return [a * b for a, b in product(

a,

accumulate(chain([1], x), mul)

)]

return sorted(

reduce(go, [

list(g) for _, g in groupby(primeFactors(n))

], [1])

)[:-1] if 1 < n else []

# listTranspose :: [[a]] -> [[a]]

def listTranspose(xss):

'''Transposed matrix'''

def go(xss):

if xss:

h, *t = xss

return (

[[h[0]] + [xs[0] for xs in t if xs]] + (

go([h[1:]] + [xs[1:] for xs in t])

)

) if h and isinstance(h, list) else go(t)

else:

return []

return go(xss)

# until :: (a -> Bool) -> (a -> a) -> a -> a

def until(p):

'''The result of repeatedly applying f until p holds.

The initial seed value is x.

'''

def go(f):

def g(x):

v = x

while not p(v):

v = f(v)

return v

return g

return go

# ---------------------- FORMATTING ----------------------

# spacedTable :: [[String]] -> String

def spacedTable(rows):

'''Tabulation with right-aligned cells'''

columnWidths = [

len(str(row[-1])) for row in listTranspose(rows)

]

def aligned(s, w):

return s.rjust(w, ' ')

return '\n'.join(

' '.join(

map(aligned, row, columnWidths)

) for row in rows

)

# MAIN ---

if __name__ == '__main__':

main()</lang>

{{Out}}

<pre></pre>

====Variant with actual Python type hints====