module NumberTheory::Divisors
Public Class Methods
Returns the ordered list of the divisors of n (1 and n included).
Example¶ ↑
>> Divisors.divisors(100) => [1, 2, 4, 5, 10, 20, 25, 50, 100]
# File lib/number-theory/divisors.rb, line 33 def self.divisors(n) factors = Primes.factor(n) ps = factors.keys.sort! self._divisors(0, factors, ps).sort!.uniq end
Returns the greatest common divisor of a and b
Example¶ ↑
>> Divisors.euclidean_algo(20, 15) = 5
# File lib/number-theory/divisors.rb, line 151 def self.euclidean_algo(a, b) a = 0 - a if a < 0 b = 0 - b if b < 0 if a == 0 || b == 0 0 else r = a - (a/b)*b while r!=0 do a = b b = r r = a - (a/b)*b end b end end
Returns the valuer of phi(n), the Euler phi function; i.e. the number of integers in [1..n] comprime to n.
Example¶ ↑
>> Divisors.euler_phi(30) => 8 >> Divisors.euler_phi(37) => 36
Algorithm¶ ↑
n is first factored, then the result is computed as n * prod_{p} (1 - 1/p) where the product spans over all the prime factors of n
# File lib/number-theory/divisors.rb, line 116 def self.euler_phi(n) return 0 if n < 1 res = n Primes.factor(n).keys.each do |i| res *= i - 1 res /= i end res end
Returns the greatest common divisor of a and b and the corresponding Bézout coefficients for ax + by = g where g is the greatest common divisor of a and b
Example¶ ↑
>> Divisors.extended_euclidean_algo(20, 15) = [5, 1, -1]
# File lib/number-theory/divisors.rb, line 172 def self.extended_euclidean_algo(a, b) a = 0 - a if a < 0 b = 0 - b if b < 0 if a == 0 || b == 0 [0, 0, 0] else r = a - (a/b)*b s0 = 1; t0 = 0 s1 = 0; t1 = 1 s2 = s0 - (a/b)*s1; t2 = t0 - (a/b)*t1 while r!=0 do a = b b = r r = a - (a/b)*b s0 = s1; t0 = t1 s1 = s2; t1 = t2 s2 = s0 - (a/b)*s1; t2 = t0 - (a/b)*t1 end ans = [] ans << b ans << s1 ans << t1 ans end end
Returns true if a positive integer is square free; returns false otherwise
A positive integer 'n' is said to be square free if no prime factor appears more than once in the list of prime factors for 'n'
Example¶ ↑
>> Divisors.square_free?(10) => true
The integer 1 is a special case since it is both a prefect square, and square free.
# File lib/number-theory/divisors.rb, line 141 def self.square_free?(n) return false if n <= 0 (Primes.factor(n)).each_value { |value| return false if value >= 2 } true end