Combinations with repetitions/Square digit chain

Combinations with repetitions/Square digit chain is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 collections of k items will be taken from [0,1,4,9,16,25,36,49,64,81] and must be obtained using code from Combinations with repetitions. The collection of k zeroes is excluded.

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

For each collection 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 (k=7).

Answer the equivalent question for k=8,11,14.

Optionally answer the question for k=17. These numbers will be larger than the basic integer type for many languages, if it is not easy to use larger numbers it is not necessary for this task.

Ruby

<lang ruby>

1. Count how many number chains for Natural Numbers < 10**K end with a value of 1.
3. Nigel_Galloway
4. August 26th., 2014.

K = 17 F = Array.new(K+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
                          }

1. An array: N[n]==1 means that n translates to 1, 0 means that it does not.

N = (G=Array.new(K*81+1){|n| n==0? 0:(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 (0..9).collect{|n| n**2}.repeated_combination(K).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[K]){|gn,n| gn/F[n]}             #Add to the count of numbers terminating in 1

} puts "\nk=(#{K}) in the range 1 to #{10**K-1}\n#{z} numbers produce 1 and #{10**K-1-z} numbers produce 89" </lang>

Output:

#(k=7) in the range 1 to 9999999
#1418853 numbers produce 1 and 8581146 numbers produce 89

#(k=8) in the range 1 to 99999999
#14255666 numbers produce 1 and 85744333 numbers produce 89

#(k=11) in the range 1 to 99999999999
#15091199356 numbers produce 1 and 84908800643 numbers produce 89

#(k=14) in the range 1 to 99999999999999
#13770853279684 numbers produce 1 and 86229146720315 numbers produce 89

#(k=17) in the range 1 to 99999999999999999
#12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89