The Renewal Equation

A math odyssey

More Digit Sums

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$.

,

Responses

  1. Olly

    Actually, it’s not necessary that $n>1$ here. That’s left over from a somewhat different form of the proposition that I worked with initially.

    Reply
  2. Tim McL

    My father’s mother was a HS math teacher. (She started out to major in German, but when WWI started the German major went away and she switched to Math.) She used to talk about “casting out nines” as a way to check arithmetic you were doing by hand, which was obviously the only way to do arithmetic on those days. (OK, there were abaci, and Pascal had a simple mechanical calculator as early as around 1650, so I’m exaggerating.)

    I think the idea was to replace the numbers you were adding or multiplying with their digit sums and to replace the calculation with the digit sums, which are normally much smaller. Repeat until you have single digit mumbers. Do the calculation on these digit sums, and compare the digit sum of the result with the digit sum of your answer using the original large number. These sums should differ by a multiple of 9. If you made an arithmetic error, you have only one chance in 9 of getting the right digit sum, so you’re pretty likely to detect (though not correct) the error.

    At least, I assume that’s how casting out nines worked. For my grandmother, it was just something everybody knew, and I was sheepish about confessing that I didn’t.

    Reply
    1. Olly

      I will have to look into that. There are number of math-related things I feel a bit sheepish that I don’t know, such as how to compute square roots by hand. I keep meaning to sit down and learn that but never do.

      Reply
  3. Tim McL

    In high school I found an old book that had an algorithm something like long division but, ummm, longer, for computing square roots. I used it a few times and programmed a computer to use it, but I never understood it (not did I try).

    That might be fun to dig up, but what’s much more useful and astounding is to use Newton’s Method. It’s a technique for approximating roots of a polynomial, and computing $\sqrt a$ is just solving the polynomial $x^2-a=0$. The amazing thing about applying Newton’s Method to a quadratic is that each iteration doubles the number of correct digits. (I’m lying very slightly here, but we’re friends, right?) So if you know 1 digit of $\sqrt a$, and you use Newton, then you know 2 digits, then 4, then 8, then 16, 32, 64, etc. I’d be very surprised if the long-division-like algorithm in my grandmother’s old book had this dazzling convergence behavior.

    Reply

Leave a Reply to Tim McL Cancel reply

Your email address will not be published. Required fields are marked *