for josh

pe_70.rb

require 'prime'
require 'pp'

def each_multiple(base, boundary)
  multiplier = 1
  while (product = base * multiplier) < boundary
    # puts "#{prime}: totients[#{product}] -= #{multiplier}"
    yield product, multiplier
    multiplier += 1
  end
end

def each_divisor(boundary, base, rest, lower_bound=0, &block)
  lower_bound.upto rest.size-1 do |index|
    current = rest[index]
    divisor = base * current
    return if boundary < divisor
    block.call divisor
    each_divisor(boundary, divisor, rest, index+1, &block)
  end
end
       
size     = 30.next
totients = Array.new(size) { |i| i }

              
Prime.each do |prime|
  break if size < prime
                
  # reduce multiples of the prime
  each_multiple(prime, size) { |multiple, multiplier| 
    puts "#{prime}: totients[#{multiple}] -= #{multiplier}" if multiple == 30
    totients[multiple] -= multiplier }
  
  # undo double reductions
  subprimes = Prime.take_while { |subprime| subprime != prime }
  each_divisor size, prime, subprimes do |divisor|
    each_multiple(divisor, size) { |multiple, multiplier| 
      puts "#{prime}: totients[#{multiple}] += #{multiplier}" if multiple == 30
      totients[multiple] += multiplier }
  end
end       

# totients.each_with_index do |n, i|
#   p [i, n]
# end 

# >> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
# >> [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]
expected = [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, 24, 70, 24, 72, 36, 40, 36, 60, 24, 78, 32, 54, 40, 82, 24, 64, 42, 56, 40, 88, 24, 72, 44, 60, 46, 72, 32, 96, 42, 60]

expected.zip(totients).each.with_index do |(e, t), i|
  if e == t
    p [i, e, t]
  else
    puts "#{i} --#{[e, t]}--"
  end
end