2_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "367de800-7155-4024-aa11-54d947de9924",
   "metadata": {},
   "source": [
    "## Chapter 2\n",
    "\n",
    "\n",
    "### Ground rules\n",
    "\n",
    "\n",
    "- $n$ is a positive integer with $k$ distinct prime factors: $n = \\prod_{i=1}^{k}{p_i}^{a_i}$.\n",
    "\n",
    "\n",
    "- $\\mu(n)$ is the Möbius function: $\\mu(1) = 1$ and for $n > 1$: $\\mu = 0$ when $n$ has a squared prime in its factorization, otherwise $\\mu(n) = -1^{k}$ for $n$ having $k$ distinct prime factors.\n",
    "\n",
    "\n",
    "- $\\mu * u = I$ or in more familiar form: The sum over divisors of $n$ of $\\mu(d)$ is zero for $n>1$. \n",
    "\n",
    "\n",
    "- $\\varphi(a)$ is the Euler totient function, the count of relative primes less than or equal to $a$. See the chapter 2 examples for $\\varphi$'s relationship to DFT(gcd). \n",
    "\n",
    "\n",
    "- $\\nu(n)$ is the number of unique prime factors of $n$.\n",
    "\n",
    "\n",
    "- 'Multiplicative' applies to breaking out $f(m \\cdot n) = f(m) \\cdot f(n)$ when $(m, n) = 1$. *Completely* multiplicative are the same without the $gcd=1$ condition.\n",
    "\n",
    "\n",
    "- $\\varphi$ is multiplicative; so $\\varphi(a \\cdot b) = \\varphi(a) \\cdot \\varphi(b)$ when $(a, b) = 1$.\n",
    "\n",
    "\n",
    "- The Dirichlet product of two multiplicative functions is also multiplicative.\n",
    "\n",
    "\n",
    "- $I(n)$ is the identity function $\\{1, 0, 0, 0, \\dots \\}$. It is sometimes expressed as $\\lfloor \\frac{1}{n} \\rfloor$.\n",
    "\n",
    "\n",
    "- $u(n)$ is the unit function equal to $1$ for all $n$. It is the Dirichlet inverse of $\\mu(n)$.\n",
    "\n",
    "\n",
    "- $N(n) = n$ and more generally $N^\\alpha(n)$ is the power function equal to $n^\\alpha$: $\\alpha$ is a fixed real or complex number. The power function is completely multiplicative.\n",
    "\n",
    "\n",
    "- $\\varphi = \\mu * N$\n",
    "\n",
    "\n",
    "- $d(n)$ is the number of positive divisors of $n$. It is multiplicative.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d49036b-b3a3-40a4-a11d-86bca9bec91c",
   "metadata": {},
   "source": [
    "### Recapitulating the proof of theorem 2.4\n",
    "\n",
    "\n",
    "This proof contains an interesting view of product expansion in a combinatoric sense. \n",
    "Before starting on the theorem I quote the prior theorem 2.3 connecting the totient to \n",
    "the Mobius function:\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\textrm{Theorem 2.3: }\\;\\;\\; \\varphi(n) = \\sum_{d|n}\\mu(d) \\frac{n}{d} = n \\sum_{d|n} \\frac{\\mu(d)}{d} = \\mu * N\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "Now to state theorem 2.4: For $n \\ge 1$\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\varphi(n) = n \\prod_{p|n} \\left( {1 - \\frac{1}{p}} \\right)\n",
    "\\end{align}$.\n",
    "\n",
    "\n",
    "This is understood as a product over unique prime factors $p$.\n",
    "When $n=1$ the right side is taken to be $1$ in the absence of prime terms. \n",
    "Checking for $n=13$ we have $13 \\cdot (1-1/13) = 12$: correct.\n",
    "\n",
    "\n",
    "Proof: Strategy is take the right-hand $\\prod$ expression and maneuver it to look like $\\varphi(n)$.\n",
    "\n",
    "\n",
    "First step: Ignoring the factor of $n$ until later, write the right-hand product in a 'counting all combinations of primes' fashion:\n",
    "\n",
    "$\\begin{align}\n",
    "\\prod_{p|n} \\left( 1 - \\frac{1}{p} \\right) & = \\left( 1 - \\frac{1}{p_1} \\right) \\left( 1 - \\frac{1}{p_2} \\right) \n",
    "\\cdots \\left( 1 - \\frac{1}{p_k} \\right) \\\\\n",
    "& = 1 - \\frac{1}{p_1} - \\frac{1}{p_2} - \\cdots - \\frac{1}{p_k} + \\frac{1}{p_1 p_2} + \\frac{1}{p_1 p_3} + \\cdots + \\frac{1}{p_{k-1} p_k}\n",
    "- \\frac{1}{p_1 p_2 p_3} - \\cdots + \\frac{{-1}^k}{p_1 p_2 \\cdots p_k}\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "The alternating signs in this sequence of fractions mirror the Mobius function: \n",
    "Each numerator is $\\mu(\\textrm{denominator})$; and powers of 2 or more for these\n",
    "prime factors do not appear.\n",
    "\n",
    "\n",
    "Rewriting with abstract indices to indicate 'all possible combinations': \n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\prod_{p|n} \\left( {1 - \\frac{1}{p} } \\right) & =\n",
    "1 - \\sum \\frac{1}{p_i} + \\sum \\frac{1}{p_i \\cdot p_j} - \\sum \\frac{1}{p_i \\cdot p_j \\cdot p_k} \n",
    "+ \\cdots + \\frac{{(-1)}^k}{p_1 \\cdot p_2 \\cdots p_k}\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "Here is the Tommy-esque twist: As it stands the expansion as a sum of fractions involves all\n",
    "possible combinations of first powers of the prime factors of $n$.  Suppose we want the sum to extend\n",
    "over all divisors of $n$: This is possible provided any fractions with primes of power $2+$ in the\n",
    "denominator have a numerator of zero. This is handed us by the Mobius introduced as the numerator\n",
    "of each fraction evaluated for the corresponding denominator (i.e. divisor $d$). The \n",
    "expression for the original product is now a sum over all divisors $d$ of $n$: \n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\prod_{p|n} \\left( {1 - \\frac{1}{p} } \\right) & = \\sum_{d|n} \\frac{\\mu(d)}{d} \\;\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "Multiply by $n$ and make use of the result of theorem 2.3: The totient is the Dirichlet product of the Mobius function \n",
    "and the identity function $N(n) = n$:\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "n \\prod_{p|n} \\left( {1 - \\frac{1}{p} } \\right) = n \\sum_{d|n} \\frac{\\mu(d)}{d} = \\sum_{d|n} \\mu(d) \\frac{n}{d} = \\mu * N = \\varphi(n) \\;\\;\\;\\;\\;\\;\\;\n",
    "\\end{align}$&#x2610;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aca3575b-4955-407c-9bd8-a15bb50e6640",
   "metadata": {},
   "source": [
    "#### 2.1 Find $n$ for which (a) $\\varphi(n) = \\frac{n}{2}$; (b) $\\varphi(n) = \\varphi(2n)$; (c) $\\varphi(n) = 12$.\n",
    "\n",
    "\n",
    "**(a)** $\\varphi(n) = \\frac{n}{2}$ \n",
    "\n",
    "\n",
    "For $n=1$ we have \n",
    "$\\varphi = 1$ (not a solution) and $\\varphi(2) = 1$ (a first solution); \n",
    "so let's proceed to $n > 2$, the regime where $\\varphi(n)$ is always even \n",
    "to find more $\\varphi(n) = \\frac{n}{2}$. \n",
    "Combine these to conclude $n$ is a multiple of $4$\n",
    "so taking $\\alpha > 1$ we have\n",
    "\n",
    "\n",
    "$n = 2^{\\alpha} \\cdot \\prod_{p \\; odd}{p_i}^{a_i}$\n",
    "\n",
    "\n",
    "Observing $(2^\\alpha, \\Pi) = 1$ where $\\varphi(n)$ is multiplicative gives us:\n",
    "\n",
    "\n",
    "$\\varphi(n) = \\varphi(2^\\alpha \\cdot \\Pi)$\n",
    "\n",
    "\n",
    "$\\varphi(n) = \\varphi(2^\\alpha) \\cdot \\varphi(\\Pi)$\n",
    "\n",
    "\n",
    "The value of $\\varphi(2^\\alpha)$ is the number of odd values less than $2^\\alpha$:\n",
    "\n",
    "\n",
    "$\\varphi(n) = 2^{\\alpha-1} \\cdot \\varphi(\\Pi) = \\frac{n}{2}$\n",
    "\n",
    "\n",
    "Powers of two are relatively prime to the odd numbers so $\\varphi(2^d)=2^{d-1}.$\n",
    "Now to use $\\varphi(n) = n$ only for $n=1$:\n",
    "\n",
    "\n",
    "$2^{\\alpha-1} \\cdot \\varphi(\\Pi) = 2^{\\alpha-1} \\cdot \\Pi \\implies \\Pi = 1$\n",
    "\n",
    "\n",
    "Consequently $n = 2^\\alpha = \\{ 2, 4, 8, \\dots \\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e51c4793-9fae-4c53-a0e9-5f5ba4deac29",
   "metadata": {},
   "source": [
    "**(b) $\\varphi(n) = \\varphi(2n)$** \n",
    "\n",
    "\n",
    "Useful observation: $\\varphi(2^s) \\ne \\varphi(2^{s+1})$ excepting the one case $s=0$.\n",
    "\n",
    "\n",
    "Write $n$ as a product of (a power of 2) times (a residual odd number $r$).\n",
    "Here $r$ is **either** $1$ **or** a residual product of odd primes raised to\n",
    "various powers). $n = 2^s \\cdot r$.\n",
    "\n",
    "\n",
    "Write $2n$ similarly: $2n = 2^{s+1} \\cdot r$\n",
    "\n",
    "\n",
    "Use the multiplicative nature of $\\varphi$ to state the condition on $n$: \n",
    "\n",
    "\n",
    "$\\begin{align}\\varphi(2^s) \\cdot \\varphi(r) = \n",
    "\\varphi(2^{s+1}) \\cdot \\varphi(r)\\end{align}$\n",
    "\n",
    "\n",
    "This will be true for *any* odd $r$ so long as $s$ has value $0$\n",
    "so the solution is $n = \\{1, 3, 5, 7, 9, \\dots\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aaae54a7-64cd-42bf-acd0-81cb66500ab6",
   "metadata": {},
   "source": [
    "**(c)** $\\varphi(n)=12$\n",
    "\n",
    "\n",
    "This innocuous problem caused me considerable emotional distress.\n",
    "It is easy enough to see that $n=13$ is a solution; but it is more\n",
    "arduous to conclusively produce all possible solutions. \n",
    "\n",
    "\n",
    "Citing two *product* forms of the totient.\n",
    "\n",
    "\n",
    "Equation 1:\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\varphi(n) = 12 = 2 \\cdot 2 \\cdot 3 = \\varphi(n) = n \\prod_{p|n} \\left( 1 - \\frac{1}{p} \\right) = n \\prod_{p|n} \\frac{p_i-1}{p_i}\n",
    "\\end{align}$ \n",
    "\n",
    "\n",
    "using theorem 2.4 (see section above). Doing a quick check: $n = 13$ works as expected.\n",
    "\n",
    "\n",
    "In the rightmost expression in equation 1 the entirety of the denominator product cancels factors of the \n",
    "leading $n$ leaving a residual $R \\ge 1$: \n",
    "\n",
    "\n",
    "$\\begin{align}12 = R \\cdot \\prod_{p|n}(p_i-1)\\end{align}$.\n",
    "\n",
    "\n",
    "Equation 2:\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\varphi(n) = 12 = 2 \\cdot 2 \\cdot 3 = \\varphi(n) = \\prod_{p|n} \\bigl( p_i^{\\alpha_i} - p_i^{\\alpha_i - 1} \\bigr)\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "which also works as expected for $n=13$. Equation 2 is obtained from equation 1 by writing $n$\n",
    "as the product of primes raised to powers; and then distributing these factors across the \n",
    "$(1 - \\frac{1}{p_i})$ terms in the product: $p_i^{\\alpha_i}*(1-\\frac{1}{p_i}) = p_i^{\\alpha_i} - p_i^{\\alpha_i-1}$.\n",
    "\n",
    "\n",
    "In this narrative $n$ has $k$ distinct prime factors. If $k = 4$ then equation (1) implies\n",
    "the end result 12 has (at least) 3 even factors due to $p_i-1$ (not possible) so $k = 1, 2 \\textrm{ or } 3$.\n",
    "For $k=3$ we can write $n = p^\\alpha \\cdot q^\\beta \\cdot r^\\gamma$ ordered $p < q < r$. \n",
    "Each distinct prime contributes a factor to the product given in equation 2. \n",
    "\n",
    "\n",
    "For $k=1$ we have $12 = p^\\alpha - p^{\\alpha-1}$\n",
    "\n",
    "\n",
    "For $k=2$ we have $12 = (p^\\alpha - p^{\\alpha-1})\\cdot(q^\\beta - q^{\\beta-1})$\n",
    "\n",
    "\n",
    "For $k=3$ this extends once more to $12 = (p^\\alpha - p^{\\alpha-1})\\cdot(q^\\beta - q^{\\beta-1})\\cdot(r^\\gamma - r^{\\gamma-1})$\n",
    "\n",
    "\n",
    "These constraints suggest a table to find all $n$ for which $\\varphi(n) = 12$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b45a0fe9-633c-4419-a830-eab97c5fa495",
   "metadata": {},
   "source": [
    "|  |  p:      | 2 | 3 | 5 | 7 | 11 | 13 |\n",
    "| :---| ---:| ---:| ---:| ---:| ---:| ---:| ---:|\n",
    "| **$\\alpha$:** | **1** $\\;$ | 1 | 2 | 4 | 6 | &#x1f78c;  | 12\n",
    "| | **2** $\\;$ | 2 | 6 |  &#x1f78c; | &#x1f78c;  |  &#x1f78c; |   &#x1f78c; |\n",
    "| | **3** $\\;$ | 4 |  &#x1f78c; |  &#x1f78c; |  &#x1f78c; | &#x1f78c;  |   &#x1f78c; |\n",
    "\n",
    "\n",
    "The column headers of this table are candidate prime values for $p$, $q$ or $r$.\n",
    "Row labels are candidate exponent values for exponents $\\alpha$, $\\beta$ or $\\gamma$.\n",
    "Table values are resulting $\\bigl( p^{\\alpha} - p^{\\alpha - 1} \\bigr)$ that divide the \n",
    "totient value $12$.\n",
    "\n",
    "\n",
    "Suppose $k=1$: Then $p=13 \\textrm{, } \\alpha=1$ is the only solution. \n",
    "\n",
    "\n",
    "Suppose $k=2$: The strategy is to choose pairs of numbers from the above table\n",
    "whose product is $12$ and from these pairs infer $p$, $\\alpha$, $q$ and $\\beta$.\n",
    "We can begin with the minimum values $p=2$ and $\\alpha = 1$ to get a \n",
    "$p$-term of $1$ in the product. Chosing $q=13$ and $\\beta = 1$ gives the desired \n",
    "totient $1 \\cdot 12 = 12$; so $n=2 \\cdot 13 = 26$ is a solution. This is consistent with \n",
    "$\\varphi(2) = 1$ and $\\varphi$ is multiplicative. \n",
    "\n",
    "\n",
    "All of the table pairs for $k=2$ are easily read off: \n",
    "\n",
    "- $(1 \\cdot 12)$ corresponding to $2^1 \\cdot 13^1 = 26$\n",
    "- $(2 \\cdot 6)$ corresponding to $2^2 \\cdot 3^2 = 36$\n",
    "- $(2 \\cdot 6)$ corresponding to $2^2 \\cdot 7^1 = 28$\n",
    "- $(2 \\cdot 6)$ corresponding to $3^1 \\cdot 7^1 = 21$\n",
    "\n",
    "\n",
    "Finally there is one $k=3$ combination: $1 \\cdot 2 \\cdot 6$ corresponding to $2^1 \\cdot 3^1 \\cdot 7^1 = 42$.\n",
    "The exhaustive set of values for which $\\varphi(n) = 12$ is consequently $\\{13, 26, 36, 28, 21, 42 \\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48feed67-0324-4f38-8915-24eb6c5f3270",
   "metadata": {},
   "source": [
    "#### 2.2 Complete: Prove or find counterexamples $\\otimes$ for...\n",
    "\n",
    "\n",
    "(a) Show $(m,n) = 1 \\implies (\\varphi(m), \\varphi(n))=1$. \n",
    "Choosing $m=3,\\;n=4$ both give $\\varphi = 2$, a counterexample. $\\otimes$\n",
    "\n",
    "\n",
    "(b) Show $n \\; composite \\; \\implies (n, \\varphi(n)) > 1$.\n",
    "Choose $n = 15$ and check: $(15, 8) = 1$, a counterexample. $\\otimes$\n",
    "\n",
    "\n",
    "(c) If the same primes divide $m$ and $n$ then $n\\cdot\\varphi(m) = m\\cdot\\varphi(n)$.\n",
    "\n",
    "\n",
    "$\\frac{\\varphi(m)}{m}=\\prod_{p|m}{1-p^{-1}}$. Since all $p$ that divide $m$ also divide $n$\n",
    "the product on the right is also equal to $\\frac{\\varphi(n)}{n}$.\n",
    "\n",
    "\n",
    "This part (c) is very concise so I will expand a little bit. Writing the product form of \n",
    "the totient function $\\varphi(s)$ introduces a factor of $s$; so divide both sides\n",
    "by $s$ to get $\\varphi(s)/s$ on one side and the product on the other. Here\n",
    "this product will be identical for two distinct numbers $m$ and $n$ that share the same\n",
    "set of prime factors; so their totient-to-self ratios are equal.  $\\;$ &#x2610;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "baf52c7d-9457-4753-b38a-c5ee5261a3d9",
   "metadata": {},
   "source": [
    "#### 2.3 Complete: Show that $\\frac{n}{\\varphi(n)}=\\sum_{d|n}\\frac{\\mu^2(d)}{\\varphi(d)}$\n",
    "\n",
    "\n",
    "This problem is fairly quick and very cool. It begins with a useful observation\n",
    "from the rules of multiplicative functions, that $f * g$ is multiplicative if\n",
    "both $f$ and $g$ are (**Theorem 2.15**). \n",
    "Since the problem includes a Dirichlet product-like element,\n",
    "$\\sum_{d|n}\\frac{\\mu^2(d)}{\\varphi(d)}$, the insight is to invoke $u(n)=1$\n",
    "in $\\frac{\\mu^2}{\\varphi}*u$. \n",
    "The composite function\n",
    "$\\frac{\\mu^2}{\\varphi}$ is constructed from multiplicative functions \n",
    "$\\mu$ and $\\varphi$. This is all a bit imprecise; see the remarks\n",
    "below the solution. Thematically the idea is to support the decomposition\n",
    "of $n$ into its set of divisors by means of the $k$ primes that divide $n$.\n",
    "\n",
    "\n",
    "Plan: Operate on the right side of the above expression.\n",
    "Two points are needed: First the usual prime decomposition of $n$\n",
    "in terms of exponents $a_i > 0$; and second the consequent expression\n",
    "for building out all divisors of $n$ as a product of sums:\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "{\n",
    "\\sum_{d|n}\\frac{\\mu^2(d)}{\\varphi(d)} = \n",
    "\\frac{\\mu^2(n)}{\\varphi(n)} * u(n) = \n",
    "\\prod_{i=1}^k \\Bigl( \\sum_{j=0}^{a_i} \n",
    "\\frac{\\mu^2(p_{i}^{j})}{\\varphi(p_{i}^{j})} \\Bigr)\n",
    "}\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "From here we can make use of features of $\\mu$ and $\\varphi$.\n",
    "First *inside the sum* the function $\\mu^2(q)$ has value \n",
    "$1$ when $q$ is either $1$ or a prime, \n",
    "and zero otherwise. Second, $\\varphi(1)=1$ and $\\varphi(p)=p-1$.\n",
    "As a result the summation over powers of the prime factor $p_i$\n",
    "simplifies into just the $j=0$ and $j=1$ cases:\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "{\n",
    "\\sum_{d|n}\\frac{\\mu^2(d)}{\\varphi(d)} = \n",
    "\\prod_{i=1}^k \\Bigl( 1 + \\frac{1}{p_i-1} \\Bigr) = \n",
    "\\prod_{i=1}^k \\Bigl( \\frac{p_i}{p_i-1} \\Bigr) = \n",
    "\\prod_{p|n} \\frac{1}{1-p^{-1}} =\n",
    "\\frac{n}{\\varphi(n)}.\n",
    "}\n",
    "\\end{align}\n",
    "$ \n",
    "\n",
    "\n",
    "The last step is from the product form of the totient function; and there we are. $\\;$ &#x2610;\n",
    "\n",
    "\n",
    "***Further elaboration:*** At many points in chapters 1 & 2 the problems \n",
    "depend on some form of \"multiply by 1\". In this arithmetic function space\n",
    "the idea of $1$ is present in two forms *prima facia*: The identity function\n",
    "$I(n) = \\bigl[ \\frac{1}{n} \\bigr]$ and the unit function $u(n)=1$. In this case \n",
    "the latter is invoked in Chip's solution sort of 'in passing' for the sake\n",
    "of the subsequent algebraic manipulation of $\\frac{\\mu^2}{\\varphi}$.\n",
    "\n",
    "\n",
    "I think the key signpost here is simply the presence of $\\sum_{d|n}$\n",
    "invoking the Dirichlet product. The real utility, the real value of the\n",
    "problem, is in the decomposition of $d|n$ into products of sums of\n",
    "powers of primes where $(p_a, p_b)=1$ gives us the necessary running room \n",
    "in the context of multiplicative functions. To put that in reverse order:\n",
    "The condition of being a multiplicative function gives us decomposition\n",
    "of functions of prime products into products of functions of primes.\n",
    "\n",
    "\n",
    "Finally to beat this to pieces one more time: There is an important \n",
    "property in the text concerning the decomposition of the totient of a product\n",
    "of two numbers $m$ and $n$ (see **Theorem 2.5 b)** and **c)**). This\n",
    "is that $\\varphi(m \\cdot n) = \\varphi(m) \\cdot \\varphi(n) \n",
    "\\textrm{ when } (m, n) = 1$. This resonates with the definition of \n",
    "multiplicative functions."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c11624d3-dbd2-42dd-be13-7a9e2f518f7e",
   "metadata": {},
   "source": [
    "#### 2.4 Complete: Show that $\\varphi(n) > \\frac{n}{6} \\; \\forall \\; n $ with $k \\le 8$ prime factors.\n",
    "\n",
    "\n",
    "This is an example of proof by calculation.\n",
    "\n",
    "\n",
    "Taking $\\varphi(n) = n \\cdot \\prod_{p|n}\\frac{p-1}{p}$ the goal is to show the\n",
    "product $\\prod < \\frac{1}{6}$. Calculate $\\prod$ for\n",
    "the first eight primes: $\\{\\frac{1}{2} \\cdot \\frac{2}{3} \\cdot \\cdots \\cdot \\frac{18}{19}\\}$.\n",
    "The result is a number greater than $1/6$. Choosing any other set of eight (larger)\n",
    "primes results in factors *closer* to 1, yielding a bigger product. Likewise choosing\n",
    "numbers with fewer than eight unique prime factors results in a larger resulting \n",
    "product: There are fewer factors where each is less than one. In both cases, therefore,\n",
    "the product above is a lower bound.$\\;\\;$ &#x2610;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7cd50489-39e9-4dbb-b5f3-312bd43f3cea",
   "metadata": {},
   "source": [
    "#### Intermezzo: Alternating sign sums of a set of binomial coefficients is zero\n",
    "\n",
    "\n",
    "Define two sums that involve binomial coefficients, this first $A_0$ unweighted\n",
    "and the second $A_1$ weighted by index (starting at zero):\n",
    "\n",
    "$\\begin{align}\n",
    "A_0(k) = \\sum_{i=0}^{k} {-1}^i \\cdot \\binom k i\n",
    "\\end{align}$\n",
    "\n",
    "$\\begin{align}\n",
    "A_1(k) = \\sum_{i=0}^{k} {-1}^i \\cdot \\binom k i \\cdot i\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "Then $A_0(0) = 1$, $A_0(k>0) = 0$. This is easy to prove for example using induction\n",
    "or the symmetry of binomial coefficients. Note $A_0(n) = I(n+1)$.\n",
    "\n",
    "\n",
    "\n",
    "$A_1(0) = 0$, $A_1(1) = -1$, $A_1(k>1) = 0$. For $n>0$ we have $A_0(n) = -I(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e22458a3-5311-4f4d-bb11-d61391afc16b",
   "metadata": {},
   "source": [
    "#### 2.5 Complete: Show $f = \\mu * \\nu$ is 0 or 1 where $\\nu(n)$ is the number of distinct prime factors of $n$. \n",
    "\n",
    "\n",
    "This is a good problem threading the non-trivial versus tractable needle. I\n",
    "made some attempts but nothing satisfactory came of that; so this solution\n",
    "is from Chip with my annotations added to slow the pace and add a couple\n",
    "of clarifications. And fix a typo. \n",
    "\n",
    "\n",
    "***Note: Problem 2.5 is found in the chapter 2 examples notebook.***\n",
    "\n",
    "\n",
    "The solution program: First lay out useful tools; then work through five cases for $n$: \n",
    "$n = 1$, $n = p$, $n = p^a$ for $a > 1$, $n = \\prod p_i$ for 2 or more primes (i.e. $n$ is squarefree), \n",
    "and finally $n = p^a \\cdot m$ with $m > 1$.\n",
    "\n",
    "\n",
    "> Relevant to following mechanics:\n",
    "> \n",
    "> $\\nu(1)=0$ (so $\\nu$ is not multiplicative)\n",
    "> \n",
    "> $\\mu$ is multiplicative; hence for prime $p$ where $(p, q) = 1$ we have \n",
    "> $\\mu(p \\cdot q) = \\mu(p) \\cdot \\mu(q) = -\\mu(q)$.\n",
    "> \n",
    "> For $p^a$ with $a \\ge 1$ and $(p, q) = 1$ we have $\\nu(p^a \\cdot q) = 1 + \\nu(a)$.\n",
    "\n",
    "Case 1, $n = 1$: We have $f(1) = 0$. \n",
    "\n",
    "Case 2, $n = p$: $f(p) = 1 \\cdot 1 + -1 \\cdot 0 = 1$.\n",
    "\n",
    "Case 3, $n = p^a$ where $a > 1$: $f(p^a) = 1*1 + -1*1 + 0*1 + \\dots + 0*1 + 0*0 = 0$.\n",
    "\n",
    "Case 4, $n > 1$ is composite and square-free: $n=\\prod p_i$.\n",
    "\n",
    "\n",
    "(Aside: Case 4 can be viewed as a specialization of Case 5 below.)\n",
    "\n",
    "\n",
    "Here we separate say the first prime factor of $n$--call this $p$--such that $p \\cdot m = n$\n",
    "where of course $(p, m) = 1$ and $m > 1$. First: Write out the Dirichlet sum and then \n",
    "partition it into two sums over non-overlapping divisor sets:\n",
    "{divisors of $n$ that *do not* contain $p$} and {divisors of $n$ that *do* contain $p$}.\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|n} \\mu(d) \\cdot \\nu \\left( \\frac{n}{d} \\right)\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|m} \\mu(d) \\cdot \\nu \\left( \\frac{n}{d} \\right) + \\sum_{(p \\cdot d)|n} \\mu(p \\cdot d) \n",
    "\\cdot \\nu \\left( \\frac{n}{p \\cdot d} \\right)\n",
    "\\end{align}$\n",
    "\n",
    "Now the left sum $\\nu$ argument $\\frac{n}{d}$ gets substitution $n = p \\cdot m$. Meanwhile\n",
    "the right sum factor divisor condition $(p \\cdot d) | n$ is changed to $d | m$. This does not change\n",
    "the $\\mu$ and $\\nu$ function arguments: If $p \\cdot d | n$ then that $d | m$ since $n = p \\cdot m$\n",
    "with $p$ and $m$ relatively prime. \n",
    "\n",
    "\n",
    "As an example take $p=2$ and $n=210$ so $m=105$. In the above right-hand sum we have $(pd)|n$ so\n",
    "the $d$ values are $\\{ 1, 3, 5, 7, 15, 21, 35, 105 \\}$. In the substitution to follow below we\n",
    "have $d|m$: The same $d$ values. We factor out $p$ from the sum\n",
    "condition without changing the summands.\n",
    "\n",
    "\n",
    "Lastly there is also a substition of $m$ for $\\frac{n}{p}$ in the \n",
    "right-hand $\\nu$ argument. This gets us the following expression:\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|m} \\mu(d) \\cdot \\nu \\left( p \\cdot \\frac{m}{d} \\right) + \\sum_{d|m} \\mu(p \\cdot d) \n",
    "\\cdot \\nu \\left( \\frac{m}{d} \\right)\n",
    "\\end{align}$\n",
    "\n",
    "Then follows some application of the tools noted above.\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|m} \\mu(d) \\cdot \\left( 1 + \\nu \\left( \\frac{m}{d} \\right) \\right) \n",
    "+ \n",
    "\\sum_{d|m} -\\mu(d) \\cdot \\nu \\left( \\frac{m}{d} \\right)\n",
    "\\end{align}$\n",
    "\n",
    "Now to distribute the left sum interior product:\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|m} \\mu(d) \n",
    "+ \\sum_{d|m} \\mu(d) \\cdot \\nu \\left( \\frac{m}{d} \\right) \n",
    "- \\sum_{d|m} \\mu(d) \\cdot \\nu \\left( \\frac{m}{d} \\right)\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|m} \\mu(d) = 0 \\textrm{ as } m > 1.\n",
    "\\end{align}$\n",
    "\n",
    "Case 5 covers the remainder of the integers: $p$ is prime and $a$ is greater than one; and\n",
    "we can set $n = p^a \\cdot m$ (noting $(p, m) = 1$).\n",
    "Here $m > 1$ and $m$ may or may not include a squared prime factor.\n",
    "\n",
    "\n",
    "Here we break out the Dirichlet sum over divisors of $n$ in terms of powers of $p$:\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\mu(n) * \\nu(n) = \\sum_{d|n} \\mu(d) \\cdot \\nu \\left( \\frac{n}{d} \\right) = \n",
    "\\sum_{i=0}^{a} \\sum_{\\substack{p^i \\cdot d|n \\\\ (p, d) = 1}} \n",
    "\\mu (p^i \\cdot d) \\cdot \\nu \\left( \\frac{n}{p^i \\cdot d} \\right) \n",
    "\\end{align}$\n",
    "\n",
    "The second condition $(p, d) = 1$ ensures we do not double-count factors. \n",
    "\n",
    "\n",
    "(Aside: If Case 5 covered Case 4 this solution would be much simpler.)\n",
    "\n",
    "\n",
    "Ok now *quo vadis*? First of all -- in a brilliant move -- the outer sum need not\n",
    "go beyond $i = 1$ because in such circumstances the argument of $\\mu$ contains a square. \n",
    "\n",
    "Secondly the inner sum uses the same change of divisor conditions as before, again\n",
    "because $(p, m) = 1$: Rather than $p^i d | n$ we can use $d | m$. \n",
    "\n",
    "\n",
    "Thirdly the numerator of the $\\nu$ argument is $n = p^a \\cdot m$.\n",
    "This combines with the $p^i$ in the denominator. \n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{i=0}^{1} \\sum_{d|m} \\mu(p^i \\cdot d) \\cdot \\nu \\left( p^{a-i} \\cdot \\frac{m}{d} \\right)\n",
    "\\end{align}$\n",
    "\n",
    "Now we eliminate the outer $i$-sum by adding the two cases: $i = 0$ and $i = 1$.\n",
    "In the second sum: Also apply the $\\mu(p \\cdot d) = -\\mu(d)$ mechanism.\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|m} \\mu(d) \\cdot \\nu \\left( p^{a} \\cdot \\frac{m}{d} \\right)\n",
    "+\n",
    "\\sum_{d|m} -\\mu(d) \\cdot \\nu \\left( p^{a-1} \\cdot \\frac{m}{d} \\right)\n",
    "\\end{align}$\n",
    "\n",
    "Home stretch: Apply the $\\nu(p^a \\cdot m) = 1 + \\nu(m)$ mechanism. This requires $a > 1$\n",
    "to avoid a $p^0$ situation.\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|m} \\mu(d) \\cdot \\left( 1 + \\nu \\left( \\frac{m}{d} \\right) \\right)\n",
    "- \\sum_{d|m} \\mu(d) \\cdot \\left( 1 + \\nu \\left( \\frac{m}{d} \\right) \\right)\n",
    "= 0\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "Result: $f(p) = 1$ and $f = 0$ otherwise. $\\;\\;$ &#x2610;\n",
    "\n",
    "\n",
    "Continuing the aside from above: It seems that running through case 5 \n",
    "with $a$ set to $1$ would follow the same path until the last step \n",
    "when $p^{a-1}$ is just $1$ so the right-hand $\\nu$ is a bit different: \n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|m} \\mu(d) \\cdot \\left( 1 + \\nu \\left( \\frac{m}{d} \\right) \\right)\n",
    "- \\sum_{d|m} \\mu(d) \\cdot \\left( \\nu \\left( \\frac{m}{d} \\right) \\right)\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f(n) = \\sum_{d|m} \\mu(d) = 0\n",
    "\\end{align}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48fc1537-f0a6-47c4-a9d0-ddf92314b9a4",
   "metadata": {},
   "source": [
    "#### 2.6 Complete: Divisor power sums of Möbius functions\n",
    "\n",
    "\n",
    "Show $\\sum_{d^2|n}\\mu(d)=\\mu^2(n)$ and generalize this result to show $\\sum_{d^k|n}\\mu(d) = 0$ \n",
    "if $m^k|n$ for some $m>1$; $\\sum_{d^k|n}\\mu(d) = 1$ otherwise.\n",
    "\n",
    "\n",
    "\n",
    "Chip takes the direct route: Prove the general expression (parameter $k$) to prove the special case. \n",
    "\n",
    "\n",
    "We have $n$ divided into two types (given $k$): Some $m > 1$ raised to the $k$ divides $n$; or \n",
    "*otherwise* it does not. The value of the Möbius sum: Show it is $0$, $1$ respectively. \n",
    "\n",
    "\n",
    "Take the *otherwise* case first: Over the sum no suitable divisors $d^k|n$ appear save \n",
    "for $d=1$ and we have $\\mu(1) = 1$ as was to be shown. \n",
    "\n",
    "\n",
    "Now the case where at least one prime divisor of $n$ when raised to the $k$ divides $n$. \n",
    "Suppose there are $r$ such primes $p_1, p_2, \\dots p_r$. Each of these is present\n",
    "raised to at least the $k$ power in the prime factorization of $n$. \n",
    "\n",
    "\n",
    "Side note: Supposing this power of $p_i$ exceeds $2k$ as\n",
    "in ${{p_i}^2}^m$: This is immaterial to the Möbius sum because ${p_i}^2$ is a square so \n",
    "$\\mu({p_i}^2)=0$. \n",
    "\n",
    "\n",
    "Those higher powers ignored we consider the $r$ primes that pass the ${p}^k | n$ test.\n",
    "Take the product of these $r$ primes to be a new number $n'$. . Of course $\\sum_{d|n'}\\mu(d) = 0$; \n",
    "so via this extraction we establish the second result. That completes the proof of the\n",
    "general expression; which covers the situation where $d^2$ \n",
    "divides $n$. (The rationale I use circumvents enumeration of $d$ into an alternating-sign\n",
    "sum of a row of the Pascale triangle, summing to zero.) $\\;\\;$ &#x2610;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea22b013-9157-48ae-9d9d-4c8ac601f7c9",
   "metadata": {},
   "source": [
    "#### 2.7 Complete: Divisor sum of a Möbius product\n",
    "\n",
    "\n",
    "Abbreviate $\\mu((p, d))$ as $\\mu(p,d)$. Confirm these three outcomes for some prime $p$: The sum\n",
    "$\\sum_{d|n}\\mu(d)\\cdot\\mu(p,d)=1$ if $n=1$; $=2$ if $n=p^\\alpha$; $=0$ otherwise.\n",
    "\n",
    "Case 1: $n=1$: $d=1$, and the sum becomes $\\mu(1) \\cdot \\mu(1) = 1$, first result confirmed.\n",
    "\n",
    "\n",
    "Case 2: $n=p^\\alpha$. \n",
    "\n",
    "\n",
    "Recall for a number $s$ that is *not* squarefree: $\\mu(s)=0$. In this case, then, only two\n",
    "terms remain in the sum: $d=1$ and $d=p^1$. The sum becomes \n",
    "\n",
    "\n",
    "$\\begin{align}\\sum = \\mu(1) \\cdot \\mu(p, 1) + \\mu(p) \\cdot \\mu(p,p) = 1\\cdot 1 + (-1) \\cdot (-1) = 2.\\end{align}$\n",
    "\n",
    "\n",
    "Second result confirmed.\n",
    "\n",
    "\n",
    "Case 3a: $n$ does not have $p$ as a prime factor: $n = \\prod q_i^{\\beta_i}$.\n",
    "\n",
    "\n",
    "Now the sum over divisors of $n$ only includes first powers of the primes $\\{ q_i \\}$. \n",
    "The Möbius function will give powers of $-1$ for $\\mu(d)$ and $\\mu(p, d)$ will always be $1$. \n",
    "As a result we have the alternating sign sum of binomial coefficients\n",
    "(see solution to 2.5 above), which is zero. \n",
    "\n",
    "\n",
    "Case 3b: $n$ *does* include $p$ as a prime factor (say to some power $\\alpha$). \n",
    "\n",
    "\n",
    "As in (3a) only squarefree divisors of $n$ will contribute to the sum. Divisors of $n$ \n",
    "that do not include $p$ are covered above in (3a), summing to zero. That same set of \n",
    "divisors is now replicated where each has an additional factor of $p$. This gives the\n",
    "same alternating-sign binomial coefficient sum multiplied by (-1) owing to the added\n",
    "factor $p$; so the sum is still zero provided the second factor $\\mu(p,d)$ does not\n",
    "change matters. In fact the second factor in the sum is $\\mu(p,d) = \\mu(p) = -1$. This new set of \n",
    "divisors involving $p$ therefore also sums to zero.\n",
    "\n",
    "Third result confirmed. $\\;\\;$ &#x2610;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8694a62-4ba5-4d82-8a6e-55e4f51e3e3d",
   "metadata": {},
   "source": [
    "#### 2.8 Complete: Show $\\sum_{d|n}\\mu(d) \\cdot \\log^m d = 0$ if $m>0$ and $n$ has $\\nu(n) > m$. (Hint: Induction)\n",
    "\n",
    "\n",
    "Before embarking on a mechanical solution I have to wonder if \"sum over $d$ of $\\mu(d)$ equals 0\" might\n",
    "have some utility here; as the Möbius function is multiplied by powers of logs... like is there a one line\n",
    "solution? \n",
    "\n",
    "\n",
    "Ok be that as it may: \n",
    "The solution given below requires some sophisticated manipulation of sums so my hat is really off to Chip. \n",
    "That is: I happily follow / annotate his work here. The induction strategy assumes the sum is zero up to\n",
    "some value of $m$ (using $\\nu(n)$ for the number of unique prime factors\n",
    "of $n$; which must be greater than $m$).  From there: Show the sum is zero for $m + 1$. With this \n",
    "and from the baseline $\\sum = 0$ for $m=1$ we have a completed (casual) proof. \n",
    "\n",
    "\n",
    "I'm going to start with a couple observations here. First $n$ can be presumed to be a product of \n",
    "$\\nu(n)$ unique prime factors, i.e. $n$ is square-free. Why? Because for non-square-free values of $n$ \n",
    "all of the divisors $d|n$ containing the square of a prime factor give $\\mu(d)=0$ which contributes nothing \n",
    "to the sum. So we simplify life by taking $n = \\prod_{i=1}^{\\nu(n)} p_i$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc63b768-177f-4a44-9bb8-c535c14103a9",
   "metadata": {},
   "source": [
    "Second, for $m=1$ the sum is indeed zero. Why? \n",
    "\n",
    "\n",
    "Let's run it for $n = 30 = 2 \\cdot 3 \\cdot 5$ giving $d =  1, 2, 3, 5, 6, 10, 15, 30$. $\\log 1 = 0$ so we\n",
    "progress to primes and composites. For each $d$ I convert $\\mu(d)$ to $\\pm 1$ and expand the log \n",
    "of a product using $\\log (a\\cdot b) = \\log a + \\log b$. \n",
    "\n",
    "\n",
    "Result: $-\\log 2 - \\log 3 - \\log 5 + \\log 2 + \\log 3 + \\log 2 + \\log 5 + \\log 3 + \\log 5 - \\log 2 - \\log 3 - \\log 5 = 0$.\n",
    "\n",
    "\n",
    "The pattern this establishes is that in the expansion of the sum of logarithms the Möbius function\n",
    "introduces an equal number of $+$ and $-$ signs for each prime factor provided we have at least two of these.\n",
    "\n",
    "\n",
    "That's not really rigorous but it will have to do for this write-up: The sum is zero for $m=1$. Now assume\n",
    "the sum is zero for $m = 1, 2, \\dots$ up to some value of $m$. We can now take $m$ as fixed; and proceed\n",
    "to the sum for $m + 1$ with $\\nu(n) > m + 1$. \n",
    "\n",
    "\n",
    "$\\begin{align}{\\sum_{d|n} \\mu(d) \\log^{m+1}d = \\sum_{d|n} \\mu(d) \\cdot \\log^m d \\cdot \\log d}\\end{align}$$.\n",
    "\n",
    "\n",
    "This is baffling. What is the motivation for factoring the logarithm raised to the $m + 1$ power\n",
    "into two logarithms? Ok true now one of them is just $\\log d$ and the other is $\\log^m d$ which\n",
    "appears to belong in the $m$ case... but still this arrives as the first in a sequence of\n",
    "inspired maneuvers. To continue we notice that $\\log d$ can be reconstrued as the sum of \n",
    "logs of the prime factors of $d$. \n",
    "\n",
    "\n",
    "$\\begin{align}{\\sum_{d|n} \\mu(d) \\log^{m+1}d = \\sum_{d|n} \\mu(d) \\cdot \\log^m d \\cdot \\sum_{p_i|d}\\log p_i}\\end{align}$\n",
    "\n",
    "\n",
    "This again uses the 'log of a product' rule. \n",
    "\n",
    "\n",
    "Retaining a concrete example might help so let's bump up from $n = 30$ to $n = 210$ with four\n",
    "distinct prime factors $2, 3, 5, 7$. This puts $m$ at 1 or 2 but keep $m$ as just abstract $m$. \n",
    "Now the sum over $d|n$ covers $\\{ 1, 2, 3, 5, 7, 6, 10, 14, 15, 21, 35, 30, 42, 105, 210 \\}$.\n",
    "Of these $d = 1$ can be ignored due to $\\log 1 = 0$. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ade3966f-bac4-4b42-b6cd-70d890a56efe",
   "metadata": {},
   "source": [
    "The next step requires a good deal of staring: It reverses the order of the sums and this comes with\n",
    "a change in both sum conditions.\n",
    "\n",
    "\n",
    "$\\begin{align}{\\sum_{d|n} \\mu(d) \\log^{m+1}d = \\sum_{d|n} \\mu(d) \\cdot \\log^m d \\cdot \\sum_{p_i|d}\\log p_i = \n",
    "\\sum_{p_i|n} \\sum_{\\substack{d|n \\\\ p_i|d}} \\log p_i \\cdot \\mu(d) \\cdot \\log^m d}\\end{align}$\n",
    "\n",
    "\n",
    "\n",
    "This remarkable transformation *requires* the revised conditions to produce all the same terms. \n",
    "It is sort of a restacking of those terms by a shift in emphasis. Consider that one of the terms \n",
    "in the upper sum (still for $n = 210$) is $\\mu(10) \\cdot \\log^m(10) \\cdot (\\log 2 + \\log 5)$.\n",
    "Multiply this out to get two terms. \n",
    "\n",
    "\n",
    "Now with the sum order reversed the new outer sum produces these same two terms. \n",
    "This will be when $p_1 = 2$ and when $p_3 = 5$: From that outer sum over $p_i|n$. \n",
    "For each $p_i$ the inner sum goes through all the $d|n$ but with the additional\n",
    "condition to only consider $d$ divisible by that outer sum prime: $p_i|d$. \n",
    "In the example we have $p_1 = 2$ giving us a term $\\log 2 \\cdot (\\mu(10) \\cdot \\log^m(10))$.\n",
    "Later on with $p_3 = 5$ we get the second term $\\log 5 \\cdot (\\mu(10) \\cdot \\log^m(10))$.\n",
    "\n",
    "\n",
    "Notice in the above expression that $\\log p_i$ depends only $p_i$ (not on $d$) so\n",
    "it can be factored out of the inner sum and now we have\n",
    "\n",
    "\n",
    "$\\begin{align}{\\sum_{d|n} \\mu(d) \\log^{m+1}d = \\sum_{p_i|n} \\log p_i \n",
    "\\sum_{\\substack{d|n \\\\ p_i|d}} \\mu(d) \\cdot \\log^m d}\\end{align}$\n",
    "\n",
    "\n",
    "The next step is another remarkable one. The goal is to rewrite the inner sum above. \n",
    "I'm going to illustrate the strategy using the example numbers first and then describe\n",
    "the transformation. \n",
    "\n",
    "\n",
    "Take the case of $p_1=2$ and now the inner sum will use $d = \\{ 2, 6, 10, 14, 30, 42, 70, 210 \\}$ so\n",
    "there are eight values for $d$, all divisible by $2$. These will appear in the inner sum, as in\n",
    "$\\mu(2) \\cdot \\log^m(2) + \\mu(6) \\cdot \\log^m(6) + \\mu(10) \\cdot \\log^m(10) + \\cdots + \\mu(210) \\cdot \\log^m(210)$.\n",
    "We could just as easily make the inner sum be over those same numbers divided by the outer \n",
    "sum prime $2$ provided that the function is modified to multiply back by the outer sum prime. \n",
    "That is: Dividing by $2$ we have a new set of divisors of $n/p_1$ and a 'restoring' version\n",
    "of the Möbius and logarithm functions. The new $d = \\{ 1, 3, 5, 7, 15,21, 35, 105 \\}$ and the\n",
    "new function is now $\\mu(d \\cdot p_i) \\cdot \\log^m d \\cdot p_i$.\n",
    "\n",
    "\n",
    "The net result here is that the inner sum produces all the same terms as before; but the \n",
    "outer sum prime $p_i$ is introduced in the inner sum as a factor of the Möbius and logarithm\n",
    "arguments. \n",
    "\n",
    "\n",
    "\n",
    "$\\begin{align}{\\sum_{d|n} \\mu(d) \\log^{m+1}d = \\sum_{p_i|n} \\log p_i \n",
    "\\sum_{d|\\frac{n}{p_i}} \\mu(d \\cdot p_i) \\cdot \\log^m d \\cdot p_i}\\end{align}$\n",
    "\n",
    "\n",
    "So far so good; and next: The argument of the Möbius function is a product of unique prime factors; \n",
    "so the $p_i$ factor contributes a minus sign to the end result. We can remove this $p_i$ and put a\n",
    "negative sign out front. Also let's expand the logarithm of the product in the usual manner.\n",
    "\n",
    "\n",
    "$\\begin{align}{\\sum_{d|n} \\mu(d) \\log^{m+1}d = -\\sum_{p_i|n} \\log p_i \\sum_{d|\\frac{n}{p_i}} \\mu(d) \n",
    "\\cdot (\\log d + \\log p_i)^m}\\end{align}$\n",
    "\n",
    "\n",
    "The sum of the two logarithms raised to the $m$ power: Replace with the binomial theorem sum.\n",
    "\n",
    "\n",
    "$\\begin{align}{\\sum_{d|n} \\mu(d) \\log^{m+1}d = -\\sum_{p_i|n} \\log p_i \\sum_{d|\\frac{n}{p_i}} \\mu(d) \n",
    "\\cdot \\sum_{j=0}^m \\binom{m}{j} \\cdot \\log^j d \\cdot log^{m-j} p_i}\\end{align}$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "247ff9d7-9797-4396-8ac6-b4447ec99a63",
   "metadata": {},
   "source": [
    "Home stretch: Swap the order of the inner two sums by first pushing the Möbius function into the innermost loop.\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "{\\sum_{d|n} \\mu(d) \\log^{m+1}d = -\\sum_{p_i|n} \\log p_i \\sum_{d|\\frac{n}{p_i}} \n",
    "\\sum_{j=0}^m \\mu(d) \\binom{m}{j} \\cdot \\log^j d \\cdot log^{m-j} p_i}\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "{\\sum_{d|n} \\mu(d) \\log^{m+1}d = -\\sum_{p_i|n} \\log p_i \n",
    "\\sum_{j=0}^m \n",
    "\\sum_{d|\\frac{n}{p_i}}\n",
    "\\mu(d) \\binom{m}{j} \\cdot \\log^j d \\cdot log^{m-j} p_i}\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "Finally factor elements out of the inner loop that have no $d$ dependence:\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "{\\sum_{d|n} \\mu(d) \\log^{m+1}d = -\\sum_{p_i|n} \\log p_i \n",
    "\\sum_{j=0}^m\n",
    "\\binom{m}{j} \\cdot\n",
    "log^{m-j} p_i \\cdot\n",
    "\\sum_{d|\\frac{n}{p_i}}\n",
    "\\mu(d) \\cdot \\log^j d }\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "Here we have an inner loop over divisors with exponent $j$ in the range $0$ to $m$; \n",
    "and this we presume is established as zero. (The $m=0$ case is zero by inspection.)\n",
    "\n",
    "\n",
    "So per the plan at the outset: We have a (roughly speaking) completed proof by induction. \n",
    "The argument thread has rested heavily on the separability of the Möbius and logarithm\n",
    "functions as well as summation logic.  $\\;\\;$ &#x2610;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6aa0db45-392b-4d3e-be1b-a85b51f8d0dd",
   "metadata": {},
   "source": [
    "#### 2.9 Complete: Extending the totient $\\varphi$ for $x \\in \\mathbb{R}$\n",
    "\n",
    "If $x \\in \\mathbb{R}$, $x \\ge 1$: Let $\\varphi(x, n)$ denote the number of positive integers $\\le x$ \n",
    "that are relatively prime to $n$.\n",
    "\n",
    "\n",
    "a) Show $\\varphi(x, n) = \\sum_{d|n} \\mu(d) \\lfloor \\frac{x}{d} \\rfloor$.\n",
    "\n",
    "\n",
    "b) Show $\\sum_{d|n} \\varphi(\\frac{x}{d}, \\frac{n}{d}) = \\lfloor x \\rfloor$.\n",
    "\n",
    "\n",
    "Both a) and b) are borne out in the Chapter 2 Examples notebook. That work illustrates\n",
    "that it is useful to stipulate that $\\varphi(x, n) = 0$ when $x < 1$. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13f1adb9-cc16-4afb-8d09-7d94314e6d92",
   "metadata": {},
   "source": [
    "Part a) This solution elaborates on Chip's. It begins with the 'to be shown'\n",
    "expression and works backwards to arrive at $\\varphi(x, n)$.\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\sum_{d|n} \\mu(d) \\cdot {\\Large \\lfloor} \\frac{x}{d} {\\Large \\rfloor} \n",
    "= \\sum_{d|n} {\\Large \\lfloor} \\frac{x}{d} {\\Large \\rfloor} \\cdot \\mu(d)\n",
    "= \\sum_{d|n} \\sum_{k=1}^{{\\Large \\lfloor} x/d {\\Large \\rfloor}} \\mu(d)\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "using the artifice ${\\Large \\lfloor} \\frac{x}{d} {\\Large \\rfloor} = 1 + 1 + 1 + \\dots + 1$, \n",
    "a sum of ones. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77464a1d-d664-4f3c-abde-de098ec47145",
   "metadata": {},
   "source": [
    "The Theorem 2.3 proof relates to the switch in summation order that ensues.\n",
    "I will illustrate through an extended example how the $k$ index sum swaps with\n",
    "the $d$ index sum with an appropriate change in ranges.\n",
    "\n",
    "\n",
    "I use $n = 12$ and $x = 17.2$, noting $\\varphi(x, n) = 6$. \n",
    "Then $d \\in \\{1, 2, 3, 4, 6, 12\\}$ with corresponding $\\mu(d)$ being $\\{1, -1, -1, 0, 1, 0\\}$. \n",
    "The corresponding weights are $\\{17, 8, 5, 4, 2, 1 \\}$:\n",
    "$17 \\cdot 1 + 8 \\cdot (-1) + 5 \\cdot (-1) + 4 \\cdot 0 + 2 \\cdot 1 + 1 \\cdot 0 = 6$.\n",
    "\n",
    "\n",
    "I now express the generalized totient calculation via a table of $\\mu(d)$ values: \n",
    "$d | n \\; and \\; k \\in 1, \\dots, \\lfloor x/d \\rfloor$.\n",
    "\n",
    "\n",
    "|d|k=1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|partial $\\sum$|\n",
    "|---|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|:-------:|\n",
    "|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|17|\n",
    "|2|-1|-1|-1|-1|-1|-1|-1|-1||||||||||-8|\n",
    "|3|-1|-1|-1|-1|-1|||||||||||||-5|\n",
    "|4|0|0|0|0||||||||||||||0|\n",
    "|6|1|1||||||||||||||||2|\n",
    "|12|0|||||||||||||||||0|\n",
    "|||||||||||||||||||$\\sum = 6$|\n",
    "\n",
    "\n",
    "If $k \\in \\{ 1, \\dots, \\lfloor x/d \\rfloor \\}$ we can equivalently multiply\n",
    "the $k$ values by $d$ in each row, scaling up the representation:\n",
    "$k \\in \\{ d, 2 d, 3 d, ... , q \\cdot d <= \\lfloor x \\rfloor \\}$. The value\n",
    "of $\\mu(d)$ remains unchanged as does the number of $\\mu$ values in each\n",
    "row so the final sum is as above. The table now looks like this:\n",
    "\n",
    "\n",
    "|d|k=1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|partial $\\sum$|\n",
    "|---|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|:-------:|\n",
    "|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|17|\n",
    "|2||-1||-1||-1||-1||-1||-1||-1||-1||-8|\n",
    "|3|||-1|||-1|||-1|||-1|||-1|||-5|\n",
    "|4||||0||||0||||0||||0||0|\n",
    "|6||||||1||||||1||||||2|\n",
    "|12||||||||||||0||||||0|\n",
    "|||||||||||||||||||$\\sum = 6$|\n",
    "\n",
    "\n",
    "The reversed-order double sum is appended:\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\sum_{d|n} \\mu(d) \\cdot {\\Large \\lfloor} \\frac{x}{d} {\\Large \\rfloor}\n",
    "= \\sum_{d|n} \\sum_{k=1}^{{\\Large \\lfloor} x/d {\\Large \\rfloor}} \\mu(d)\n",
    "= \\sum_{k=1}^{\\lfloor x \\rfloor} \\;\\; \\sum_{d|(n, k)} \\mu(d)\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "From theorem 2.1 the inner sum is the identity function of $(n, k)$:\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\sum_{d|n} \\mu(d) \\cdot {\\Large \\lfloor} \\frac{x}{d} {\\Large \\rfloor} = \n",
    "\\sum_{k=1}^{\\lfloor x \\rfloor} I((n, k)) = \\varphi(x, n) \\end{align}$.  $\\;\\;$ &#x2610;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1759b8c-50cd-4069-95fd-7c5e403ccb4a",
   "metadata": {},
   "source": [
    "2.9 b) Take $x$ to represent $\\lfloor x \\rfloor$. Second, notice there is no $\\mu(d)$ involved; \n",
    "this is strictly the extended totient scaled by a fixed divisor $d$: $\\varphi(x/d, n/d)$.  \n",
    "\n",
    "\n",
    "Reminder: We *partition* a set of integers into subsets with each integer present once:\n",
    "nothing missing, no repetitions.\n",
    "\n",
    "Define the set of consecutive integers from $1$ to $\\lfloor x \\rfloor$ as $S_x = \\{ 1, 2, \\dots, \\lfloor x \\rfloor\\}$.\n",
    "Partition this into sets corresponding to values of $d$ that divide $n$. Chip uses $A_{xn}(d)$\n",
    "but I am going to use $A_d$ with $x$ and $n$ implicit. \n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\textrm{Define } A_d=\\{ \\; k \\in S_x \\ni d = (n, k)\\; \\} \\textrm{ and define } f_d = |A_d|\n",
    "\\end{align}$\n",
    "\n",
    "Of course $k$ will be taking on values that are multiples of $d$ to satisfy that second condition; so 'hopping'. \n",
    "\n",
    "\n",
    "As $\\{ A_d \\}$ partitions $S_x$, the sum of all the $f_d$ values will be $\\lfloor x \\rfloor$. So far so good. \n",
    "\n",
    "\n",
    "Now we can scale down the expression for $d$ in the definition of $f_d$ (really in $A_d$) by\n",
    "dividing out $d$: The gcd of $n/d$ and $k/d$ becomes $1$ (so they are relatively prime):\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "f_d = \\left| \\{  \\; q \\;\\; \\ni \\;\\; 1 \\le q \\le \\frac{x}{d} \\;\\; \\cap \\;\\; 1 = (q, \\frac{n}{d}) \\; \\} \\right|\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "So $f_d$ is now expressing a count of relative primes precisely in the manner of the extended totient:\n",
    "\n",
    "\n",
    "$\\begin{align}f_d = \\varphi \\left( \\frac{x}{d}, \\frac{n}{d} \\right) \\end{align}$.\n",
    "\n",
    "\n",
    "Since the $f_d$ summed over divisors of $n$ is $x$ we have \n",
    "established that $\\sum_{d|n} \\varphi \\left( \\frac{x}{d}, \\frac{n}{d} \\right) = \\lfloor x \\rfloor$.  $\\;\\;$ &#x2610;\n",
    "\n",
    "Define $S_x = 1, 2, \\dots , x $ and partition this based on the divisors $d$ of $n$ into subsets.\n",
    "For a fixed value of $d \\textrm{ we have } A_{n,x,d} = \\{ k \\backepsilon d = (n, k)\\}$.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "We have three starter definitions: A set of integers up to \n",
    "$\\lfloor x \\rfloor$, a partition of this set into subsets, and a function based on the partition.\n",
    "\n",
    "\n",
    "Define $S_x = \\{ 1, 2, \\dots, \\lfloor x \\rfloor \\}$. Example: $\\{ 1, 2, 3, \\dots, 17 \\}$\n",
    "\n",
    "\n",
    "Define a partition of $S_x$ into a set of subsets: \n",
    "$A_{x, n}(d) = \\{ k \\in S_x \\; { \\large \\backepsilon } \\; (k, n) = d \\}$.\n",
    "\n",
    "\n",
    "English: The $d$-subset of $S_x$ are the numbers that have $gcd$ with respect to $n$ equal to $d$.\n",
    "\n",
    "\n",
    "Define a function $f$ as the size of $A$: $f_{x, n}(d) = | A_{x, n}(d) |$.\n",
    "\n",
    "\n",
    "As above with $x = 17.2$ (using $\\lfloor x \\rfloor = 17$) and $n = 12$\n",
    "\n",
    "\n",
    "- $A_{17, 12}(1) = \\{ 1, 5, 7, 11, 13, 17 \\}$; $f = 6$\n",
    "- $A_{17, 12}(2) = \\{ 2, 10, 14 \\}$; $f = 3$\n",
    "- $A_{17, 12}(3) = \\{ 3, 9, 15 \\}$; $f = 3$\n",
    "- $A_{17, 12}(4) = \\{ 4, 8, 16 \\}$; $f = 3$\n",
    "- $A_{17, 12}(6) = \\{ 6 \\}$; $f = 1$\n",
    "- $A_{17, 12}(12) = \\{ 12 \\}$; $f = 1$\n",
    "\n",
    "\n",
    "\n",
    "For $n=12$ only the $d \\in \\{ 1, 2, 3, 4, 6, 12 \\}$ yield non-zero $f$ values. \n",
    "$A$ partitions $S_x$ without repetitions or skips so the sum of the $f$ values is \n",
    "$\\lfloor x \\rfloor$.\n",
    "\n",
    "\n",
    "$\\begin{align} \n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "$\\begin{align} \n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "$\\begin{align} \n",
    "\\end{align}$\n",
    "\n",
    "#### In 2.10, 2.11, 2.12: $d(n)$ denotes the number of positive divisors of $n$.\n",
    "\n",
    "\n",
    "#### 2.10 Show $\\begin{align}{\\small\\prod_{t|n} t = n^{\\frac{d(n)}{2}}}\\end{align}$\n",
    "\n",
    "\n",
    "- $n=1$ checks out...\n",
    "- Suppose $n$ is prime so $d=2$\n",
    "    - The RHS becomes ${\\large n^{2/2}}$. The LHS product is $1 \\cdot n$. Everything is fine!\n",
    "\n",
    "\n",
    "\n",
    "Pairwise example for a compound $n=60$: $(1 \\cdot 60) \\cdot (2 \\cdot 30) \\cdot \\dots \\cdot (6 \\cdot 10)$. \n",
    "Counting: $d(60) = 12$; $6$ products, each equal to $60.$ Half $d(n)$ is the exponent of $n$. \n",
    "\n",
    "\n",
    "The ***exception*** to this rationale is when $n$ is a square; so we need to check that out. \n",
    "For $n=25$ we have $1 \\cdot 5 \\cdot 25 = 125$ and $d(25)=3$, odd. The pairing concept is a bit\n",
    "modified now: The pairs multiply out as before but the square root of $n$ multiplied by\n",
    "itself introduces an extra factor, an extraneous square root of $n$.\n",
    "\n",
    "\n",
    "$\\begin{align}{\\Large \\sqrt{n} \\cdot n^{\\frac{d_{odd}-1}{2}}}\\end{align}$ \n",
    "\n",
    "\n",
    "and here again we arrive at $n^{\\frac{d}{2}}$. This completes the problem but I want to point out\n",
    "Chip's elegant solution: \n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "n^d = \\prod_{t|n}n = \\prod_{t|n} t \\cdot \\frac{n}{t} = \\prod_{t|n}{t} \\cdot \\prod_{t|n}{\\frac{n}{t}} = \\Bigl\\{ \\prod_{t|n} t \\Bigr\\}^2\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "#### 2.11 Show if $n$ has an odd number of divisors $n$ is a square.\n",
    "\n",
    "\n",
    "- Gauss' class was tasked with summing  $1 + 2 + \\cdots + 99 + 100$\n",
    "    - Pairing 1 with 100 and so on simplifies the task to $50 \\cdot 101$.\n",
    "    - Analogy with this problem: Pair the factors of $n$: $f \\textrm{ and } n/f$\n",
    "        - Only when $n$ is a perfect square do we have degeneracy and an odd number of divisors.$\\;\\;$ &#x2610;\n",
    "\n",
    "***Note: Here is an alternative proof for 2.11***\n",
    "\n",
    "I think this hews closer to the spirit of number theory via inexhorable Tomminess.\n",
    "\n",
    "\n",
    "Let's look at the factorization of $n$ which we assume has an odd number of divisors.\n",
    "\n",
    "\n",
    "Factoring $n$ is equivalent to counting how many subsets can be formed from the prime \n",
    "factorization of $n$; with of course $n = \\prod {p_i}^{a_i}$. The subsets simply count\n",
    "through each prime with the $i$'th prime raised to every possible exponent: \n",
    "$0, 1, \\dots, a_i$ so for this prime there are $a_i + 1$ \n",
    "possible exponents. Now it appears that the total number of divisors $d$\n",
    "(the number of permutations of prime factors raised to exponents) \n",
    "is $d = (a_1 + 1)\\cdot(a_2 + 1)\\cdot \\dots \\cdot(a_k + 1)$.\n",
    "\n",
    "\n",
    "Taking $d$ to be odd: Each factor in the above expression is necessarily \n",
    "odd. Therefore each $a_i$ is even and greater than 1, and is therefore the \n",
    "sum of two equal integers. This conclusion applying as it does to all prime \n",
    "factors of $n$ shows that $n$ is a perfect square.$\\;\\;$ &#x2610; \n",
    "\n",
    "#### 2.12 Incomplete: Show that $\\sum_{t|n} d(t)^3 = \\bigl( \\sum_{t|n} d(t)\\bigr)^2.$  \n",
    "\n",
    "\n",
    "The assertion is true for $n=1$ ($1=1$) and $n$ *prime* ($1 + 8 = (1+2)^2$) \n",
    "and for $n$ the product of \n",
    "two primes $p \\textrm{ and } q: \\;\\; (n=p\\cdot q \\textrm{ produces }81=81)$ \n",
    "and for a prime multiplied by a prime-squared \n",
    "$n = p \\cdot q^2$ (resulting in $324 = 18^2$). So that is an encouraging start. It \n",
    "suggests an algebraic manipulation of $n=\\prod {p_i}^{a_i}$, proceeding to an expression for the\n",
    "number of divisors $d(n)$.\n",
    "\n",
    "\n",
    "Let's check in with Chip on his solution. He points out:\n",
    "\n",
    "\n",
    "* $d$ is multiplicative\n",
    "* Useful fact: Nicomachus' Theorem is $\\sum_{i=1}^n {i^3} = \\left( \\sum_{i=1}^n {i}\\right)^2\\;$. \n",
    "I proved using induction, the formula for the sum of $1+2+\\cdots+n$, and a little algebra.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#### 2.13 Incomplete: *Product form of the Möbius inversion formula*\n",
    "\n",
    "\n",
    "***Note: There is a section in the *examples* notebook on this problem.***\n",
    "\n",
    "\n",
    "If $f(n) > 0$ for all $n$ and if $a(n)$ is real with $a(1) \\ne 0$, prove that\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "g(n) =  \\prod_{d|n}f(d)^{a(\\frac{n}{d})} \\;\\; \\textrm{ if and only if } \\;\\; f(n)=\\prod_{d|n}g(d)^{a^{-1}(\\frac{n}{d})},\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "- We have a recursive means of generating the inverse of a function\n",
    "- We have the Möbius inversion formula relating two functions f() and g() in terms of a third function a() and its inverse()\n",
    "    - Notice this does not make f() and g() inverses; nor does it provide a formula for a-inv() in terms of a()\n",
    "- Chip Hurst's solution is extravagantly long; avoid for now and instead try and proceed directly from Tommy's building blocks\n",
    "\n",
    "#### 2.14 Incomplete: On functions of a rational x on $[0, 1]$ and roots of unity\n",
    "\n",
    "\n",
    "Let $f(x)$ be defined for all rational $x$ in $0 \\le x \\le 1$. Define two functions $F(n)$ and $F^*(n)$: \n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "F(n) = \\sum_{k=1}^n f \\Bigl( \\frac{k}{n} \\Bigr), \\;\\;\\; F^*(n)=\\sum_{\\;\\;k=1; \\newline(k,n)=1}^n f \\Bigl( \\frac{k}{n} \\Bigr).\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "(a) Show $F^* = \\mu * F$.\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "\\mu * F = \\sum_{d|n}\\mu(d) \\cdot F(n/d) = \\sum_{d|n} \\Biggl( \\mu(d) \\cdot \\sum_{k=1}^{n/d} f \\Bigl( \\frac{k}{n} \\Bigr) \\Biggr)\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "(b) Show that $\\mu(n)$ is the sum of the primitive $n$th roots of unity\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "\\mu(n) = \\sum_{\\;\\;k=1; \\newline(k,n)=1}^n e^{2 \\pi i k/n}.\n",
    "\\end{align}\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16614ba2-212f-4d96-be89-f9ef8d6a8997",
   "metadata": {},
   "source": [
    "#### 2.15 Incomplete: Generalized totient proof (Suggestion: Use **2.14**)\n",
    "\n",
    "\n",
    "Let $\\varphi_k(n)$ denote the sum of the $k$th powers of the numbers $\\le n$ and relatively prime to $n$. Note $\\varphi_0(n) = \\varphi(n)$. \n",
    "Show that \n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "\\sum_{d|n} \\frac{\\varphi_k(d)}{d^k} = \\frac{1^k + \\cdots + n^k}{n^k}.\n",
    "\\end{align}\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbb18976-d54a-40cf-be47-41a66bbfeb77",
   "metadata": {},
   "source": [
    "#### 2.16 Invert the formula in **2.15** to obtain, for $n > 1$, \n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "\\varphi_{1}(n)= \\frac{1}{2} \\cdot n \\cdot \\varphi(n),\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "and\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "\\varphi_{2}(n) = \\frac{1}{3} \\cdot n^2 \\cdot \\varphi(n) + \\frac{n}{6} \\prod_{p|n}(1-p).\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "Derive a corresponding formula for $\\varphi_3(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28a2c59e-a717-43f1-a51d-3d8a96b93a52",
   "metadata": {},
   "source": [
    "#### 2.17 Incomplete:\n",
    "\n",
    "\n",
    "#### 2.18 Incomplete:\n",
    "\n",
    "\n",
    "#### 2.19 Incomplete:\n",
    "\n",
    "\n",
    "#### 2.20 Incomplete:\n",
    "\n",
    "\n",
    "#### 2.21 Incomplete:\n",
    "\n",
    "\n",
    "#### 2.22 Incomplete:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "386a4554-c6ad-4e92-aecd-986479f44f67",
   "metadata": {},
   "source": [
    "#### 2.23 Prove or give a counterexample that for $f$ a multiplicative function: $F$ defined below is multiplicative as well.\n",
    "\n",
    "\n",
    "$\\begin{align}F(n) = \\prod_{d|n} f(d)\\end{align}$\n",
    "\n",
    "\n",
    "False by counterexample: For $f(n)$ use $\\mu(n)$: Then $F_{\\mu}(30) \\ne F_{\\mu}(2) \\cdot F_{\\mu}(15)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4af4e0af-0bbe-4939-9ec4-23a35b05dbbd",
   "metadata": {},
   "source": [
    "#### 2.24 Incomplete:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "117839db-952e-4306-9755-a397fbe02897",
   "metadata": {},
   "source": [
    "#### 2.25 (a) Complete: For $f$ a multiplicative function: Show the Dirichlet inverse $f^{-1} = \\mu f$ for all square-free $n$.\n",
    "\n",
    "\n",
    "Conversational recap: A Dirichlet inverse for value $n$ supposes two\n",
    "functions $f$ and $f^{-1}$ defined at $n$ whose Dirichlet product is $0$ for $n > 1$ and $1$ when $n = 1$.\n",
    "$f$ (being multiplicative) has *some* Dirchlet inverse for any $n \\ge 1$; but in this problem we consider \n",
    "the subset of $Z^+$ with $n$ square-free: $[1, 2, 3, 5, 6, 7, 10, 11, 13, 14, \\dots]$.\n",
    "Claim to prove: For square-free $n$ the inverse $f^{-1}$ is the product $\\mu \\cdot f$.\n",
    "(This is not a Dirichlet product; it is the product of the function values.)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f1262da-af33-4518-8982-0ce00797aa8a",
   "metadata": {},
   "source": [
    "Reminder: A multiplicative function follows two rules: It is not identically zero and for two \n",
    "relatively prime numbers $(m, n) = 1$ we have $f(mn) = f(m) \\cdot f(n)$. \n",
    "\n",
    "Examples: \n",
    "\n",
    "\n",
    "| n  |     $\\varphi$   |  $\\mu$  |   mu f  |   f*(mu f) |  ***I*** |\n",
    "| :---|      ---:|     ---:|    ------:|    ---:|   ---:| \n",
    "| 1   |    1    |             1    |     1    |      1      |    1  |\n",
    "| 2   |    1    |            -1    |    -1    |      0      |    0  |\n",
    "| 3   |    2    |            -1    |    -2     |     0      |    0  |\n",
    "| 4   |    2    |             0    |     0    |      1 *    |    0  | \n",
    "| 5   |    4    |            -1    |    -4    |      0      |    0  |\n",
    "| 6   |    2    |             1    |     2    |      0      |    0  |\n",
    "| 7   |    6    |            -1    |    -6    |      0      |    0  |\n",
    "| 8   |    4    |             0    |     0    |      2 *    |    0  |\n",
    "| 9   |    6    |             0    |     0    |      2 *    |    0  |\n",
    "| 10  |    4    |             1    |     4    |      0      |    0  |\n",
    "| 11  |   10    |            -1    |   -10    |      0      |    0  |\n",
    "| 12  |    4    |             0    |     0    |      0 *    |    0  |\n",
    "| 13  |   12    |            -1    |   -12    |      0      |    0  |\n",
    "| 14  |    6    |             1    |     6    |      0      |    0  |\n",
    "\n",
    "(\\* not square-free)\n",
    "\n",
    "For $n=1$ we have $f^{-1} = 1$ (see proof of theorem 2.8) and the proposed inverse is correct."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1824720a-9a12-4f57-9689-040872e51691",
   "metadata": {},
   "source": [
    "For $n > 1$: Pairs of divisors of $n$ of the form\n",
    "$\\{ d, \\frac{n}{d} \\}$ will have $(d, n/d)=1$ as otherwise $n$ would not be square-free.\n",
    "This is because $d \\cdot \\frac{n}{d} = n$ and the two multiplicands share a common \n",
    "prime factor.\n",
    "\n",
    "\n",
    "Since $(d, n/d) = 1$ and $f$ is multiplicative we have $f(d) \\cdot f(n/d) = f(d \\cdot \\frac{n}{d}) = f(n)$. \n",
    "\n",
    "\n",
    "Looking to $n>1$ we want to show that $f^{-1}(n) * f(n) = 0$.\n",
    "\n",
    "\n",
    "$f^{-1}(n) * f(n) = \\sum_{d|n} \\mu(d) \\cdot f(d) \\cdot f(\\frac{n}{d}) = f(n)\\sum_{d|n}\\mu(d) = f(n) \\cdot 0 = 0$ \n",
    "using Theorem 2.1. $\\;\\;$ &#x2610;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc27969e-d236-4692-98c2-86931c1b97b8",
   "metadata": {},
   "source": [
    "***In passing:*** The divisors of $n>1$ can be generated from $(1 + p_1)\\cdot(1 + p_2) \\dots (1 + p_i)$. This applies to \n",
    "Dirichlet multiplication as a sum, for example with\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "\\sum_{d|n} \\mu(d) = \\mu(1) + \\binom{i}{1} \\cdot \\mu(p_1) + \\binom{i}{2} \\cdot \\mu(p_1\\cdot p_2) + \\dots + \n",
    "\\mu(p_1 \\cdot p_2 \\dots p_i) = \\sum_{k=0}^{i} {-1}^k \\binom{i}{k} = 0.\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "(On the last step here: See the solution to 2.5 above.)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e21163bd-f6ea-4988-ab04-bd91cc269a86",
   "metadata": {},
   "source": [
    "#### 2.25 (b) Complete: Again with $f$ multiplicative: Show for any prime $p$ that $f^{-1}(p^2)=f(p^2)-f(p)^2$ \n",
    "\n",
    "\n",
    "Semantic note: This condition $n = p^2$ applies to a subset of the \n",
    "integers $\\{ 1, 2, 3, 4, \\dots \\}$. \n",
    "That is, $f$ is multiplicative and is therefore arithmetic and is therefore defined on *all*\n",
    "integers; but the problem only concerns the proposed inverse for \n",
    "the subset $n = \\{ 4, 9, 25, 49, \\dots\\}$. Again\n",
    "we can begin with $f(1)=1$ and $f^{-1}(1)=1$ as in **2.25(a)**. And now for $n>1, \\; n=p^2$ \n",
    "the Dirichlet product $f_{proposed}^{-1} * f$ must again be zero.\n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "f_{proposed}^{-1}(p^2) * f(p^2) = \\sum_{d|n} = \\sum_{d\\in\\{1,p,p^2\\}}(f(d^2)-f(d)^2)\\cdot f(\\frac{n}{d})\n",
    "\\end{align}\n",
    "$\n",
    "\n",
    "\n",
    "Elaborating the three terms in the sum: \n",
    "\n",
    "\n",
    "$\n",
    "\\begin{align}\n",
    "f_{proposed}^{-1} * f = \\bigl( f(1)-f(1)^2 \\bigr) \\cdot f(p^2) +\n",
    "                        \\bigl( f(p^2)-f(p)^2 \\bigr)\\cdot f(p) +\n",
    "                        \\bigl( f(p^4) - f(p^2)^ \\bigr) \\cdot f(1). \n",
    "\\end{align}\n",
    "$\n",
    "                          \n",
    "                          \n",
    "$\\begin{align}\n",
    "f_{proposed}^{-1} * f = 0 \\cdot f(p^2) +\n",
    "                          f(p^2) \\cdot f(p) - f(p)^2 \\cdot f(p) +\n",
    "                          f(p^4) - f(p^2)^2. \n",
    "\\end{align}\n",
    "$\n",
    "                          \n",
    "                          \n",
    "                          \n",
    "$$f_{proposed}^{-1} * f = f(p^4) - f(p^2)^2 = 0.$$\n",
    "\n",
    "\n",
    "This final couple steps make use of Theorem 2.13b: $f(p^a)=f(p)^a.\\;\\;$&#x2610;\n",
    "\n",
    "#### 2.26 Incomplete: For $f$ multiplicative: Proceed to show $f$ is *completely* multiplicative if and only if $f^{-1}(p^a)=0$ for all primes $p$ and all integers $a \\ge 2$.\n",
    "\n",
    "\n",
    "- One approach to 'if and only if' proof is to show both $A \\implies B$ \n",
    "and $B \\implies A$. \n",
    "\n",
    "\n",
    "- I write the Dirichlet inverse of $f$ as $g$, easier than $f^{-1}$. \n",
    "\n",
    "\n",
    "- For $n=p^a$ we have the Dirichlet sum divisors $d \\in \\{ 1, p, p^2, \\dots, p^a \\}$.\n",
    "Furthermore $f(1) = g(1)=1$.\n",
    "\n",
    "\n",
    "- Question: Under what circumstances do we have $f(p^a)=f(p)^a$?\n",
    "\n",
    "\n",
    "- Remark: Chip uses Thm 2.17 to go from the premise of\n",
    "$f$ completely multiplicative to the expression for the inverse $g$ as\n",
    "$g(n) = \\mu(n) \\cdot f(n)$ noting this is zero for $n=p^a$ with $a > 1$ \n",
    "since $\\mu$ is then given a squareful argument.\n",
    "\n",
    "\n",
    "- Taking $f$ to be completely multiplicative for integers $1, 2, \\dots$ let us proceed\n",
    "to the implication that $g(p^a)=0$, where $a > 1$. \n",
    "\n",
    "\n",
    "- Consider $g(p)$: The Dirichlet sum has just two\n",
    "terms so we have $f(p) + g(p) = 0$. That is, $g(p) = -f(p)$. \n",
    "Now to increase the prime exponent from $1$ to $2$.\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "g * f |_{p^2} = g(1) \\cdot f(p^2) + \n",
    "g(p) \\cdot f(p) + \n",
    "g(p^2) \\cdot f(1) = f(p)^2 - f(p)^2 + g(p^2) = 0.\n",
    "\\end{align}$\n",
    "\n",
    "\n",
    "- This gives us $g(p^a)=0$ for $a=2$. \n",
    "Assuming $g(p^a)=0$ for $a=2, \\dots, n-1$. How about for $a=n$?\n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "g * f|_{p^n} = 1 \\cdot f(p^n) + (-f(p)) \\cdot f(p^{n-1}) + g(p^2) \\cdot f(p^{n-1}) \n",
    "+ \\dots + g(p^n) = 0 + g(p^n) = 0.\n",
    "\\end{align}$ \n",
    "\n",
    "\n",
    "- That is an induction proof that 'completely multiplicative' implies $g(p^a)=0$.\n",
    "\n",
    "\n",
    "- In the opposite direction we want $g(p^a)=0$ for $a \\ge 2$ to imply $f$ is \n",
    "completely multiplicative.\n",
    "\n",
    "\n",
    "- If $g(p^a)=0$ then as a special case $g(p^2)=0$ and by 2.25b:\n",
    "For any prime $p$ this is $f(p^2)-f(p)^2$;\n",
    "so the two terms are equal: $f(p^2)= f(p)^2$. \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Not quite &#x2610;\n",
    "\n",
    "#### 2.27 (a) If $f$ is completely multiplicative, prove that $f \\cdot (g*h) = (f \\cdot g) * (f \\cdot h)$ for all arithmetic functions $g$ and $h$.\n",
    "\n",
    "Here $f \\cdot g$ denotes a simple product: $(f \\cdot g)(n) = f(n) g(n)$.\n",
    "\n",
    "#### 2.27 (b) If $f$ is multiplicative and if the relation in (a) above holds for $g=\\mu$ and $h=\\mu^{-1}$, prove that $f$ is completely multiplicative.\n",
    "\n",
    "#### 2.28 (a) Incomplete:\n",
    "\n",
    "#### 2.28 (b) Incomplete:\n",
    "\n",
    "#### 2.29 Incomplete:\n",
    "\n",
    "#### 2.30 Incomplete:\n",
    "\n",
    "#### 2.31 Incomplete:\n",
    "\n",
    "#### 2.32 Incomplete:\n",
    "\n",
    "#### 2.33 Incomplete:\n",
    "\n",
    "#### 2.34 Incomplete:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2548684-bf94-4ec8-8978-18705b9977e0",
   "metadata": {},
   "source": [
    "#### 2.35  Incomplete:\n",
    "\n",
    "\n",
    "#### Möbius functions of order $k \\ge 1$\n",
    "\n",
    "Define $\\mu_k(n)$:\n",
    "\n",
    "\n",
    "Case 1: $\\mu_k(1) = 1$;\n",
    "\n",
    "\n",
    "Case 2: $\\mu_k(n) = 0$ when $p^{k+1}|n$ for some prime $p$;\n",
    "\n",
    "\n",
    "Case 3: $\\mu_k(n) = (-1)^r$ if $n=p_1^k\\cdot p_2^k \\cdot \\dots \\cdot p_r^k \n",
    "\\prod_{i>r}p_i^{a_i}$ for $0 \\lt a_i \\lt k$;\n",
    "\n",
    "\n",
    "Case 4: $\\mu_k(n) = 1$ otherwise.\n",
    "\n",
    "\n",
    "In comparative language (relative to $\\mu(n)$) we have the same $\\mu_k(1)=\\mu(1)=1$. \n",
    "$\\mu(n)=0$ when $n$ has a square divisor; and $\\mu_k(n)=0$ when\n",
    "$n$ has a *power-$(k+1)$* divisor. So far so good, now the more complicated bit. \n",
    "\n",
    "\n",
    "Suppose $n$ has $r$ divisors that are $k$-powers of some primes (and $n$ may \n",
    "have some additional prime divisors present as strictly less-than-$k$ powers): \n",
    "Then $\\mu_k(n)=(-1)^r$. (These \n",
    "additional divisors are inconsequential in the definition of $\\mu_k$ and they\n",
    "do not appear in $\\mu(n)$ as it is equivalen to $\\mu_{k=1}$. \n",
    "\n",
    "\n",
    "Finally (as an extension of $\\mu(1)=1$) if $n$ has no divisors that are $k$-powers\n",
    "or higher: $\\mu_k(n)=1$. Of course this is the same as $r=0$.\n",
    "\n",
    "\n",
    "The concluding five problems concern properties of $u_k$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2dd9af32-613b-4812-bee4-f71d84928c1d",
   "metadata": {},
   "source": [
    "#### 2.36 Show that for $k \\ge 1$ we have $\\mu_k(n^k) = \\mu(n)$\n",
    "\n",
    "\n",
    "Clearly $\\mu_1(n^1) = \\mu(n)$ so taking $k > 1$ in what follows:\n",
    "\n",
    "\n",
    "Case 1: $\\mu_k(1^k) = \\mu(1) = 1$: ok.\n",
    "\n",
    "\n",
    "Case 2: Suppose $n$ has a divisor that is a prime $p$ raised to a square-or-more power,\n",
    "say $p^{q \\ge 2}$. In this case $\\mu(n)=0$. Then $p^{nq} | n^k$ so $\\mu_k(n^k) = 0$\n",
    "as well: ok.\n",
    "\n",
    "\n",
    "Case 3: Suppose in contrast to Case 2 that \n",
    "$n$ is the product of $r$ primes raised to the $1$ power, \n",
    "$n = \\prod_{i=1}^r p_i$. Then $n_k = \\prod_{i=1}^r p_i^k$ and we have \n",
    "$\\mu(n) = (-1)^r = \\mu_k(n^k)$: ok. \n",
    "\n",
    "\n",
    "Case 4: All prime divisors of $n$ are present in $n^k$ in powers of $k$.\n",
    "That is, $n^k$ has no lower-than-k-power prime factors. This means the\n",
    "fourth case where $\\mu_k = 1$ will not occur for $n^k$: ok. $\\;\\;$ &#x2610; \n",
    "\n",
    "\n",
    "Chip's solution is an induction proof on $k$ which feels pretty rigorous; \n",
    "whereas my solution is a 'cases' argument based on possible structure for $n$.\n",
    "The extension from $\\mu$ to $\\mu_k$ and from $n$ to $n^k$ seems ok to me; \n",
    "but not sure about adequate rigor. Maybe I can find a \n",
    "mathematician to look it over. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3c589e9-2509-4974-b2d7-5611e3f12531",
   "metadata": {},
   "source": [
    "#### 2.37 Show that $\\mu_k(n)$ is multiplicative.\n",
    "\n",
    "\n",
    "As with **2.36** above: Case by case for $m$ and $n$ where $(m, n) = 1$. \n",
    "\n",
    "\n",
    "(Aside, by counterexample:\n",
    "$\\mu_k$ is not *completely* multiplicative: Take $m=p^a$ and $n=p^b$ with $a, b > 0$ and $a+b=k$.)\n",
    "\n",
    "\n",
    "For $m = 1$ we have $\\mu_k(m \\cdot n) = 1 \\cdot \\mu_k(n)$. For $m, n > 0$ and $(m, n) = 1$: \n",
    "\n",
    "- Case: $p^{(a>k)} \\; | \\; m \\implies \\mu_k = 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9d811b3-bb3d-4a5c-b0b1-2dda859a57ab",
   "metadata": {},
   "source": [
    "* Case: No $p^k \\; | \\; m, \\; n\\;\\;\\;$ so $\\;\\; \\mu_k(m \\cdot n) = 1 = \\mu_k(m) \\cdot \\mu_k(n)$ since\n",
    "the prime factor sets of $m$ and $n$ are mutually exclusive; so no higher powers appear in the\n",
    "prime factorization of $m \\cdot n$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac723ba2-0074-4f60-888c-8a98e0b8ecb7",
   "metadata": {},
   "source": [
    "* Case: $k$-powers are present in at least one of $m$ and $n$: Let's suppose respectively\n",
    "$q$ and $r \\; \\ge \\; 0$: Then\n",
    "$\\mu_k(m \\cdot n) = (-1)^{q + r} = \\mu_k(m) \\cdot \\mu_k(n)\\;\\;\\;\\;\\;\\;\\;\\;\\;$ &#x2610;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "286b45e8-737f-44eb-9068-d947e8ff9059",
   "metadata": {},
   "source": [
    "####  2.38  Show that if $k \\ge 2$ then \n",
    "\n",
    "\n",
    "$\\begin{align}\n",
    "\\mu_k(n) = \\sum_{d^k|n} \\mu_{k-1}\\bigl( \\frac{n}{d^k} \\bigr) \\mu_{k-1}\\bigl( \\frac{n}{d} \\bigr)\n",
    "\\end{align}$\n",
    "\n",
    "* Case $n=1$: Check, everything is $1$.\n",
    "* Case $p^{k+1} \\; | \\; n$: We have $0 \\; = \\; 0$ as follows:\n",
    "\n",
    "\n",
    "Left side: $\\mu_k(n) = 0$. Right side: For every $d$ with $d^{k}|n$: The corresponding $n/d$ argument\n",
    "of $\\mu_{k-1}$ contains a factor $p^k$. Hence $\\mu_{k-1} \\left( \\frac{n}{d} \\right) = \n",
    "\\mu_{k-1} \\left( \\alpha \\cdot p^k \\right) = 0$.\n",
    "\n",
    "* Case $n$ contains $r$ factors $p^{k}$\n",
    "\n",
    "Left off here."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "563e12b6-9f27-41cf-9144-73a04c90759e",
   "metadata": {},
   "source": [
    "#### 2.39  Incomplete: Show that if $k \\ge 1$ then \n",
    "\n",
    "\n",
    "$$\\bigl| \\mu_k(n) \\bigr| = \\sum_{d^{k+1}|n}\\mu(d).$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16609b29-cf22-4c33-9f12-bc53f124005e",
   "metadata": {},
   "source": [
    "#### 2.40 Complete: Show that for each prime $p$ the Bell series for $u_k$ is given by\n",
    "\n",
    "\n",
    "$$(\\mu_k)_p(x) = \\frac{1-2x^k+x^{k+1}}{1-x}.$$\n",
    "\n",
    "\n",
    "This is interesting as the choice of prime $p$ evaporates from the end result.\n",
    "\n",
    "\n",
    "The Bell series of $\\mu_k \\textrm{ mod } p$ is defined in this case\n",
    "\n",
    "\n",
    "$$(\\mu_k)_p(x) = \\sum_{n=0}^{\\infty} \\mu_k(p^n)x^n.$$\n",
    "\n",
    "\n",
    "What follows is valid for $k=1$ but is written more in the spirit of $k>1$. \n",
    "The argument of the infinite sum becomes zero when $n$ exceeds $k$\n",
    "so the sum can be truncated at $k$; and then rewritten in a more concrete form: \n",
    "\n",
    "\n",
    "$$(\\mu_k)_p(x) = \\sum_{n=0}^{k} \\mu_k(p^n)x^n = 1 + x + \\sum_{n=2}^{k} \\mu_k(p^n)x^n.$$\n",
    "\n",
    "\n",
    "The prime $p$ is raised to a value less than $k$ for most of this sum, i.e. $\\mu_k = 1$;\n",
    "and the final term $n=k$ resolves to $(-1)^1$:\n",
    "\n",
    "\n",
    "$$(\\mu_k)_p(x) = \\sum_{n=0}^{k} \\mu_k(p^n)x^n = 1 + x + \\sum_{n=2}^{k-1} x^n - x^k.$$\n",
    "\n",
    "\n",
    "Observing the pattern:\n",
    "\n",
    "\n",
    "$$k=1: (\\mu_k)_p(x) = 1-x$$\n",
    "\n",
    "\n",
    "$$k=2: (\\mu_k)_p(x) = 1 + x - x^2$$\n",
    "\n",
    "\n",
    "$$k=3: (\\mu_k)_p(x) = 1 + x + x^2 - x^3$$\n",
    "\n",
    "\n",
    "$$k=4: (\\mu_k)_p(x) = 1 + x + x^2 + x^3 - x^4$$\n",
    "\n",
    "\n",
    "$$k:(\\mu_k)_p(x) = 1 + x + x^2 + \\dots + x^{k-1} - x^k$$\n",
    "\n",
    "\n",
    "In the spirit of a telescoping series: Multiply the last (general) expression above by $1-x$: \n",
    "\n",
    "\n",
    "$$(1-x) \\cdot (1 + x + x^2 + \\dots + x^{k-1} - x^k) =  \n",
    "1 + x + x^2 + \\dots + x^{k-1} - x^k - x - x^2 - x^3 - \\dots - x^{k-1} - x^{k} + x^{k+1} = 1 - 2x^k + x^{k+1}.$$\n",
    "\n",
    "\n",
    "So the general expression can be written \n",
    "$1 + x + x^2 + \\dots + x^{k-1} - x^k = \\frac{1 - 2x^k + x^{k+1}}{1-x} = (\\mu_k)_p(x).\\;\\;$ &#x2610;\n",
    "\n",
    "Well that was certainly a long road! On to chapter 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "218e4dd2-9871-4df5-b355-fb3128af0a8f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0494da35-33dd-4b00-bfb1-ffe609d75899",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}