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

問題

以下の計算式が成り立つようにA,B,C,D,E,F,Gを求める。

解答への道(ヒント)

double だと精度が不足しているので，単純にプログラムで求めることは出来ない。以下のようにして候補値を出力しWindowsの電卓で求めるか。

#include "puzutl.h"

int main( int argc, cstring argv[])
{
  int cnt = 0;
  for( int a=1; a< 1000; a++) {
    for( int b=1; b< 10000; b++) {
      double d = (double)a/(double)b;
      if( d >= 0.256128 && d <= 0.256129) { cnt++; ps( "%d/%d = %.20g\n", a, b, d);}
    }
  }
  ps( "cnt:%d\n", cnt);
  return    0;
}

それとも以下のようなシェルを書いて気長に待つか。

#!/bin/sh
a=1
while [ $a -lt 1000 ]
do
  b=1
  while [ $b -lt 10000 ]
  do
    dc -e "${a}000000000000000000000000000000 $b / p" |grep -q 256128064032016008004002001
    if [ $? -eq 0 ] ; then echo $a / $b ; fi ;
    b=$(expr 1 + $b)
  done
  a=$(expr 1 + $a)
done
exit 0

上のシェルは余りに遅いので，もう少し数値を絞り込んだシェルに変更する。しかも途中で 49 / 3998 を出力していた。49/3998 をWindows の電卓で計算してみると，1.22561280640320160080040020010e-2 と表示される。下のシェルは絞り込んでいるから 49/3998 は表示されない。

#!/bin/sh
date
a=1
while [ $a -lt 1000 ]
do
  b=$(expr 1000 '*' $a / 257)
  bmax=$(expr 1000 '*' $a / 256)
  while [ $b -le $bmax ]
  do
    dc -e "${a}0000000000000000000000000000000 $b / p" |grep -q 256128064032016008004002001
    if [ $? -eq 0 ] ; then echo $a / $b ; fi ;
    b=$(expr 1 + $b)
  done
  a=$(expr 1 + $a)
done
date
exit 0

それでも Celeron 1.3GHz で5分くらい掛かった。

ちなみに dc はUNIX用の高精度の電卓。小数点以下はdouble位の精度で打ちきりなので，下駄を履かせて計算するようにした。

私の利用しているUNIX機(FreeBSD)にはman -k calc としたら以下の電卓が出てきた。最初calcで作ったけど，Linuxにはcalcが付いていないようなのでdcで作成した。

calc - arbitrary precision calculator
dc - an arbitrary precision calculator
bc - An arbitrary precision calculator language