Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
What happens if $a=101001$, $b=100101$? –  Gerry Myerson Apr 20 '12 at 12:26
    
oeis.org/A070279 –  Charles Jun 17 '12 at 21:15
add comment

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer
    
Claim 3 was the point of the post Seva referred to. –  Emil Jeřábek Apr 20 '12 at 13:26
    
Sorry - I cannot follow, starting from the sentence "$M$ zeroes will control the transfers ...". If you happen to feel a little more serious about your answer, would you kindly try to add some explanations? –  Seva Apr 20 '12 at 14:40
    
@Seva: if $n=10^{M+k}x+y$, where $y$ has less then $k$ digits, and $a$ less then $M$ digits, then $s(na)=s(xa)+s(ya)$. Apply this for all portions of consecutive zeros Fedja is telling about. –  Fedor Petrov Apr 20 '12 at 15:25
add comment

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.

share|improve this answer
add comment

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}}$

share|improve this answer
    
OK, maybe I do see it, but the decay is surprisingly slow. –  Aaron Meyerowitz Apr 20 '12 at 19:10
1  
It must be fairly slow if you believe the law of large numbers: after all we have two sums of $\log n$ weakly dependent random variables (the digits in the product), so $1/\log n$ is the best to hope for and $1/\sqrt{\log n}$ is the natural thing to expect. I guess Fedor answered Seva's concerns. What are yours? –  fedja Apr 20 '12 at 19:25
    
@fedja: wrong guess, I still don't get it. Exactly how have you defined your random variables, and how they are related to the story? What is $X_1$, say? What is $X_{25}$? –  Seva Apr 20 '12 at 20:03
    
OK, I'll expand a bit :) –  fedja Apr 20 '12 at 20:58
    
Done. Is it better now? –  fedja Apr 20 '12 at 21:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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