Practical numbers: Difference between revisions
Content added Content deleted
(New draft task with Python solution) |
m (→{{Header|Python}}: Typing ...) |
||
Line 44: | Line 44: | ||
# %% Powerset |
# %% Powerset |
||
def powerset(s: List[int]) -> List[Tuple[int]]: |
def powerset(s: List[int]) -> List[Tuple[int, ...]]: |
||
"""powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3) .""" |
"""powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3) .""" |
||
return list(chain.from_iterable(combinations(s, r) for r in range(len(s)+1))) |
return list(chain.from_iterable(combinations(s, r) for r in range(len(s)+1))) |
Revision as of 14:26, 30 March 2021
Practical numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
A Practical number P has some selection of its proper divisors, (other than itself), that can be selected to sum to every integer less than itself.
Compute all the proper divisors/factors of an input number X, then, using all selections from the factors compute all possible sums of factors and see if all numbers from 1 to X-1 can be created from it.
- Task
Write a function that given X returns a boolean value of whether X is a Practical number, (using the above method).
- Show how many Practical numbers there are in the range 1..333, inclusive.
- Show that the Practical numbers in the above range start and end in:
- 1, 2, 4, 6, 8, 12, 16, 18, 20, 24 ... 288, 294, 300, 304, 306, 308, 312, 320, 324, 330
- Stretch Goal
- Show if 666 is a Practical number
Python
<lang python>from itertools import chain, cycle, accumulate, combinations from typing import List, Tuple
- %% Factors
def factors5(n: int) -> List[int]:
"""Factors of n, (but not n).""" def prime_powers(n): # c goes through 2, 3, 5, then the infinite (6n+1, 6n+5) series for c in accumulate(chain([2, 1, 2], cycle([2,4]))): if c*c > n: break if n%c: continue d,p = (), c while not n%c: n,p,d = n//c, p*c, d + (p,) yield(d) if n > 1: yield((n,))
r = [1] for e in prime_powers(n): r += [a*b for a in r for b in e] return r[:-1]
- %% Powerset
def powerset(s: List[int]) -> List[Tuple[int, ...]]:
"""powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3) .""" return list(chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))
- %% Practical number
def is_practical(x: int) -> bool:
""" Is x a practical number.
I.e. Can some selection of the proper divisors of x, (other than x), sum to i for all i in the range 1..x-1 inclusive. """ if x == 1: return True if x %2: return False # No Odd number more than 1 f = factors5(x) ps = powerset(f) found = [y for y in {sum(i) for i in ps} if 1 <= y < x] return len(found) == x - 1
if __name__ == '__main__':
n = 333 p = [x for x in range(1, n + 1) if is_practical(x)] print(f"There are {len(p)} Practical numbers from 1 to {n}:") print(' ', str(p[:10])[1:-1], '...', str(p[-10:])[1:-1]) x = 666 print(f"\nSTRETCH GOAL: {x} is {'not ' if not is_practical(x) else }Practical.")</lang>
- Output:
There are 77 Practical numbers from 1 to 333: 1, 2, 4, 6, 8, 12, 16, 18, 20, 24 ... 288, 294, 300, 304, 306, 308, 312, 320, 324, 330 STRETCH GOAL: 666 is Practical.