Wednesday, February 10, 2010

Comprime and Residue class group

Ruby has the library 'prime'. And I create sample program to handle "coprime" and "residue class group".

residue.rb
class Integer

  # return all coprimes of self
  def coprimes
    if self.prime?
      (1...self).to_a
    else
      [1] + (Integer.each_prime(self).to_a - self.prime_division.transpose[0])
    end
  end
  
  # Is self comprime with argument number?
  def coprime_with?(other)
    coprimes.include?(other)
  end

  # return reduced residue class group
  def reduced_residue_class_group
    z_mz(coprimes)
  end

  # return residue class group
  def residue_class_group
    z_mz(0...self)
  end

  private
  def z_mz(numbers)
    group = numbers.inject([]) do |result, i|
      result << numbers.inject([]) do |inner_result, j|
        inner_result << ((i * j) % self)
      end
    end

    # change behavior of to_s to multiple group with formatted spaces
    def group.to_s
      digit = self.flatten.max / 10 + 1
      self.inject('') do |result, array|
        result << array.inject('') do |inner_result, item|
          inner_result << ("%#{digit + 1}d" % item)
        end << "\n"
      end
    end

    group
  end
end

$ irb -r 'residue.rb'
irb(main):001:0> 12.coprimes
=> [1, 5, 7, 11]
irb(main):002:0> 12.coprime_with?(5)
=> true
irb(main):003:0> 12.coprime_with?(6)
=> false
irb(main):004:0> puts 12.residue_class_group.to_s
  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  3  4  5  6  7  8  9 10 11
  0  2  4  6  8 10  0  2  4  6  8 10
  0  3  6  9  0  3  6  9  0  3  6  9
  0  4  8  0  4  8  0  4  8  0  4  8
  0  5 10  3  8  1  6 11  4  9  2  7
  0  6  0  6  0  6  0  6  0  6  0  6
  0  7  2  9  4 11  6  1  8  3 10  5
  0  8  4  0  8  4  0  8  4  0  8  4
  0  9  6  3  0  9  6  3  0  9  6  3
  0 10  8  6  4  2  0 10  8  6  4  2
  0 11 10  9  8  7  6  5  4  3  2  1
=> nil
irb(main):005:0> puts 12.reduced_residue_class_group.to_s
  1  5  7 11
  5  1 11  7
  7 11  1  5
 11  7  5  1
=> nil

No comments:

Post a Comment