朝日新聞2005年11月11日のパズル横丁問題

問題

0と1を11個ずつ使って22で割り切れるような22桁の整数を作る。

解答への道(ヒント)

22桁かー。辛いな。私の使えるコンパイル環境に128ビット整数は無いので，以下のようにdcを使って計算するコードを出力する。

#include "puzutl.h"

int bitcnt( int i)
{
  return 1の数;
}

cstring conv( int i) 
{
  static char buf[128];
  …2進数を文字列に変換する…
  return buf;
}

int main( int argc, cstring argv[])
{
  for( int i=0x200000; i<= 0x3FFFFF; i+=2) {
    if( (i&1) == 0 && bitcnt(i) == 11) { // 22で割れるということは2でも割れる,ビットがONは11個
      cstring s = conv(i);
      ps( "if [ `dc -e \"%s 22 %% p\"` -eq 0 ] ; then echo %s / 22 = `dc -e \"%s 22 / p\"`; fi\n", s, s);
    }
  }
  return 0;
}

実行すると，以下のような出力を得る。全部で184756行ある。

if [ `dc -e "1000000000011111111110 22 % p"` -eq 0 ] ; then echo 1000000000011111111110 / 22 = `dc -e "1000000000011111111110 22 / p"`; fi
if [ `dc -e "1000000000101111111110 22 % p"` -eq 0 ] ; then echo 1000000000101111111110 / 22 = `dc -e "1000000000101111111110 22 / p"`; fi
if [ `dc -e "1000000000110111111110 22 % p"` -eq 0 ] ; then echo 1000000000110111111110 / 22 = `dc -e "1000000000110111111110 22 / p"`; fi
if [ `dc -e "1000000000111011111110 22 % p"` -eq 0 ] ; then echo 1000000000111011111110 / 22 = `dc -e "1000000000111011111110 22 / p"`; fi
………以下略………

この出力をUNIXに持っていって実行する。

結果は1件出力されました。

解速度

シェルプログラムを出力する方はPentiumIII500MHzで約8秒。

シェルプログラムはCeleron1.3GHzで約1時間。