Combinations with repetitions/Square digit chain

Iterated digits squaring introduces RC the Project Euler Task #92. Combinations with repetitions introduce RC to the concept of generating all the combinations with repetitions of n types of things taken k at a time.

The purpose of this task is to combine these tasks as follows:

The set of things from which k will be taken is [0,1,4,9,16,25,36,49,64,81] and must be obtained using code from Combinations with repetitions

For each set of k items determine if it translates to 1 using the rules from Iterated digits squaring

For each set which translates to 1 determine the number of different ways, c say, in which the k items can be uniquely ordered

Keep a running total of all the values of c obtained

Answer the Project Euler Task #92 question.

Ruby

Count how many number chains for Natural Numbers <= 100,000,000 end with a value 89.
Nigel_Galloway
August 26th., 2014.

require 'benchmark' D = 8 #Calculate from 1 to 10**D (8 for task) F = Array.new(D+1){|n| n==0?1:(1..n).inject(:*)} #Some small factorials g = -> n, gn=[n,0], res=0 { while gn[0]>0

                             gn = gn[0].divmod(10)
                             res += gn[1]**2
                           end
                           return res==89?0:res

An array: N[n]==0 means that n translates to 89 and 1 means that n translates to 1 }

N = (G=Array.new(D*81+1){|n| n==0? 1:(i=g.call(n))==89 ? 0:i}).collect{|n| while n>1 do n = G[n] end; n }

z = 0 #Running count of numbers translating to 1 t = Benchmark.measure do [0,1,4,9,16,25,36,49,64,81].repeated_combination(D).each{|n| #Iterate over unique digit combinations

   next if N[n.inject(:+) == 0                                #Count only ones
   nn = Hash.new(){0}                         #Determine how many numbers this digit combination corresponds to
   n.each{|n| nn[n] += 1}                     #and
   z += nn.values.inject(F[D]){|gn,n| gn/F[n]}#Add to the count of numbers terminating in 1

} end puts "\n\n#{z} numbers produce 1 and #{10**D-z} numbers produce 89"

puts "\n\nTiming\n#{t}" </lang>