The digit sum: $s(na)=s(nb)$ - MathOverflow

The digit sum: $s(na)=s(nb)$

2012-04-20T11:23:35Z

Not that I was serious about the following question, but I think it is a must-to-ask as a follow-up to this MO post.

For integer $n\ge0$, let $s(n)$ denote the sum of the digits in the decimal representation of $n$.

Is it true that for any integer $a,b>0$, the ratio of which is not a power of $10$, the set of all those $n\ge 0$ with $s(an)=s(bn)$ has zero density?

Answer by fedja for The digit sum: $s(na)=s(nb)$

2012-04-20T13:07:19Z

OK, by Seva's request I'm getting somewhat more serious :) Fix $a$, $b$. Take large $M$ to be chosen shortly. Take a $3MN$ digit number $n$ (something from $0$ to $10^{3MN}-1$, written with head zeroes if necessary) and split its decimal representation into pieces of length $3M$ where $M$ is large but fixed. Let us call these $3M$-digit pieces $n_k$ so $n=\sum_{k=0}^{N-1}10^{3Mk}n_k$. Consider $n_k$ as independent random variables uniformly distributed in the set $\{0,1,2,\dots,10^{3M}-1\}$. By the law of large numbers, with probability close to $1$, there are about $N\cdot 10^{-2M}$ pieces $n_k$ that start and end with $M$ zeroes (with the middle $M$ digits being anything). Call the numbers $n$ that satisfy this property typical. The typical numbers can be split into groups according to exactly which $k$ correspond to such pieces (denote by $K$ the set of all such $k$) and what number is formed by the digits outside these groups (that number is $n'=\sum_{k\notin K}10^{3Mk}n_k$). We need to show that in each group $G=G(K,n')$ of typical numbers the portion of the solutions is small.

As Fedor explained, if $M$ exceeds the number of digits in $a$, we have $s(an)=s(an')+\sum_{k\in K}s(an_k)$ and similarly for $b$. Thus $$ s(an)-s(bn)=s(an')-s(bn')+\sum_{k\in K}X_k $$ with $$ X_k=s(an_k)-s(bn_k) $$ The random variables $X_k$ are i.i.d. and their distribution is completely determined by $a,b$, and $M$.

Suppose that the equality $s(an)=s(bn)$ fails for at least one $n\ge 0$. Then (since it holds for $n=0$) $X_k$ is not a constant for sufficiently large $M$ and we can use the following

Probabilistic Claim. If $X$ is any fixed integer-valued random variable with finitely many values that is not constant, then $\lim_{Q\to\infty}\sup_{S\in\mathbb Z} P\{\sum_{k=1}^Q X_k+S=0\}=0$ where $X_k$ are i.i.d. random variables equidistributed with $X$.

Since the cardinality $Q$ of $K$ for every typical group is huge when $N$ is large enough, we conclude that the above displayed equation has very little chance to hold in every typical group $G(K,n')$ and, thereby, overall.

However, if $s(an)=s(bn)$ for all $n$, then $a$ and $b$ differ only by the number of zeroes in the end.

I apologize if this edit rendered some comments meaningless.

Answer by Aaron Meyerowitz for The digit sum: $s(na)=s(nb)$

2012-04-20T18:52:14Z

I don't follow fedja's proof. I'd guess that $s(n)=s(2n)$ might have positive density. My reasoning is vague: $2n$ is equally likely to have digit sum above as below $n$. Of course it is better to look $s(9n)=s(18n)$ since those are the only possible matches. Again the distribution is symmetric and now heavily clustered about 0. As I say, weak.

Random experiments show possible patterns and do provide some support. Example: Density in [b,b+9999] for b a random 100 digit integer. It is frequently 0 but also frequently over half.

However it may be the law of small numbers. It could be that the density decreases like $0.95^{\ln{x}}$

Answer by Gjergji Zaimi for The digit sum: $s(na)=s(nb)$

2012-04-20T23:32:43Z

You can find some explicit asymptotics in a paper by J. Schmidt, "The joint distribution of the binary digits of integer multiples". He considers base $2$, and theorem 1.2 says that for any $a,b$ odd and arbitrary integer $k$. $$|\lbrace 0\le n\le x: s(na)-s(nb)=k\rbrace|=\frac{x}{\sqrt{2\pi V\cdot \log_2x }}e^{-\frac{k^2}{2V\log_2 x}}+O(\frac{x}{\log x}),$$ where $V=\frac{1}{2}\left(1-\frac{\gcd^2(a,b)}{ab}\right)$. Something similar should work for any base.