Sha256: a9e780481df12e7e127262122697e4d58c60b278aa0f4d2d68e722d41a746f69

Contents?: true

Size: 1.46 KB

Versions: 1

Compression:

Stored size: 1.46 KB

Contents

# coding: utf-8
class Integer
  def φ
    return 1 if self == 1
    return self - 1 if prime?
    (prime_factors.uniq.map{|f| 1 - f.reciprocal}.reduce(:*) * self).to_i
  end

  alias :totient :φ


  # Returns `true` if `self` is equal to the sum of its iterated
  # totients, otherwise `false`
  #
  # For example:  φ(183) = 120
  #               φ(120)  = 32
  #               φ(32)   = 16
  #               φ(16)    = 8
  #               φ(4)     = 2
  #               φ(2)     = 1
  # 120 + 32 + 16 + 8 + 4 + 2 + 1 = 183
  # @return [true, false] `true` if `self` is a perfect totient; `false` otherwise.
  def perfect_totient?
    # TODO: Possible optimisation: once the totient is a power of 2,
    # which we identify using bit ops, it is predictable what totients
    # will follow. For example, consider 441027. Its iterated totients
    # are [294012, 97992, 32640, 8192, 4096, 2048, 1024, 512, 256,
    # 128, 64, 32, 16, 8, 4, 2, 1], i.e. 17 iterations are
    # needed. Once we hit 8192, we can derive [2, 4, 8, 16, 32, 64,
    # 128, 256, 512, 1024, 2048, 4096, 8192], add the 1, then return.

    # TODO: The more obvious tweak is to return true immediately when
    # self is a power of 3. I want to write a #power_of? predicate for
    # the general case first, then benchmark it for use here.
    return false if even?
    a = [totient]
    sum = a.first
    until a.last == 1 or sum > self
      a << a.last.totient
      sum += a.last
    end
    sum == self
  end
end

Version data entries

1 entries across 1 versions & 1 rubygems

Version Path
numb-0.186.0 lib/numb/totient.rb