Practical numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{Header|Raku}}: Add a Raku example)
m (→‎{{header|Raku}}: Better variable name, stretchy)
Line 86: Line 86:


sub is-practical ($n) {
sub is-practical ($n) {
my @proper = $n.&proper-divisors.combinations».sum.unique.sort;
my @proper-sums = $n.&proper-divisors.combinations».sum.unique.sort;
+@proper < $n-1 ?? False !! @proper[^$n] eqv (^$n).list ?? True !! False
+@proper-sums < $n-1 ?? False !! @proper-sums[^$n] eqv (^$n).list ?? True !! False
}
}


say "{+$_} matching numbers:\n{.batch(10)».fmt('%3d').join: "\n"}"
say "{+$_} matching numbers:\n{.batch(10)».fmt('%3d').join: "\n"}\n"
given [ (1..333).hyper(:32batch).grep: { is-practical($_) } ];
given [ (1..333).hyper(:32batch).grep: { is-practical($_) } ];


say "\n666 is practical? ", is-practical 666;</lang>
say " 666 is practical? ", is-practical 666;
say " 6666 is practical? ", is-practical 6666;
say "66666 is practical? ", is-practical 66666;</lang>
{{out}}
{{out}}
<pre>77 matching numbers:
<pre>77 matching numbers:
Line 105: Line 107:
304 306 308 312 320 324 330
304 306 308 312 320 324 330


666 is practical? True</pre>
666 is practical? True
6666 is practical? True
66666 is practical? False</pre>

Revision as of 17:27, 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

  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.

Raku

<lang perl6>use Prime::Factor:ver<0.3.0+>;

sub is-practical ($n) {

  my @proper-sums = $n.&proper-divisors.combinations».sum.unique.sort;
  +@proper-sums < $n-1 ?? False !! @proper-sums[^$n] eqv (^$n).list ?? True !! False

}

say "{+$_} matching numbers:\n{.batch(10)».fmt('%3d').join: "\n"}\n"

   given [ (1..333).hyper(:32batch).grep: { is-practical($_) } ];

say " 666 is practical? ", is-practical 666; say " 6666 is practical? ", is-practical 6666; say "66666 is practical? ", is-practical 66666;</lang>

Output:
77 matching numbers:
  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
 6666 is practical? True
66666 is practical? False