{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a83c9f28",
   "metadata": {},
   "source": [
    "# オイラーのφ関数\n",
    "\n",
    "オイラーのφ関数 $\\varphi(n)$ は、$\\{1,\\ldots,n\\}$ のうち $n$ と\n",
    "互いに素な整数の個数を表します。$n$ の相異なる素因数を\n",
    "$p_1,\\ldots,p_k$ とすると、\n",
    "\n",
    "$$\n",
    "\\varphi(n)\n",
    "  =n\\prod_{j=1}^k\\left(1-\\frac1{p_j}\\right).\n",
    "$$\n",
    "\n",
    "この積公式から、素因数分解を使うのが自然な計算方法だと分かります。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "531ad604",
   "metadata": {},
   "source": [
    "## 型付きの直接的な定義\n",
    "\n",
    "素因数分解には同じ素数が繰り返し現れることがあるため、積を取る前に\n",
    "unique で重複を取り除きます。最終結果は整数ですが、途中の各因子も厳密に\n",
    "扱えるよう、有理数演算を用います。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "2d589a12",
   "metadata": {},
   "outputs": [],
   "source": [
    "def φ (n : Integer) : Rational :=\n",
    "  n * product (map (\\p -> 1 - 1 / p) (unique (pF n)))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e37f87a3",
   "metadata": {},
   "source": [
    "## 一つの素因数分解を確認する\n",
    "\n",
    "$36=2^2\\,3^2$ なので、相異なる素数 $2$ と $3$ だけが積に現れます。\n",
    "\n",
    "$$\n",
    "\\varphi(36)=36(1-1/2)(1-1/3)=12.\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d6c6ef99",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$(\\{2, 2, 3, 3\\}, \\{2, 3\\}, 12)$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(pF 36, unique (pF 36), φ 36)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f354a046",
   "metadata": {},
   "source": [
    "## 最初の20個の値\n",
    "\n",
    "各 $n$ についてφ関数の値と完全な素因数分解を並べて表示すると、素数や\n",
    "素数の冪における値の変化を比較しやすくなります。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "04f502e5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$\\{(1, 1, \\{\\}), (2, 1, \\{2\\}), (3, 2, \\{3\\}), (4, 2, \\{2, 2\\}), (5, 4, \\{5\\}), (6, 2, \\{2, 3\\}), (7, 6, \\{7\\}), (8, 4, \\{2, 2, 2\\}), (9, 6, \\{3, 3\\}), (10, 4, \\{2, 5\\}), (11, 10, \\{11\\}), (12, 4, \\{2, 2, 3\\}), (13, 12, \\{13\\}), (14, 6, \\{2, 7\\}), (15, 8, \\{3, 5\\}), (16, 8, \\{2, 2, 2, 2\\}), (17, 16, \\{17\\}), (18, 6, \\{2, 3, 3\\}), (19, 18, \\{19\\}), (20, 8, \\{2, 2, 5\\})\\}$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "map (\\n -> (n, φ n, pF n)) (take 20 nats)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d570451f",
   "metadata": {},
   "source": [
    "## 約数和に関する恒等式\n",
    "\n",
    "すべての正の整数について、次の恒等式が成り立ちます。\n",
    "\n",
    "$$\n",
    "\\sum_{d\\mid n}\\varphi(d)=n.\n",
    "$$\n",
    "\n",
    "約数であるという条件は通常のフィルターで表現でき、先ほどと同じ例を使って\n",
    "この恒等式を検証できます。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "480e7585",
   "metadata": {},
   "outputs": [],
   "source": [
    "def divisorsOf (n : Integer) : [Integer] :=\n",
    "  filter (\\d -> divisor n d) [1..n]\n",
    "\n",
    "def totientDivisorSum (n : Integer) : Rational :=\n",
    "  sum (map φ (divisorsOf n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "72ce3120",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "$(\\{1, 2, 3, 4, 6, 9, 12, 18, 36\\}, 36)$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(divisorsOf 36, totientDivisorSum 36)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8de1aa1d",
   "metadata": {},
   "source": [
    "## まとめ\n",
    "\n",
    "素因数分解、重複除去、写像、積を直接組み合わせることで、オイラーの積公式を\n",
    "厳密な一行の定義として表せます。約数和の検算からは、同じ関数がより深い\n",
    "数論的恒等式にも現れることが分かります。\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Egison",
   "language": "egison",
   "name": "egison"
  },
  "language_info": {
   "codemirror_mode": "egison",
   "file_extension": ".egi",
   "mimetype": "text/x-egison",
   "name": "egison"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}