3

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

A. Salas
  • 41
  • @Troposphere In OP's Python script they start from powers of 2. – Jair Taylor Jul 29 '21 at 23:51
  • 1
    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. – fleablood Jul 30 '21 at 01:29

1 Answers1

6

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

Troposphere
  • 7,158