Humble numbers: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: Added a first sketch in Haskell) |
(→{{header|Python}}: Added a first sketch in Python.) |
||
| Line 1,735: | Line 1,735: | ||
152,515 humble numbers have 42 digits (23.9s, total:1,703,635) |
152,515 humble numbers have 42 digits (23.9s, total:1,703,635) |
||
</pre> |
</pre> |
||
=={{header|Python}}== |
|||
<lang python>'''Humble numbers''' |
|||
from itertools import count, groupby, islice |
|||
from functools import reduce |
|||
from math import floor, sqrt |
|||
# humbles :: () -> [Int] |
|||
def humbles(): |
|||
'''A non-finite stream of Humble numbers. |
|||
OEIS A002473 |
|||
''' |
|||
def isHumble(x): |
|||
return all(8 > x for x in primeFactors(x)) |
|||
return filter(isHumble, count(1)) |
|||
# TEST ---------------------------------------------------- |
|||
# main :: IO () |
|||
def main(): |
|||
'''First 50, and counts with N digits''' |
|||
print('First 50 Humble numbers:\n') |
|||
for row in chunksOf(10)( |
|||
take(50)(humbles()) |
|||
): |
|||
print(' '.join(map( |
|||
lambda x: str(x).rjust(3), |
|||
row |
|||
))) |
|||
print('\nCounts of Humble numbers with n digits:\n') |
|||
for tpl in take(5)( |
|||
(k, len(list(g))) for k, g in |
|||
groupby(map(compose(len, str), humbles())) |
|||
): |
|||
print(tpl) |
|||
# 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. |
|||
''' |
|||
return lambda xs: reduce( |
|||
lambda a, i: a + [xs[i:n + i]], |
|||
range(0, len(xs), n), [] |
|||
) if 0 < n else [] |
|||
# compose :: ((a -> a), ...) -> (a -> a) |
|||
def compose(*fs): |
|||
'''Composition, from right to left, |
|||
of a series of functions. |
|||
''' |
|||
return lambda x: reduce( |
|||
lambda a, f: f(a), |
|||
fs[::-1], x |
|||
) |
|||
# 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) |
|||
# take :: Int -> [a] -> [a] |
|||
# take :: Int -> String -> String |
|||
def take(n): |
|||
'''The prefix of xs of length n, |
|||
or xs itself if n > length xs. |
|||
''' |
|||
return lambda xs: list(islice(xs, n)) |
|||
# 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, x): |
|||
v = x |
|||
while not p(v): |
|||
v = f(v) |
|||
return v |
|||
return lambda f: lambda x: go(f, x) |
|||
# MAIN --- |
|||
if __name__ == '__main__': |
|||
main()</lang> |
|||
{{Out}} |
|||
<pre>First 50 Humble numbers: |
|||
1 2 3 4 5 6 7 8 9 10 |
|||
12 14 15 16 18 20 21 24 25 27 |
|||
28 30 32 35 36 40 42 45 48 49 |
|||
50 54 56 60 63 64 70 72 75 80 |
|||
81 84 90 96 98 100 105 108 112 120 |
|||
Counts of Humble numbers with n digits: |
|||
(1, 9) |
|||
(2, 36) |
|||
(3, 95) |
|||
(4, 197) |
|||
(5, 356)</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||