Practical numbers: Difference between revisions
Content added Content deleted
(Removed Haskell typing and improved code with Python typing.) |
((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.)) |
||
Line 228: | Line 228: | ||
===Composition of pure functions=== |
===Composition of pure functions=== |
||
====With type hints for the compiler==== |
|||
On Haskell vs Python typing see the discussion page. |
|||
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''' |
<lang python>'''Practical numbers''' |
||
Line 248: | Line 251: | ||
)) |
)) |
||
# Note: Although mypy compliant, type Any below could be improved. |
|||
def sumOfAnySubset(xs: List[int]) -> Callable[[Any], Any]: |
def sumOfAnySubset(xs: List[int]) -> Callable[[Any], Any]: |
||
Line 414: | Line 417: | ||
666 is practical :: True</pre> |
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}}== |
=={{header|Raku}}== |