A math odyssey
I’ve been quite depressed today. The change in my medication may not be working out. Nevertheless, I worked on more exercises from the calculus book’s review of trigonometry. They were pretty basic and didn’t spark any interesting thoughts to share, but I did get to use my dandy compass.
Today I read more about trigonometry, both in the appendix of my calculus textbook and in OpenStax’s Algebra and Trigonometry. (The calc book does not discuss the Unit Circle, the Law of Sines, the Law of Cosines, or for some mysterious reason, the half-angle trig identities.) I also started on the calc book’s review exercises. Depending on how I feel after finishing those, I may do some of the exercises from Algebra and Trigonometry. It has a lot of applied problems that look as if they might be interesting.
I thought that today I would share the other fruit of my investigation of digit sums. I actually proved this proposition before the one from yesterday, but I didn’t have the energy to write it up. I originally found it in my notebook stated for base 10 only, but it occurred to me that it applied to other bases, as well. (Other than that, it’s not all that interesting.)
Proposition: In base $n>1$, if $m$ is a natural number then the digit sum of $m$ is less than or equal to $m$.
If $m$ is a natural number, then $m=n^md_m+n^{m-1}d_{m-1}+…+nd_1+d_0$ where $d_m, d_{m-1},…,d_1, d_0$ are the digits, in order, of $m$ expressed in base $n$.
The digit sum of $m$, expressed in base $n$, is $d_m+d_{m-1}+…+d_1+d_0$.
Since $n>1$, $d_p<n^pd_p$ for all $p\in\mathbb{N}$.
It follows that $d_m+d_{m-1}+…+d_1+d_0\leq n^md_m+n^{m-1}d_{m-1}+…+nd_1+d_0\text{.}$
Therefore, the digits sum of $m$ is less then or equal to $m$.
I didn’t do any trigonometry today, but instead read more of Steven Strogatz’s The Joy of X and worked on the propositions about digit sums that I found in my notebook.
The most interesting tidbit from The Joy of X was Strogatz’s comment regarding a particular proof of the Pythagorean Theorem that, “The proof does far more than convince; it illuminates. That’s what makes it elegant.” That caught my attention and had me wondering whether all elegant proofs must be illuminating. I haven’t come to a conclusion yet.
To be illuminating is certainly not the only requirement for an elegant proof. The main proposition I worked on today was “the sum of the digits of any multiple of 9 is also a multiple of 9.” I came up with the outline of a proof by induction, the meat of which was a description of what happens to the digit sum when you add 9 to any natural number. It was full of cases and loops and was decidedly not elegant. I do think it gave a good sense of what was happening, though, and it could have been reworked to prove the general theorem that, in base $n$, the digit sum of any multiple of $n-1$ is also a multiple of $n-1$.
I was sure there must be a better proof, however, and I ended up searching for guidance on the Internet. I regret that, as I would rather have discovered the answer I found for myself. I did get to generalize it, at least, since it applied only to two-digit numbers. I’m not sure I would say that the result is illuminating. I don’t think it reveals why the theorem is true, except in as much as “why” is that 9 is one less than the base of the number system being used. It is simple, though. Does that make it elegant?
Proposition: For all $n\in\mathbb{N}$, the digit sum of $9n$ is a multiple of 9.
When $n$ is a natural number, $9n = 10^md_m+10^{m-1}d_{m-1}+…+10d_1+d_0$, where $d_m, d_{m-1},…,d_1, d_0$ are the digits of $9n$, in order.
$$10^md_m+10^{m-1}d_{m-1}+…+10d_1+d_0=$$ $$\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]+\left[d_m+d_{m-1}+…+d_1+d_0\right]$$
Thus, $$d_m+d_{m-1}+…+d_1+d_0=9n-\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]\text{.}$$
Note that the left-hand side of the equation is the digit sum of $9n$.
Note also that, for any natural number $x$, $$10^x-1=\sum_{i=0}^{x-1}10^i(9)=9\sum_{i=0}^{x-1}10^i\text{.}$$
[For instance, $10^3-1=1000-1=999=9(111)$.]
Hence, because each term of the expression is a multiple of 9, $$9n-\left[\left(10^m-1\right)d_m+\left(10^{m-1}-1\right)d_{m-1}+…+(10-1)d_1\right]=9p$$ for some integer $p$.
It follows that the digit sum of $9n$ is a multiple of 9 for all $n\in\mathbb{N}$.
This proof could also be rewritten to cover all bases. In addition, the same argument could be used to prove that, in base 10, the digit sum of any multiple of three is also a multiple of three.
(And it occurs to me as I write this that you could also use it to prove the analogous fact, in base $n$, for any factor of $n-1$. That’s very cool and makes me feel like I have come up with something worthwhile on my own today.)
Sometimes, during my review, my mind will supply facts before they are mentioned or even in contexts where they never are mentioned. Other times, I will read something an think, “Wait, did I ever know that?”
Today I read about trigonometry, both in the appendix to my calculus text and in the OpenStax free textbook Algebra and Trigonometry. It turns out that, when an angle’s vertex is located at the center of a circle, the measure of that angle in radians is the ratio between the length of the arc subtended by the angle and the radius of the circle. That’s not just a property of radians; that’s what a radian is. Surely I must have known that at some point, but it came as total news to me.
(I’m feeling better today, though still not very good. The fun math revelations were helpful. All that I did remember about radians now makes a lot more sense.)
Today I worked through poor concentration to finish the exercises from the review of conics. There wasn’t much left to do, in fact, because the five final exercises all called for tools from calculus that I have not reviewed yet.
Next up will be trigonometry. I didn’t start reading the appendix on that topic today, but I looked over it. I also did a little review of the Unit Circle (which, oddly, isn’t pictured in the review of trigonometry). I remember Mike, my high school math teacher for two out of three years, was very strong on the Unit Circle. He used to say that if he ever met us again as adults, his first question would be, “What’s $\sin\left(\frac{\pi}{6}\right)$?” I did remember the answer to that before my review today, so perhaps threatening years-late pop quizzes is an effective teaching technique.
I reckon it’s about time I present my hand-waving argument that repeating decimals must represent rational numbers. I proved the converse in my post Rational-a-Rama with what I think most of my audience found a boring amount of rigor. Here I’m going to err far on the other side.
Consider the repeating decimal $x=0.\overline{142857}$.
Since $x$ repeats every six digits, multiplying $x$ by $10^6$ will yield another number with the same decimal part: $10^6x=142857.\overline{142857}$
Observe that $10^6x-x=142857.\overline{142857}-0.\overline{142857}=142857$.
Thus $(10^6-1)x=142857$ and $x=\frac{142857}{10^6-1}=\frac{142857}{999999}\text{.}$
Both $142857$ and $999999$ are integers, so it follows that $x=0.\overline{142857}$ is rational.
(In fact, $x=0.\overline{142857}=\frac{142857}{999999}=\frac{1}{7}$.)
A similar argument can be made about any repeating decimal, so any repeating decimal represents a rational number.
(Note that some repeating decimals do not begin repeating right after the decimal point. An example is $y=0.58\overline{3}$ (which is $\frac{7}{12}$). Multiplying $y$ by ten and subtracting $y$ from the result yields $10y-y=5.83\overline{3}-0.58\overline{3}=5.25$. This is not an integer, but it can be made one by multiplying by 100. This leaves the equation $100(10y-y)=525$, which can be used to show that $y$ is rational in the same manner as above.)
Today I read more of The Joy of X. Things are disrupted right now because my medications are being changed, causing me a lot of withdrawal symptoms. It’s frustrating that my functioning is so dependent on the levels of these chemicals, but it isn’t news. After all, this whole project was made possible by my discovery of the CBD, on the heels of an improvement in my prescribed medication.
I hoped I might finish the exercises from the review of conics today, but I am still feeling under the weather, so I didn’t push that. Instead I read some of The Joy of X by Steven Strogatz and poked around in the same old notebook where I unearthed the problem about superprimes. There I found a nifty, non-inductive proof that $\sum_{i=0}^{n-1}x^i=\frac{x^n-1}{x-1}$, which is a theorem from the first chapter of Number Theory by George E. Andrews, where it is proven by induction.
I also found two unproven propositions about digit sums and the question, “What is the pattern of the sums of digits for multiples of 9?” I worked a bit on the latter, but couldn’t make much of the results. That led me to look them up in the On-Line Encyclopedia of Integer Sequences, a resource I’d heard of but never before used. The sequence I was working with didn’t prove to have any very interesting properties, but I found some others I want to look into further, such as the binary weight of $n$ and the sequence $n$ minus the sum of the digits of $n$, the terms of which are always multiples of 9.1 (Whoa.) I’ll have to be careful, though. The OEIS looks worse than Wikipedia or even TV Tropes for trapping in the unwary browser.
I’ve been feeling unwell since early afternoon, so I’m not going to post about the converse of Wednesday’s theorem today. I did manage a couple of hours’ study this morning. I’m getting near the end of the exercises from the review of conics.
Today I worked on some interesting applied exercises in the review of conics, as well as finishing a problem set in Analysis with an Introduction to Proof. I also spent some time thinking about a challenge problem that I found copied into one of my notebooks:
Problem of the Week #793 by Stan Wagon
A superprime is an integer (such s 7331) such that all of its left-to-right initial segments are prime. (For 7331, the segments are 7, 73, 733, and 7331, all prime.) There is largest superprime. Find it.1
I had done some work on the problem during one of my abortive stabs at doing math again. My approach was to try to prove that there is a largest superprime as a step toward constructing it. The work I did to that end is interesting, but I don’t know yet whether I can get beyond the place I got stuck before. Possibly finding the largest superprime empirically, then proving that it must be the largest would be more fruitful.
Today I will be sharing my proof that the decimal representations of rational numbers must repeat. This proof is based on a simple idea, but turned out to be pretty involved, with several parts.
The fundamental idea can be illustrated using long division. Consider the rational number $\frac{8}{7}$. We can find its decimal representation using the long division calculation below.
Each step of this calculation begins with the remainder from the previous step (circled in red). Since the remainder on division by 7 must be an integer between 0 and 6, there are only 7 possible remainders. Thus, the remainder must repeat within no more than 8 steps. Once it repeats, the calculation will begin to cycle, causing the decimal representation it produces to repeat, as this one does.
Now let’s prepare for the more formal proof by proving two lemmas. I think the first of these is quite interesting and not immediately obvious. The second one is obvious, but I wanted to be assured of it, since it is vital to the main proof.
Lemma 1: Given a rational number $x$, if there exist two distinct digits $d_1$ and $d_2$ in the decimal representation of $x$ such that the sequence of digits following $d_1$ is the same as the sequence of digits following $d_2$, then the decimal representation of $x$ repeats.
Assume that two such digits exist and let the one which appears first be called $d_1$. Then the decimal representation of $x$ begins as follows: $s_1.s_2d_1s_3d_2$, where $s_1$ is a sequence of at least one digit and $s_2$ and $s_3$ are sequences of zero or more digits.
Now, since the sequence of digits following $d_2$ is the same as the sequence of digits following $d_1$, the decimal representation must continue: $s_1.s_2d_1s_3d_2s_3d_2$. Yet this further specifies the sequence of digits following $d_1$, so the same digits must appear again in the sequence following the initial appearance of $d_2$, yielding $s_1.s_2d_1s_3d_2s_3d_2s_3d_2$. This process (illustrated below) will continue infinitely, so $x=s_1.s_2d_1\overline{s_3d_2}$.
Thus, the lemma holds.
(I realize the notation was a little sloppy here, with $d_2$ representing both a digit and a digit with its position, but I couldn’t find a good way to fix it.)
Lemma 2: Let $x$ be a non-negative rational number such that $x=\frac{n}{m}$, where $n$ and $m$ are non-negative integers and $m\neq 0$. There is no more than one way to represent $x$ as a mixed number $q\frac{r}{m}$ such that $q$ and $r$ are non-negative integers and $r<m$.
Suppose $\frac{n}{m}=q_1\frac{r_1}{m}$ and $\frac{n}{m}=q_2\frac{r_2}{m}$ where $q_1$, $q_2$, $r_1$, and $r_2$ are non-negative integers and $r_1,r_2<m$.
It follows that $q_1+\frac{r_1}{m}=q_2+\frac{r_2}{m}$ and thence that $q_1-q_2=\frac{r_1-r_2}{m}$.
Since $0<r_1<m$ and $0<r_2<m$, $-1<\frac{r_1-r_2}{m}<1$.
Thus $-1<q_1-q_2<1$, from which it follows that $q_1=q_2$, since $q_1$ and $q_2$ are integers.
Hence $\frac{r_1-r_2}{m}=0$, so $r_1=r_2$.
Therefore, both mixed numbers are the same, and the theorem holds.
Finally, we come to the main theorem.
Proposition: If $x$ is a rational number, then the decimal representation of $x$ repeats.
For any $x$, if the decimal representation of $x$ repeats, then the decimal representation of $-x$ repeats. Thus, it is sufficient to show that the theorem holds for all non-negative $x$.
Let $x$ be a non-negative rational number. Then $x=\frac{n}{m}$ for some non-negative integers $n$ and $m$, where $m\neq 0$.
The fraction $\frac{n}{m}$ can be expressed as a mixed number $q_1\frac{r_1}{m}$ such that $q_1$ and $r_1$ are non-negative integers and $r_1<m$. By Lemma 2, there is only one way to do this.
Using algebra we have: $$q_1\frac{r_1}{m}=q_1+\frac{r_1}{m}=q_1+\frac{r_1}{m}\left(\frac{10}{10}\right)=q_1+\frac{10r_1}{m}\left(\frac{1}{10}\right)$$
As above, the fraction $\frac{10r_1}{m}$ can be expressed uniquely as a mixed number $q_2\frac{r_2}{m}$ such that $q_2$ and $r_2$ are non-negative integers and $r_2<m$.
This yields $$q_1+\frac{10r_1}{m}\left(\frac{1}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)\text{.}$$
Notice that $q_2$ has only one digit, since $0\leq\frac{r_1}{m}<1$ and $0\leq q_2\leq\frac{10r_1}{m}$. Notice also that $0\leq\frac{r_2}{m}\left(\frac{1}{10}\right)<\frac{1}{10}$, since $0\leq\frac{r_2}{m}<1$. This means that $q_2$ is the tenths-place digit of the decimal expansion of $x$.
The algorithm can be continued as shown below, $$q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)\left(\frac{10}{10}\right)$$ $$=q_1+q_2\left(\frac{1}{10}\right)+\frac{10r_2}{m}\left(\frac{1}{100}\right)=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+\frac{r_3}{m}\left(\frac{1}{100}\right)$$ $$=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+\frac{r_3}{m}\left(\frac{1}{100}\right)\left(\frac{10}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+q_4\left(\frac{1}{1000}\right)+\frac{r_4}{m}\left(\frac{1}{1000}\right)…$$ with $q_i\frac{r_i}{m}$ for $i>1$ always the unique mixed number representation of the fraction $\frac{10r_{i-1}}{m}$ such that $q_i$ and $r_i$ are non-negative integers and $r_i<m$. By logic similar to that above, when $i>1$, $q_i$ will always be a digit of the decimal representation of $x$, with its value given by the power of $\frac{1}{10}$ by which it is multiplied.
Since, for all $i$, $r_i$ is a non-negative integer less than $m$, there are only $m$ possible values of $r_i$. This means that, among the infinite values of $r_i$, there must exist distinct $r_j$ and $r_k$ such that $r_j=r_k$. (ETA: By the Pigeonhole Principle!)
Since the mixed number representations used by the algorithm are unique, if $r_j=r_k$, then $q_{j+1}=q_{k+1}$ and $r_{j+1}=r_{k+1}$. By induction, it therefore follows that $q_{j+h}=q_{k+h}$ for all $h$. Since, when $i>1$, each $q_i$ is a digit of the decimal representation of $x$, it follows by Lemma 1 that decimal representation of $x$ repeats.
Therefore the theorem holds.
I hope this makes some measure of sense. I had a lot of trouble making this proof lucid, and eventually I had spent too much time working on. Those whose eyes did not glaze over will note that the algorithm I employed here is essentially long division. In developing it, I did not set out specifically to reproduce the long division algorithm, and I was intrigued when I noticed they are basically the same. Here is our long division problem annotated to show the relationship:
