Combinations with repetitions/Square digit chain: Difference between revisions

</pre>▼

=={{header|Phix}}==▼

There is a solution to this on the [[Iterated_digits_squaring#Combinatorics_version|Iterated_digits_squaring]] page▼

=={{header|Ruby}}==▼

<lang ruby>▼

# Count how many number chains for Natural Numbers < 10**K end with a value of 1.▼

#▼

# Nigel_Galloway▼

# 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▼

}▼

#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>▼

{{out}}▼

<pre>▼

#(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▼