Combinations with repetitions/Square digit chain: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 13: | Line 13: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<lang ruby> |
<lang ruby> |
||
# Count how many number chains for Natural Numbers < |
# Count how many number chains for Natural Numbers < 10**K end with a value of 1. |
||
# |
# |
||
# Nigel_Galloway |
# Nigel_Galloway |
||
# August 26th., 2014. |
# August 26th., 2014. |
||
K = 17 |
|||
require 'benchmark' |
|||
⚫ | |||
D = 8 #Calculate from 1 to 10**D (8 for task) |
|||
⚫ | |||
g = -> n, gn=[n,0], res=0 { while gn[0]>0 |
g = -> n, gn=[n,0], res=0 { while gn[0]>0 |
||
gn = gn[0].divmod(10) |
gn = gn[0].divmod(10) |
||
Line 25: | Line 24: | ||
end |
end |
||
return res==89?0:res |
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( |
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 |
z = 0 #Running count of numbers translating to 1 |
||
⚫ | |||
t = Benchmark.measure do |
|||
next if N[n.inject(:+)] == 0 #Count only ones |
|||
⚫ | |||
nn = Hash.new{0} #Determine how many numbers this digit combination corresponds to |
|||
nn = |
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 |
|||
z += nn.values.inject(F[D]){|gn,n| gn/F[n]}#Add to the count of numbers terminating in 1 |
|||
} |
} |
||
⚫ | |||
end |
|||
⚫ | |||
puts "\n\nTiming\n#{t}" |
|||
</lang> |
</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> |