3
$\begingroup$

I wrote a small python script to calculate a number's digit-sum (i.e #152 = 1 + 5 + 2 = 8) after being raised to various powers. Then I noticed certain numbers are dramatically more common than others, while others don't occur at all.

For example, after iterating through the numbers 1-1000, each being raised to the 1-100th power, not once did a digit-sum of 3 or 6 occur, whereas 1 and 9 occur tens of thousands of times. Below are the output results;

i: 0 | Count: 0
i: 1 | Count: 27178
i: 2 | Count: 3547
i: 3 | Count: 0
i: 4 | Count: 10862
i: 5 | Count: 3546
i: 6 | Count: 0
i: 7 | Count: 10862
i: 8 | Count: 9208
i: 9 | Count: 32601

And here's a github link to the python script I wrote; https://github.com/Your-Pal-Al/Digit_Sum_Exp/blob/322846f690b8fdac9b600150de8887d7e25a734a/digit_sum_exp.py

EDIT: Fixed script loop logic errors

$\endgroup$
2
  • $\begingroup$ @Troposphere In OP's Python script they start from powers of 2. $\endgroup$ Jul 29 at 23:51
  • 1
    $\begingroup$ Well, if $k$ is a multiple of $3$ then $k^{100}$ is a multiple of $9$ so the digit sum will be $9$. If $k$ is not a multiple of $3$ then $3^{100}$ isn't either and the sum of the digits will not be $3, 6$ or $9$. So $\frac 13$ of the digits will be $9$ and $3$ and $6$ will never occur. $\endgroup$
    – fleablood
    Jul 30 at 1:29
5
$\begingroup$

First, your script doesn't really "iterat[e] through the numbers 1-1000, each being raised to the 1-100th power". Because you never reset the $x$ variable between runs of the inner loop, you're actually computing $(a+2)^{\lfloor a/98\rfloor+2}$ for $0<a<998\cdot 98$.

This creates some minor differences with the nice counts you would get if you were looping $x$ and $y$ independently from $2$ to $999$ and $2$ to $99$. Never mind, the overall pattern is broadly speaking the same.


The iterated digit sum of a positive integer is none other than the remainder when dividing the original number by $9$, except when the remainder is $0$ the digit sum is $9$ instead. This is the basis for casting out nines.

Now whenever $x$ in $x^y$ was divisible by $3$ and $y\ge 2$, then $x^y$ is divisible by $3^2=9$, so all those cases (about a third of all) yield the digit sum $9$. On the other hand, $x^y$ cannot be divisible by $3$ unless $x$ is divisible by $3$, so digit sums of $3$ or $6$ are impossible.

When $x$ is not divisible by $3$ it is coprime to $9$, and therefore Euler's theorem says that $x^y\equiv 1 \pmod 9$ whenever $y$ is a multiple of $\varphi(9)=6$. Of course, the remainder is also $1$ when $x\equiv 1 \pmod 9$ no matter what $y$ is. This creates a clear overweight of $1$ among the sums.

Finally, a square modulo $9$ is always one of $\{0,1,4,7\}$ -- and $x^y$ is a square whenever $y$ is even. This explains why you see $4$ and $7$ more often than $2$, $5$, or $8$. On the other hand, a cube modulo $9$ is always one of $\{0,1,8\}$, so when $y\equiv 3\pmod 6$, a third of the $x$ values produce $8$, explaining why $8$ is more popular than $2$ and $5$.


We can also count the popularity of each residue directly by writing up a table: $$ \begin{array}{r|cccccc} y = & 6n+6 & 6n+7 & 6n+2 & 6n+3 & 6n+4& 6n+5 \\ \hline 0^y \bmod 9 = & 0 & 0 & 0 & 0 & 0 & 0 \\ 1^y \bmod 9 = & 1 & 1 & 1 & 1 & 1 & 1 \\ 2^y \bmod 9 = & 1 & 2 & 4 & 8 & 7 & 5 \\ 3^y \bmod 9 = & 0 & 0 & 0 & 0 & 0 & 0 \\ 4^y \bmod 9 = & 1 & 4 & 7 & 1 & 4 & 7 \\ 5^y \bmod 9 = & 1 & 5 & 7 & 8 & 4 & 2 \\ 6^y \bmod 9 = & 0 & 0 & 0 & 0 & 0 & 0 \\ 7^y \bmod 9 = & 1 & 7 & 4 & 1 & 7 & 4 \\ 8^y \bmod 9 = & 1 & 8 & 1 & 8 & 1 & 8 \end{array} $$

Counting instances of each result in this table you should match up your experimental frequencies pretty well. (Each of the cells is hit by about $\frac{98\cdot 998}{54}\approx 1811$ of your test cases).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.