Practical numbers: Difference between revisions

Undo revision 329071 by Hout (talk) Use of Haskell typing in Python - see talk page.
((No Paddy, you can't endlessly delete approaches which you wish to discourage. We are optimizing different things. Live and let live. Let others show their approach.))
(Undo revision 329071 by Hout (talk) Use of Haskell typing in Python - see talk page.)
Line 228:
 
===Composition of pure functions===
On Haskell vs Python typing see the discussion page.
====With type hints for the compiler====
On type comments for the human reader, vs type hints for the compiler, see the discussion page.
 
For the unvandalized version of this submission, with comments on the semantics of the types, see below.
<lang python>'''Practical numbers'''
 
Line 251 ⟶ 248:
))
 
# Note: Although mypy compliant, type Any below could be improved.
 
 
def sumOfAnySubset(xs: List[int]) -> Callable[[Any], Any]:
Line 417 ⟶ 414:
 
666 is practical :: True</pre>
 
====With type comments for the human reader====
 
Restoring the original, (and, at critical points more informative) '''comments''' on type semantics which have been gratuitously deleted, without consultation, in the name of "discouraging" variant approaches,
 
and in particular showing that the central '''sumOfAnySubset''' function returns a boolean value, and takes an integer value as its second argument:
 
<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>77 OEIS A005153 numbers in [1..333]
 
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
156 160 162 168 176 180 192 196 198 200
204 208 210 216 220 224 228 234 240 252
256 260 264 270 272 276 280 288 294 300
304 306 308 312 320 324 330
 
 
666 is practical :: True
</pre>
 
=={{header|Raku}}==
Anonymous user