The digit sum: $s(na)=s(nb)$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T04:36:15Z http://mathoverflow.net/feeds/question/94625 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94625/the-digit-sum-snasnb The digit sum: $s(na)=s(nb)$ Seva 2012-04-20T11:23:35Z 2012-06-17T19:16:19Z <p>Not that I was serious about the following question, but I think it is a must-to-ask as a follow-up to <a href="http://mathoverflow.net/questions/94525/equal-digit-sums" rel="nofollow">this MO post</a>. </p> <p>For integer $n\ge0$, let $s(n)$ denote the sum of the digits in the decimal representation of $n$.</p> <blockquote> <p>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? </p> </blockquote> http://mathoverflow.net/questions/94625/the-digit-sum-snasnb/94638#94638 Answer by fedja for The digit sum: $s(na)=s(nb)$ fedja 2012-04-20T13:07:19Z 2012-04-20T21:28:46Z <p>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.</p> <p>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$.</p> <p>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 </p> <p><em>Probabilistic Claim.</em> 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$.</p> <p>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.</p> <p>However, if $s(an)=s(bn)$ for all $n$, then $a$ and $b$ differ only by the number of zeroes in the end. </p> <p>I apologize if this edit rendered some comments meaningless.</p> http://mathoverflow.net/questions/94625/the-digit-sum-snasnb/94668#94668 Answer by Aaron Meyerowitz for The digit sum: $s(na)=s(nb)$ Aaron Meyerowitz 2012-04-20T18:52:14Z 2012-04-20T18:52:14Z <p>I don't follow fedja's proof. I'd guess that $s(n)=s(2n)$ <em>might</em> 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.</p> <p>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.</p> <p>However it may be the law of small numbers. It could be that the density decreases like $0.95^{\ln{x}}$ </p> http://mathoverflow.net/questions/94625/the-digit-sum-snasnb/94701#94701 Answer by Gjergji Zaimi for The digit sum: $s(na)=s(nb)$ Gjergji Zaimi 2012-04-20T23:32:43Z 2012-04-20T23:32:43Z <p>You can find some explicit asymptotics in a paper by J. Schmidt, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa43/aa4347.pdf" rel="nofollow">"The joint distribution of the binary digits of integer multiples"</a>. 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.</p>