「デジタル・ルート」問題

「デジタル・ルート」問題

締め切りが 2016/11/03 10:00 AM なので，その 1 分後に投稿されるように予約

ある自然数に対し、各桁の数字をすべて足し合わせるという変換を行います。
例えば、199 にこの変換を行うと、1＋9＋9＝19 という数になります。

さらに、得られた数に同様の変換を行います。最終的に 1 桁の数になるまで変換を繰り返し行います。
199 だと、1 回目の変換で 19 になり、2 回目の変換で 10 になり、3 回目の変換で 1 になります。

自然数 k に対し、上の変換を繰り返したときに最終的に 1 桁の数になるまでに必要な変換の回数を F(k) と定義します。
例えば F(199) ＝ 3 です。同様に、F(9) ＝ 0, F(26) ＝ 1, F(888888) ＝ 3 です。

自然数 n に対し、1 ≦ k ≦ n となる全ての k に対する F(k) の和を G(n) と定義します。
例えば G(9) ＝ 0，G(20) ＝ 12，G(149) ＝ 200, G(9876) ＝ 19951 となることが確かめられます。

標準入力から、自然数 n（1 ≦ n ≦ 10⁸）が与えられます。
標準出力に G(n) の値を出力するプログラムを書いてください。

==========================================

単純なブルートフォースによるプログラム

tbl = integer(1e8)
F = function(n) {
    in.n = n
    count = 0
    repeat {
        if (10 > n) {
            return(count)
        }
        count = count+1
        n = sum(as.integer(unlist(strsplit(as.character(n), ""))))
        if (tbl[n]) {
            count = count+tbl[n]
            count ->> tbl[in.n]
            return(count)
        }
    }
}
# F(199) # 3
# F(9) # 0
# F(26) # 1
# F(888888) # 3
G = function(k) {
    sum(sapply(1:k, F))
}
#G(48) # 48
#G(100) # 136
#G(5432) # 10539
#G(54321) # 113023
#G(90817263)
#G(99003157)

=====================================

しかし，そんなプログラムでは歯の立たないことが多いので，工夫する

seq.gen2 = function(m) {
    z = vector("list", m)
    z[[1]] = x = rep(1, 10)
    for (i in 2:m) {
        y = c(x, rep(0, 9))
        for (j in 1:9) {
            y[j+seq_along(x)] = y[j+seq_along(x)]+x
        }
        z[[i]] = y
        x = y
    }
    z
}
seq = seq.gen2(8)

リストである seq の要素は，
[[1]] 1 1 1 1 1 1 1 1 1 1
[[2]] 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1
[[3]] 1 3 6 10 15 21 28 36 45 55 63 69 73 75 75 73 69 63 55 45 36 28 21 15 10 6 3 1
[[4]] 1 4 10 20 35 56 84 120 165 220 282 348 415 480 540 592 633 660 670 660 633 592 540 480 415 348 282 220 165 120 84 56 35 20 10 4 1
[[5]] 1 5 15 35 70 126 210 330 495 715 996 1340 1745 2205 2710 3246 3795 4335 4840 5280 5631 5875 6000 6000 5875 5631 5280 4840 4335 3795 3246 2710 2205 1745 1340 996 715 495 330 210 126 70 35 15 5 1
  :
[[8]] 1 8 36 120 330 792 1716 3432 ...

G(342) は，

======================================================================
*a    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
======================================================================
      1  2  3  4  5  6  7  8  9 10  9  8  7  6  5  4  3  2  1        
         1  2  3  4  5  6  7  8  9 10  9  8  7  6  5  4  3  2  1    
            1  2  3  4  5  6  7  8  9 10  9  8  7  6  5  4  3  2  1
               1  1  1  1  1  1  1  1  1  1                                
                  1  1  1  1  1  1  1  1  1  1                            
                     1  1  1  1  1  1  1  1  1  1                        
                        1  1  1  1  1  1  1  1  1  1                    
+                          1  1  1                                            
======================================================================
*b    1  3  6 10 14 18 22 26 29 32 32 31 28 24 20 16 12  9  6  3  1
======================================================================
を用いて計算する。
*a は，G の引数となる数の各桁を足しあわせたもの。たとえば，342 なら 3+4+2 = 9。この結果は G(0) 〜 G(99999999) に対しては，0 ~ 72（= 8*9) に落ち着く。
たとえば，この数値が 67 である場合は，さらに 6+7 = 13, 1+3 = 4 となるので，実際は全体で 3 回の桁の足し算がある。
*b は *a が何回出現するかの頻度（カウント数）。
求める答えは sum((y[num]+1)*tbl)-10 である。

g = function(n) {
    y = rep(c(0,1,2,1,2,1,2,1,2,1,2,1,2,1), c(10,9,1,8,2,7,3,6,4,5,5,4,6,3))
    m = as.integer(unlist(strsplit(as.character(n), "")))
    tbl = integer(100)
    begin = 0
    for (i in (length(m)-1):1) {
        x = seq[[i]]
        for (j in seq_len(m[length(m)-i])) {
            tbl[begin+seq_along(x)] = tbl[begin+seq_along(x)]+x
            begin = begin+1
        }
    }
    x = rep(1, m[length(m)]+1)
    tbl[begin+seq_along(x)] = tbl[begin+seq_along(x)]+x
    tbl = tbl[tbl != 0]
    num = seq_along(tbl)
    cat(sum((y[num]+1)*tbl)-10)
}

G(48) # 48
g(48)

G(100) # 136
g(100)

G(5432) # 10539
g(5432)

G(54321) # 113023
g(54321)

g(90817263) # 207841726

g(99003157) # 227032799