読者です 読者をやめる 読者になる 読者になる

定理: 自然数 n を B 進位取り記数法で書いたときの各桁の和 S が B - 1 の倍数なら、n も B - 1 の倍数である

math

数年前に10進法の3の倍数の性質について証明したことがあったので、それを一般化してみました。

$B - 1$ が合成数なら、その素因数の倍数かどうかも各桁の和を見ることで確認できます*1。 記事の最後に、10進法の場合と16進法の場合を系として書いています。


定理 $B$ 進法で書かれた自然数 $n$ の各桁の和 $S$ が $B - 1$ の倍数なら、$n$ も $B - 1$ の倍数である。

証明 $n$ を $N$ 桁の数と仮定し証明する。$n$ の$B$ 進位取り記数法による表現は式 (1) である。

$$ n = \sum_{j=0}^{N-1} B^j d_j \tag{1} $$

$d_k$ は $k$ 桁目の数を表す。このとき $n$ の各桁の和 $S$ は次式で与えられる。

$$ S = \sum_{j=0}^{N-1} d_j \tag{2} $$

$S$ が $B-1$ の倍数であるとき $S = (B-1)a$ となる自然数 $a$ が存在するから、式 (2) より $n$ の $N-1$ 桁目の数は次のように書ける。

$$ d_{N-1} = (B - 1)a - \sum_{j=0}^{N-2} d_j \tag{3} $$

これを式 (1) に適用して式変形すると次式を得る。

$$ \begin{split} n &= B^{N-1} d_{N-1} + \sum_{j=0}^{N-2} B^j d_j \\ &= B^{N-1} \left\{ (B-1)a - \sum_{j=0}^{N-2} d_j \right\} + \sum_{j=0}^{N-2} B^j d_j \\ &= (B-1)B^{N-1}a - B^{N-1}\sum_{j=0}^{N-2} d_j + \sum_{j=0}^{N-2} B^j d_j \\ &= (B-1)B^{N-1}a - \sum_{j=0}^{N-2} (B^{N-1} - B^j) d_j \\ &= (B-1)B^{N-1}a - \sum_{j=0}^{N-2} (B^{N-1-j} - 1) B^j d_j \\ \end{split} \tag{4} $$

ここで、$(B^{N-1-j} - 1)$ は、B進法で表現すると $N-1-j-1$ 桁であり、すべての桁が $B-1$ なっているため、次式で表すことができる。

$$ B^{N-1-j} - 1 = (B-1) \sum_{k=0}^{N-1-j-1} B^{k} \tag{5} $$

これを式 (4) に適用して式変形を続けると、

$$ \begin{split} n &= (B-1)B^{N-1}a - \sum_{j=0}^{N-2} (B^{N-1-j} - 1) B^j d_j \\ &= (B-1)B^{N-1}a - \sum_{j=0}^{N-2} (B-1) \left\{ \sum_{k=0}^{N-1-j-1} B^{k} \right\} B^j d_j \\ &= (B-1)B^{N-1}a - (B-1) \sum_{j=0}^{N-2} \left\{ \sum_{k=0}^{N-1-j-1} B^{k} \right\} B^j d_j \\ &= (B-1) \left[ B^{N-1}a - \sum_{j=0}^{N-2} \left\{ \sum_{k=0}^{N-1-j-1} B^{k} \right\} B^j d_j \right] \\ \end{split} \tag{6} $$

このように $n$ が $B-1$ の倍数であることが分かる。

(証明終わり)


10進法で表現した場合の各桁の和が9の倍数になる任意の自然数は9の倍数である。

10進法で表現した場合の各桁の和が3の倍数になる任意の自然数は3の倍数である。

16進法で表現した場合の各桁の和が15の倍数になる任意の自然数は15の倍数である。

16進法で表現した場合の各桁の和が5の倍数になる任意の自然数は5の倍数である。

16進法で表現した場合の各桁の和が3の倍数になる任意の自然数は3の倍数である。

*1:素数 $p$ と $q$ で $B - 1 = pq$ と書ける場合、$S = pqa$ と書けることになるので。

JuliaTokyo #5 に参加した

julia

きのう JuliaTokyo #5 に参加した。おととい富山に日帰りで行く用事があって今回は発表できなかったので、次回は何か喋りたい。

今回も面白い発表が目白押しだった。hshindo さんによる Merlin.jl は、Chainer から乗り換える先として一考に値すると思う。この記事を書いてる時点でまだ10コミットしかないから、足りない部分を自分で実装して開発に貢献できる魅力もある。

私にとって今回一番の目玉だったのは、世界で唯一人プロレスリング上で Julia を書いた経験をお持ちの Julia 伝道師の bicycle1885 さんによる、Julia チューニングハンズオンだ。プロファイルをとって関数を最適化していく手順を一歩ずつ見せていただいたので本当に参考になった。

その証拠としてさっそく今日、typical_colors の実装をプロファイルをとりながら最適化して実行速度を半分以下できた

Julia の時代だ。

WEB+DB PRESS vol. 89 に深層学習の特集記事を書きました

10/24 発売の WEB+DB PRESS vol. 89 で『深層学習』というタイトルで特集記事を執筆させていただきました。

特集の概要

本特集は、機械学習に明るくないWEBエンジニアが深層学習へ入門する際のスタート地点になることを想定して執筆しました。

深層学習へつながる歴史、シンプルな構造のニューラルネットワーク、深層学習の困難さなどを、難しい数学を可能な限り使わずに解説しました。

さらに、実際にコードをいじって試せる題材として、GoogLeNet と waifu2x を採用し、Jupyter notebook 形式でサンプルコードをgithub 上で公開しています。mrkn/webdb_deep_learningをフォークして試してもらえると嬉しいです。

特集の構成

特集は5章構成になっています。

  1. ニューラルネットワーク入門
  2. [実践] ニューラルネットワーク
  3. 深層学習入門
  4. [実践] 深層学習
  5. waifu2x による画像の超解像

さいごに

WEB+DB PRESS vol. 89 は 10/24 発売です。よろしくお願いします。


JuliaTokyo #4 で画像の特徴色抽出について LT した

仕事で挑戦している画像の特徴色抽出について JuliaTokyo #4 で喋りました。 これ以上の高精度を追求するには、ピクセル毎に料理か否かをラベリングするくらいの意気込みが必要だろうなと思っていて、実際にそれに相当する事には取り組むつもりでいます。

とりあえず、第一歩として typical_colors.jl を本番環境のバッチで利用して、社内システムの利便性を向上させるところからやっていこうと思います。

この分野に詳しい方がもしこれを見ていましたら、私に連絡してください。弊社でランチを食べながら情報交換しましょう。

今日のスライドは以下になります。


分岐水栓

明日、食洗機が届く予定なので Panasonic のサイトで取り付け方を復習している。明日届くのにまだ準備をしていなかったのである。

食洗機の取り付けには分岐水栓なるものを取り付ける必要がある。 Panasonicこのページのフォームに水栓の型番を入力すると、購入すべき分岐水栓とその取り付けマニュアルを入手できるようになっている。親切。

うちの水栓の型番は SF-4420S。この水栓に対する分岐水栓は CB-SXF6 だった。ググってみると Amazon で売ってることが分かったので即購入。

取り付けマニュアルは PDF 形式で入手できる (例: CB-SXF6)。 取り付ける際にモーターレンチが必要なので、それも Amazon で即購入。