Rosetta Code

Combinations with repetitions/Square digit chain: Difference between revisions

Page Discussion

Combinations with repetitions/Square digit chain (view source)

Revision as of 13:28, 17 September 2014

510 bytes added ,  9 years ago
→‎{{header|Ruby}}
No edit summary
Line 13:
=={{header|Ruby}}==
<lang ruby>
# Count how many number chains for Natural Numbers <= 100,000,00010**K end with a value 89of 1.
#
# Nigel_Galloway
# August 26th., 2014.
K = 17
require 'benchmark'
F = Array.new(DK+1){|n| n==0?1:(1..n).inject(:*)} #Some small factorials▼
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)
Line 25 ⟶ 24:
end
return res==89?0:res
#An array: N[n]==1 means that n translates 1, 0 means that it does not. }
#An array: N[n]==1 means that n translates to 1, 0 means that it does not.
N = (G=Array.new(DK*81+1){|n| n==0? 10:(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,1,4,..9,16,25,36,49,64,81]).collect{|n| n**2}.repeated_combination(DK).each{|n| #Iterate over unique digit combinations▼
t = Benchmark.measure do
next if N[n.inject(:+)] == 0 #Count only ones
▲[0,1,4,9,16,25,36,49,64,81].repeated_combination(D).each{|n| #Iterate over unique digit combinations
nextnn if= N[nHash.inject(:+)new{0} == 0 #CountDetermine how many numbers this digit combination onlycorresponds onesto
n.each{|n| nn[n] += Hash.new(){01} #Determine how many numbers this digit combination corresponds to #and
nz += nn.eachvalues.inject(F[K]){|gn,n| nngn/F[n] += 1} #Add to the count of numbers terminating in #and1
z += nn.values.inject(F[D]){|gn,n| gn/F[n]}#Add to the count of numbers terminating in 1
}
puts "\nnk=(#{K}) in the range 1 to #{10**K-1}\n#{z} numbers produce 1 and #{10**DK-1-z} numbers produce 89"▼
end
▲puts "\n\n#{z} numbers produce 1 and #{10**D-z} numbers produce 89"
 
puts "\n\nTiming\n#{t}"
</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
</pre>
Nigel Galloway
2,172

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/250294"