2020.03.22記 最近プログラムの講義をもっていないが、いつかやるときのためのネタとして覚え書き。中学入試の算数の問題はアルゴリズム的な問題が結構多いのだ。それにしても、プログラムをさせておいて、その数学的背景を語る講義をやる機会って来るのかな…

の偶奇についての話と同じ。(1) が持つ素因数の個数はである。(2) である。これは一般にまたは となることからわかる。(3) の等号成立はが任意のについて成立すること。 つまり、進数におけるの筆算において繰り上がりが生じないことが必要十分条件となる。(…

問題:のうち奇数はいくつあるか解答:(1) が奇数になる必要十分条件は2進法でのの筆算において繰り上がりが生じないことである。(2) つまり、を2進数で表示したときに登場する「1」をとみる(の桁)か、とみる(の桁)かのいずれかである。(3) よって pow( 2 , bi…

では、ある自然数の2進数表示における1の個数を求めるにはどうすれば良いかということになるが、(1) のの桁が1かどうかの判定は 「を2で割った余りを求める」 b % 2または、1とビット毎の AND をとる b & 1とすれば良い。(2) のの桁が1かどうかの判定は 「を…

結論から言えば、ビット演算子を用いて bitCount( n ^ r ^ (n-r) )となる。ここで bitCount は引数の2進数表示における1の個数である。「二項係数の偶奇」という記事で説明したことから直ちに2で割れる回数は が成り立つ場所の個数に一致することがわかる。 …

の偶奇について考えたのは、2013年頃の話で、当時の結論は、の値はビット演算子を用いて n == ( r | (n - r) ) となる。というものだ。例えば、は偶数だが、 ( 10 | 11 ) = 11 は101ではないので、命題は偽となり、値は0となる。または奇数だが、 ( 10 | 100…

パスカルの三角形の奇数部分を塗り潰すとシェルピンスキーのギャスケットが登場することは良く知られている。そこで二項係数が奇数か偶数か判定する方法について考えたことがある。 もちろん、定義通り二項係数を求めようとすると、C言語の int では 13の階…

では、タッパーの自己言及式を導いてみよう。 縦横の長方形のバイナリ画像を縦に1列に並べて2進数で表現したものをとする。からの値を復元することを考える。それは、の位の数字を求めれば良いので、 つまり となる。しかし、与えるのはではなく座標なので、…

タッパーの自己言及式 http://www.dgp.toronto.edu/people/mooncake/papers/SIGGRAPH2001_Tupper.pdf とはののグラフを描くとこの式自体が表示されるというものだ。ここでは以下の最大の整数で日本ではガウス記号と同じ。はをで割ったあまりのこと。 この式…

改行がCRLFの場合は sed '/^$/d' 1.txt > 2.txt ではなく sed '/^\r$/d' 1.txt > 2.txt とすれば良いのか。勉強になった。

個人的メモ sed "N; s/\(.*\)\n\(.*\)/\2\\n\1/g" 1.txt > 2.txt とりあえず動いたから良しとしよう。 さらに、空白行の挿入 sed "N; s/\(.*\)\n\(.*\)/\2\\n\1\\n/g" 1.txt > 2.txt まぁまぁ動いた。