Go Back > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Thread Tools
Old 2021-07-20, 15:34   #1
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

10100000010112 Posts
Default A real thread about digit sums

Here, [x] is the integer floor of x, n is a positive integer, and b is an integer greater than or equal to 2. The base-b digits of n can be computed by repeated integer division with quotient and remainder:

n = b*[n/b] + d0,

[n/b] = b*[n/b2] + d1

[n/b2] = b*[n/b3] + d2


where 0 <= dk <= b-1

For a given n, this process terminates in a finite number of steps, the number of steps being about log(n)/log(b).

Then we have n = d0 + d1*b + d2*b2 + ...

Note: The fact that [n/b2] = [[n/b]/b] etc is left as an exercise for the reader.

Adding the two sets of equations, we have

n + [n/b] + [n/b2] + ... = b*([n/b] + n/b2] + ...) + d0 + d1 + ...

n - (d0 + d1 + ...) = (b-1)*([n/b] + [n/b2] + ...)

When b = ten, this relation makes explicit that n differs from the sum of its decimal digits by a multiple of 9 (it gives the multiplier). This fact is the basis for the long-used process of "casting out nines," which was used to check arithmetic operations by (in effect) checking them modulo 9. If we used base three, we could check arithmetic operations by "casting out twos."

It is not hard to show another formulation of the base-b generalization of "casting out nines." If m and n are positive integers, the sum of the base-b digits of m plus the sum of the base-b digits of n, minus the sum of the base-b digits of (m + n), is (b-1) times the number of carries in the addition.

When the base b = p, a prime number, the sum [n/p] + [n/p2] + ... is the exponent of the p-power factor of n! (factorial n).

Combining the previous observations, we can deduce that if p is a prime number, then the power of p which divides the binomial coefficient m+n choose m (or m+n choose n) is the number of carries in the base-p addition m + n. In particular, when m > 0, n > 0, and m+n is a power of p, there is always at least one carry in the base-p addition m + n. So pk choose m is divisible by p if 0 < m < pk.

Another sort of question about digit sums is, the distribution of values among numbers with a given number of base-b digits. There are b-1 base-b integers with 1 base-b digit; b*(b-1) with two, b2*(b-1) with three, and so on. It is easily shown by induction that the average digit sum of k-digit numbers to the base b is

k*(b-1)/2 + 1/2.

There is a formula of sorts for the number of blocks of k base-b digits with a given sum n. Namely, the coefficient of xn in


The block of k 0's corresponds to the term 1, and the block of k b-1's to x(b-1)*k. One can use this formula for k-1 digits, and prepend with the digits 1 to b-1, for positive integers with k base-b digits.

When b = 2, we get the binomial coefficients. We would thus expect the sum of binary digits of k-digit numbers to base 2 to be strongly concentrated areound the average.

From looking around online, it seems that something similar happens with digit sums of k-digit numbers to any base.

As to digit sums of primes greater than the base b, the final base-b digit must be relativley prime to b, and the digit sum itself must be relatively prime to b-1. In particular, for base ten, the ones digit of a prime greater than ten can only be 1, 3, 7, or 9; and the digit sum can not be divisible by 3.

Apart from that, I would guess that the digit sums of primes with a given number of decimal digits are probably concentrated around the average.

Last fiddled with by Dr Sardonicus on 2021-07-23 at 12:59 Reason: xingif posty;reformat exponents
Dr Sardonicus is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Digit sums, of any value? Chris65 Miscellaneous Math 4 2021-02-21 15:23
Find Kaprekar's constants and cycles of the Kaprekar mapping of 9-digit to 12-digit numbe in base 12 sweety439 Computer Science & Computational Number Theory 0 2020-02-11 03:12
real-life pictures thread ixfd64 Lounge 38 2011-10-17 23:24
160 digit factor found of 366 digit (PRP-1) AntonVrba Factoring 7 2005-12-06 22:02
Fibonacci sums? TTn Math 2 2002-10-25 21:47

All times are UTC. The time now is 01:31.

Sat Dec 4 01:31:53 UTC 2021 up 133 days, 20 hrs, 0 users, load averages: 0.93, 1.50, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.