A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 32 13 10 1 1
85 89 145 42 20 4 16 37 58 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

+-#distinct_perm_count
def distinct_perm_count(s)
	base=factorial(s.length)
	s.uniq.each{|i|base/=factorial(s.count(i))}
	base
end

+-#factorial
def factorial(n)
  return 1 if n<2
  (2..n).inject{|u,v|u*v}
end

+-#squares
def squares(n)
  n*n
end

+-#Enumerable
module Enumerable
  def sum
    self.inject{|u,v|u+v}
  end
  def product
    self.inject{|u,v|u*v}
  end
  def count(ob)
    self.select{|i|i==ob}.length
  end
  def take_while
    return [] unless yield(self.first)
    if(self.class==Range)
      evalPoint=self.first
      evalPoint=evalPoint.succ while yield(evalPoint.succ) and not evalPoint==self.last
      return self.first..evalPoint
    else
      s=self.to_a
      upTo=1
      upTo+=1 while yield(s[upTo]) and upTo<self.length
      return self[0...upTo]
    end
  end
end

+-#dig_split
def dig_split(n)
  s=n.to_s
  s.split("").map{|i|i.to_i}
end

def p92_go(n)
  return 1 if $one.include?(n)
  return 89 if $eighty_nine.include?(n)
  x=p92_go(dig_split(n).map{|i|i*i}.sum)
  $one.add(n) if x==1
  $eighty_nine.add(n) if x==89
  x
end

def p92_branch(l,m)
  if($eighty_nine.include?(l.map{|i|$squares[i]}.sum))
    $ans+=distinct_perm_count(l)
  end
  return if m==7 or l.all?{|i|i==9}
  (m...7).each do |i|
    p92_branch(l[0...i]+l[i..-1].map{|j|j+1},i) if l[i..-1].all?{|j|j<9}
  end
end

def p92
  $one,$eighty_nine=[1].to_set,[89].to_set
  (1..567).each{|i|p92_go(i)}
  $squares=(0..9).map{|i|i*i}
  $ans=0
  p92_branch([0,0,0,0,0,0,0],0)
  puts $ans
end