12345678910111213141516171819202122232425262728293031 |
- #!/usr/bin/ruby
- # Efficient algorithm, due to M. F. Hasler (Jan 13 2013), for efficiently
- # checking if a given number is a practical number, using its prime factorization.
- # See also:
- # https://oeis.org/A005153
- # https://rosettacode.org/wiki/Practical_numbers
- func is_practical(n) {
- n.is_odd && return (n == 1)
- n.is_pos || return false
- var p = 1
- var f = n.factor_exp
- f.each_cons(2, {|a,b|
- p *= sigma(a.head**a.tail)
- b.head > (1 + p) && return false
- })
- return true
- }
- say 20.by { is_practical(_) } #=> [1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60]
- say is_practical(666) #=> true
- say is_practical(6666) #=> true
- say is_practical(66666) #=> false
|