151012(3)

Ruby

Number of times 1 is used in writing out all the numbers 1 through n(7)

f(2, 10 ** 10) を５ヶ月ほど前計算したことを思い出した。
(http://ideone.com/u7HdVj)
そこで、f(m, 10 ** i) をもう少し調べてみた。

# 高速化
def g(m, str, s)
  if s == 1
    return 0 if str == '0'
    return 1
  end
  a = str[0].to_i
  str1 = str[1..-1]
  return g(m, str1, s - 1) if a == 0
  return (s - 1) * m ** (s - 2) + 1 + str1.to_i(m) + g(m, str1, s - 1) if a == 1
  return a * (s - 1) * m ** (s - 2) + m ** (s - 1) + g(m, str1, s - 1)
end

def f(m, n)
  str = n.to_s(m)
  g(m, str, str.size)
end

def f_ary(m, ary)
  ary.map{|i| f(m, i)}
end

ary = (0..30).map{|i| 10 ** i}
(2..10).each{|m| p [m, f_ary(m, ary)]}

出力結果
[2, [1, 17, 319, 4938, 64613, 815030, 9884999, 114434632, 1314447116, 14846928141, 164293127179, 1809725656079, 19809942118413, 214309466746894, 2306412649693201, 24784747400675348, 264286863212871700, 2804216299269586964, 29761222783429247000, 314231954224804790291, 3301678091638143975450, 34722183171345671520285, 364370351327204996022297, 3799630573079809501429787, 39695385437637887626575902, 414481926914340004642684947, 4298429306008723825539153951, 44678554212330354478835302433, 464758015834485209941739044893, 4798702669950589113263389147172, 49657738936018521227027139264549]]
[3, [1, 9, 150, 2194, 30374, 379432, 4508710, 51180200, 572158742, 6417405502, 70402455152, 769364418852, 8452692931320, 91673681872620, 993534122918024, 10779360089419044, 114661242594171254, 1216758202087170334, 12767569182895088152, 133862436956018539886, 1405771200630725286006, 14663860400505783919608, 153796494936787179989436, 1614986483014523055902106, 16887592497038459726705624, 177308495497250974401699424, 1846007098588454905102196728, 19172094511757798531897719532, 197677440096181467378574033316, 2037819660431890371250386506764, 21087982689937490731566483680876]]
[4, [1, 7, 119, 1270, 19482, 242178, 2520434, 31973411, 366171397, 3790564097, 44245876996, 488164976133, 5056725669893, 56692742610948, 610964919316485, 6310200205451268, 69321688173772803, 732713250404499465, 7571981434117226501, 82037556623093661699, 854087328285483073545, 8814800381086001004552, 94722289936057215483909, 973215603996092086091784, 10042775926285679481323524, 107193424611029871262433293, 1094927512861631153262559239, 11294729851272492427228741634, 119893894654631361202345738248, 1216129526537655672735115771912, 12564494019293974745563833303049]]
[5, [1, 7, 65, 1226, 13001, 165627, 2028125, 20171876, 268203127, 2645703125, 32294921876, 331865234377, 3689306640628, 40104003906250, 403492431640629, 4679504394531250, 46297943115234377, 525622406005859377, 5326352691650390626, 57214763641357421878, 600465202331542968751, 6073609542846679687504, 66583832740783691406250, 664710590839385986328129, 7260833132266998291015627, 73223027288913726806640626, 775132898688316345214843753, 7986859233677387237548828126, 80951736219227313995361328129, 863699755929410457611083984377, 8654589133337140083312988281252]]
[6, [1, 7, 71, 731, 11198, 145691, 1471583, 15044020, 209959005, 2215950297, 22357576982, 260732117894, 2964571630298, 29734482337166, 300804840123645, 3596403661788849, 37220596165405190, 373942198480119148, 4097855055721481385, 44696639571507276727, 447357911583038454820, 4507221089612289882735, 50957678725204529674292, 522423493113073904971028, 5237942923211234920118775, 55861845725776606242564250, 597738819735637161095723198, 5978498177859560689393554348, 60114808605080898875434217157, 659222499890635670519267561691, 6722194098228926259163478574015]]
[7, [1, 6, 78, 780, 8110, 88500, 1219870, 15865600, 172539968, 1731378357, 17700998204, 189189870494, 2383125982820, 26133698711472, 261771343230968, 2684380968983890, 27311303300643582, 312355937793457211, 3463944584394735456, 35601953767056758691, 357533815140350476230, 3630857630320495382668, 37779610844512699452723, 425041907065853528823289, 4466458203133567081386951, 44618338243477807545984051, 452940874938696904182501635, 4603505594762070258781889621, 50198736040249262034751004601, 532922641777229881768673946230, 5403147555399084356218382285511]]
[8, [1, 5, 66, 870, 9418, 95404, 1020178, 10910114, 116961408, 1269319104, 15420668802, 186335569154, 2092258707459, 22324231147523, 223533368487937, 2300102388453377, 23678250753204227, 244218428740583426, 2521303233634959362, 26987371554266808324, 307381704052157972481, 3312167967401039364099, 34662251320016253747201, 352132946710859256692738, 3580993929556662847275012, 36151550056345656205770756, 369998943087644997308121092, 3791006228343139484888465411, 38829724147853438538318086146, 428005188847297506828343050243, 4528454022449639996752494854147]]
[9, [1, 4, 50, 663, 8260, 99109, 1143090, 12527839, 135246289, 1409108421, 14660616984, 155444059591, 1630739921525, 17024720710829, 180215825517231, 1876739468499213, 19764853172536251, 205589163931606489, 2155867004951010588, 22558669798425164931, 235436287048196113944, 2460489043375692066252, 26752599254052604541911, 294272850260761602792780, 3112641278712249425091604, 32764467158341991897094435, 344095897737184879884337351, 3596843315781575484981559027, 36918489296419678748627212344, 379144290872420566267722670492, 3844334443631408268993122982013]]
[10, [1, 2, 21, 301, 4001, 50001, 600001, 7000001, 80000001, 900000001, 10000000001, 110000000001, 1200000000001, 13000000000001, 140000000000001, 1500000000000001, 16000000000000001, 170000000000000001, 1800000000000000001, 19000000000000000001, 200000000000000000001, 2100000000000000000001, 22000000000000000000001, 230000000000000000000001, 2400000000000000000000001, 25000000000000000000000001, 260000000000000000000000001, 2700000000000000000000000001, 28000000000000000000000000001, 290000000000000000000000000001, 3000000000000000000000000000001]]