Practical numbers

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

1. %% 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]

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)))

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.