7
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What happens if $a=101001$, $b=100101$? $\endgroup$ Commented Apr 20, 2012 at 12:26
  • $\begingroup$ oeis.org/A070279 $\endgroup$
    – Charles
    Commented Jun 17, 2012 at 21:15

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Claim 3 was the point of the post Seva referred to. $\endgroup$ Commented Apr 20, 2012 at 13:26
  • $\begingroup$ 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? $\endgroup$
    – Seva
    Commented Apr 20, 2012 at 14:40
  • $\begingroup$ @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. $\endgroup$ Commented Apr 20, 2012 at 15:25
7
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ OK, maybe I do see it, but the decay is surprisingly slow. $\endgroup$ Commented Apr 20, 2012 at 19:10
  • 1
    $\begingroup$ 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? $\endgroup$
    – fedja
    Commented Apr 20, 2012 at 19:25
  • $\begingroup$ @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}$? $\endgroup$
    – Seva
    Commented Apr 20, 2012 at 20:03
  • $\begingroup$ OK, I'll expand a bit :) $\endgroup$
    – fedja
    Commented Apr 20, 2012 at 20:58
  • $\begingroup$ Done. Is it better now? $\endgroup$
    – fedja
    Commented Apr 20, 2012 at 21:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .