720の約数の組 /「算数にチャレンジ!!」第1105問

問題概略
素因数分解して指数に注目する
おまけ：プログラムの速度比較
- 愚直解法
- 指数に注目

問題概略

次のルールに従って2つの自然数 $a$ , $b$ の組を作ります。

$a>b$

$a$ , $b$ は 720 の約数

$a$ と $b$ は互いに素

この条件をみたす $(a,\, b)$ の個数を求めてください。
http://www.sansu.org/used-html/index1105.html

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

素因数分解して指数に注目する

$720=2^4\cdot 3^2\cdot 5$ より $a=2^x\cdot 3^y\cdot 5^z$ , $b=2^X\cdot 3^Y\cdot 5^Z$ とおけます。

これらが互いに素な条件を考えます。

$x$ と $X$ の少なくとも一方は 0
$y$ と $Y$ の少なくとも一方は 0
$z$ と $Z$ の少なくとも一方は 0
「 $x$ ～ $Z$ がすべて 0」のとき $a=b=1$ になるので不適

$(x,\, X)$ は次の 9 通りあります。

$(0,\, 0),\, (0,\, 1\text{～}4),\, (1\text{～}4,\, 0)$

一般に素因数分解の指数が $k$ なら，その素数に対する $a$ と $b$ の指数のペアは $2k+1$ 通りです。
$(y,\, Y)$ は $2\cdot 2+1=5$ 通りあって， $(z,\, Z)$ は $2\cdot 1+1=3$ 通りあります。

これらの積から「指数がすべて 0」の 1 通りを除くと

$9\cdot 5\cdot 3-1=\text{134 通り}$

この中には $a>b$ のものと $a< b$ のものが同じ個数ずつ含まれています。
2 で割った 67 組が答えです。

おまけ：プログラムの速度比較

愚直解法

Divisors@720, {2}] で 720 の約数の組を作って，CoprimeQ で互いに素なものを抽出すると $5.6\times 10^{-4}$ 秒。

  In[]:= AbsoluteTiming[
    lst = Subsets[Divisors@720, {2}];
    ans = Length@Select[lst, CoprimeQ[#[[1]], #[[2]]] &]]
   
  Out[]= {0.0005651, 67}

指数に注目

素因数分解して指数に注目する解法だと $6.7\times 10^{-5}$ 秒。

FactorInteger で $n$ を因数分解して素因数と指数のリストを作る。720 の場合， $\left\{\left\{2,\, 4\right\},\, \left\{3,\, 2\right\},\, \left\{5,\, 1\right\}\right\}$ を得る
指数 $k$ を取り出して $2k+1$ に変換
$2k+1$ などの積から 1 を引いて 2 で割ったものが答え

  In[]:= AbsoluteTiming[
    lst = FactorInteger@720;
    f[{x_, y_}] := 2 y + 1;
    g[lst_] := (Times @@ lst - 1)/2;
    ans = g@(f /@ lst)]
   
  Out[]= {0.0000674, 67}

variee.hatenablog.com