ナベアツ問題

俺も考えてみよう。総当たりとか近似値とかはすでにやっていらっしゃるようなので、確率方面?から。

1桁の数字の場合

1桁の数字は 10個 (0を含めて考えてる) あって、3の倍数は 3個。3がつく数字は、1個。重複があるので、3個。

2桁の数字の場合 (ここから近似)

3の倍数は、全体の 1/3
3がつく数字は…。10の位も 1の位も 3じゃない場合を引けばいいから、1 - (8/9 * 9/10) = 1/5 → 全体の 1/5
1/3 と 1/5 で重複分があるから、1/3 + 1/5 - (1/3 * 1/5) = 7/15
全部で 100-90個の数字があるので、90 * 7/15 = 42個。

5桁の数字の場合の確率

10000〜99999 の、90000個の数字がある。
3で割り切れる数字は、1/3個。

3がつく数字は、3がつかない数字から考えると、1 - 8/9 * (9/10)^4 = 1 - (9^3)/(10^4)
重複分があるから、1/3 + (1 - ((9^3)/(10^4))) - 1/3 * (1 - ((9^3)/(10^4)))。
なので、900000 * (1/3 + (1 - ((9^3)/(10^4))) - 1/3 * (1 - ((9^3)/(10^4))))
3がつく数字は、3がつかない数字から考えると、1 - 8/9 * (9/10)^4 = 1 - 8*(9^3)/(10^4)
重複分があるから、1/3 + (1 - (8*(9^3)/(10^4))) - 1/3 * (1 - (8*(9^3)/(10^4)))。
なので、900000 * (1/3 + (1 - ((8*9^3)/(10^4))) - 1/3 * (1 - (8*(9^3)/(10^4))))

あとは Excel でやってみた。

桁数 指定桁の数の総数 3の倍数の割合 3がつく数字の割合 重複分を除いた割合 指定桁で、3の倍数か3がつく数字の個数 指定桁までの数の総数 指定桁までで、3の倍数か3がつく数字の個数 割合
1 10 0.33333 0.10000 0.30000 3 10 3 0.30000
2 90 0.33333 0.20000 0.46667 42 100 45 0.45000
3 900 0.33333 0.28000 0.52000 468 1000 513 0.51300
4 9000 0.33333 0.35200 0.56800 5112 10000 5625 0.56250
5 90000 0.33333 0.41680 0.61120 55008 100000 60633 0.60633
6 900000 0.33333 0.47512 0.65008 585072 1000000 645705 0.64571
7 9000000 0.33333 0.52761 0.68507 6165648 10000000 6811353 0.68114
8 90000000 0.33333 0.57485 0.71656 64490832 100000000 71302185 0.71302
9 900000000 0.33333 0.61736 0.74491 670417488 1000000000 741719673 0.74172
10 9000000000 0.33333 0.65563 0.77042 6933757392 10000000000 7675477065 0.76755
11 90000000000 0.33333 0.69006 0.79338 71403816528 100000000000 79079293593 0.79079
12 900000000000 0.33333 0.72106 0.81404 732634348752 1000000000000 811713642345 0.81171
13 9000000000000 0.33333 0.74895 0.83263 7493709138768 10000000000000 8305422781113 0.83054
14 90000000000000 0.33333 0.77406 0.84937 76443382248912 100000000000000 84748805030025 0.84749
15 900000000000000 0.33333 0.79665 0.86443 777990440240208 1000000000000000 862739245270233 0.86274
16 9000000000000000 0.33333 0.81699 0.87799 7901913962161870 10000000000000000 8764653207432100 0.87647
17 90000000000000000 0.33333 0.83529 0.89019 80117225659456800 100000000000000000 88881878866889000 0.88882
18 900000000000000000 0.33333 0.85176 0.90117 811055030935112000 1000000000000000000 899936909802001000 0.89994
19 9000000000000000000 0.33333 0.86658 0.91106 8199495278416000000 10000000000000000000 9099432188218000000 0.90994
20 90000000000000000000 0.33333 0.87992 0.91995 82795457505744000000 100000000000000000000 91894889693962000000 0.91895
21 900000000000000000000 0.33333 0.89193 0.92795 835159117551696000000 1000000000000000000000 927054007245658000000 0.92705
22 9000000000000000000000 0.33333 0.90274 0.93516 8416432057965270000000 10000000000000000000000 9343486065210920000000 0.93435
23 90000000000000000000000 0.33333 0.91246 0.94164 84747888521687400000000 100000000000000000000000 94091374586898300000000 0.94091
24 900000000000000000000000 0.33333 0.92122 0.94748 852730996695187000000000 1000000000000000000000000 946822371282085000000000 0.94682
25 9000000000000000000000000 0.33333 0.92910 0.95273 8574578970256680000000000 10000000000000000000000000 9521401341538770000000000 0.95214
26 90000000000000000000000000 0.33333 0.93619 0.95746 86171210732310100000000000 100000000000000000000000000 95692612073848900000000000 0.95693
27 900000000000000000000000000 0.33333 0.94257 0.96171 865540896590791000000000000 1000000000000000000000000000 961233508664640000000000000 0.96123
28 9000000000000000000000000000 0.33333 0.94831 0.96554 8689868069317120000000000000 10000000000000000000000000000 9651101577981760000000000000 0.96511
29 90000000000000000000000000000 0.33333 0.95348 0.96899 87208812623854100000000000000 100000000000000000000000000000 96859914201835800000000000000 0.96860
30 900000000000000000000000000000 0.33333 0.95813 0.97209 874879313614687000000000000000 1000000000000000000000000000000 971739227816523000000000000000 0.97174
31 9000000000000000000000000000000 0.33333 0.96232 0.97488 8773913822532180000000000000000 10000000000000000000000000000000 9745653050348700000000000000000 0.97457
32 90000000000000000000000000000000 0.33333 0.96609 0.97739 87965224402789600000000000000000 100000000000000000000000000000000 97710877453138300000000000000000 0.97711
33 900000000000000000000000000000000 0.33333 0.96948 0.97965 881687019625106000000000000000000 1000000000000000000000000000000000 979397897078245000000000000000000 0.97940
34 9000000000000000000000000000000000 0.33333 0.97253 0.98169 8835183176625960000000000000000000 10000000000000000000000000000000000 9814581073704200000000000000000000 0.98146
35 90000000000000000000000000000000000 0.33333 0.97528 0.98352 88516648589633600000000000000000000 100000000000000000000000000000000000 98331229663337800000000000000000000 0.98331
36 900000000000000000000000000000000000 0.33333 0.97775 0.98517 886649837306703000000000000000000000 1000000000000000000000000000000000000 984981066970040000000000000000000000 0.98498
37 9000000000000000000000000000000000000 0.33333 0.97997 0.98665 8879848535760320000000000000000000000 10000000000000000000000000000000000000 9864829602730360000000000000000000000 0.98648
38 90000000000000000000000000000000000000 0.33333 0.98198 0.98798 88918636821842900000000000000000000000 100000000000000000000000000000000000000 98783466424573300000000000000000000000 0.98783
39 900000000000000000000000000000000000000 0.33333 0.98378 0.98919 890267731396586000000000000000000000000 1000000000000000000000000000000000000000 989051197821160000000000000000000000000 0.98905
40 9000000000000000000000000000000000000000 0.33333 0.98540 0.99027 8912409582569280000000000000000000000000 10000000000000000000000000000000000000000 9901460780390440000000000000000000000000 0.99015
41 90000000000000000000000000000000000000000 0.33333 0.98686 0.99124 89211686243123500000000000000000000000000 100000000000000000000000000000000000000000 99113147023513900000000000000000000000000 0.99113
42 900000000000000000000000000000000000000000 0.33333 0.98818 0.99212 892905176188111000000000000000000000000000 1000000000000000000000000000000000000000000 992018323211625000000000000000000000000000 0.99202
43 9000000000000000000000000000000000000000000 0.33333 0.98936 0.99291 8936146585693000000000000000000000000000000 10000000000000000000000000000000000000000000 9928164908904630000000000000000000000000000 0.99282
44 90000000000000000000000000000000000000000000 0.33333 0.99042 0.99361 89425319271237000000000000000000000000000000 100000000000000000000000000000000000000000000 99353484180141600000000000000000000000000000 0.99353
45 900000000000000000000000000000000000000000000 0.33333 0.99138 0.99425 894827873441133000000000000000000000000000000 1000000000000000000000000000000000000000000000 994181357621275000000000000000000000000000000 0.99418
46 9000000000000000000000000000000000000000000000 0.33333 0.99224 0.99483 8953450860970200000000000000000000000000000000 10000000000000000000000000000000000000000000000 9947632218591470000000000000000000000000000000 0.99476
47 90000000000000000000000000000000000000000000000 0.33333 0.99302 0.99535 89581057748731800000000000000000000000000000000 100000000000000000000000000000000000000000000000 99528689967323300000000000000000000000000000000 0.99529
48 900000000000000000000000000000000000000000000000 0.33333 0.99372 0.99581 896229519738586000000000000000000000000000000000 1000000000000000000000000000000000000000000000000 995758209705909000000000000000000000000000000000 0.99576
49 9000000000000000000000000000000000000000000000000 0.33333 0.99434 0.99623 8966065677647270000000000000000000000000000000000 10000000000000000000000000000000000000000000000000 9961823887353180000000000000000000000000000000000 0.99618
50 90000000000000000000000000000000000000000000000000 0.33333 0.99491 0.99661 89694591098825500000000000000000000000000000000000 100000000000000000000000000000000000000000000000000 99656414986178700000000000000000000000000000000000 0.99656

限りなく 100% に近づいていきそうです。

ちなみに、計算式は下記です。

A:桁数 B:指定桁の数の総数 C:3の倍数の割合 D:3がつく数字の割合 E:重複分を除いた割合 F:指定桁で、3の倍数か3がつく数字の個数 G:指定桁までの数の総数 H:指定桁までで、3の倍数か3がつく数字の個数 I:割合
1 10 =1/3 =1-9/10 =3/10 =B2*E2 =B2 =F2 =H2/G2
2 =10^A3-10^(A3-1) =1/3 =1-(8/9 * (9/10)^(A3-1)) =C3+D3-(C3*D3) =B3*E3 =G2+B3 =H2+F3 =H3/G3

3行目以降は同じ。

計算式の解説。

yoggy さんは数に注目して計算されていますが、私はどちらかというと統計的に？確率的に？考えました。
この方式の利点は、総当たりなどをしないために CPU パワーなどほとんど関係なく、時間もかからないこと。桁数の多い計算機があればパソコンなくてもきっと大丈夫。プログラミング言語も知らなくて OK。
では、計算内容です。
(^ は、べき乗です。)

  • A: 桁数です。
  • B: A の桁数での、数の数。2桁なら、10〜99 の 90個で、これは 10^2 - 10^1。n桁の場合は 10^n - 10^(n-1)。
  • C: 3の倍数の割合。誤差は出るがおしなべて 1/3。
  • D: 3がつく数の割合。たぶんここがこの方式のミソ。まず、3がつかない数を割合を求める。
    • n桁の場合、頭の桁は 0 はあり得なくて、3 でない数、つまり 1,2,4,5,6,7,8,9 でないとダメだから、9通りのうちの 8通りがあり得る。
    • 頭の桁以外は、3でない数、つまり 0,1,2,4,5,6,7,8,9 でないとダメだから、10通りのうち 9通り。
    • n桁だから、8/9 * (9/10) * (9/10) * ... * (9/10) = 8/9 * (9/10)^(n-1) が、3がつかない数の割合。
    • 3がつく数の割合は、1- (8/9 * (9/10)^(n-1)) になります。
  • E: C と D の合計。ただし重複分を除く。C + D - (C * D)
  • F: アホになる数の数は、総数 * 割合 = B * E。

で、ここまでは桁数ごとに計算していたので、G, H でここまでの合計を計算し、I で割合を求めています。
1桁の場合はハナっから誤差が出るので手計算し、2桁以上はすべて上の計算式で求めてみました。

ちなみに　yoggy さんちとの比較

yoggy さんちの表を抜粋すると、こんなかんじ。

n 力づくで数えたアホになる数の総数 yoggy さんがプログラムを使って求めた近似値
10000000000 7675477065 7675477066

10桁のところまでは、「力づくで数えた」のほうと、私の計算結果が一致しているようです。結構精度悪くなさそう。