5
$\begingroup$

Is there a largest number which uses precisely three times as many digits in its expression in base 2 as it does in base 10?

Is there a largest number which uses precisely three times as many digits in its expression in base 2 as it does in base 10, and whose digital sum in base 2 is also three times its digital sum in base 10?

$\endgroup$
0
9
$\begingroup$

For the first part of this question, the largest number with three times as many digits in base 2 as in base 10 is 1073741823 $(2^{30}-1)$. (The question was edited for clarity after I started answering and I wasn't aware that the second part was any different from the first until I just read it again...)

We want $\frac{ceil(log_2(x))}{ceil(log_{10}(x))}=3$. I graphed this function in Desmos on a log scale:

enter image description here

While $\frac{log_2(x)}{log_{10}(x)}$ is a constant equal to $log_210$, taking the ceiling before dividing appears to result in an infinite sequence converging on $log_210$. I only have a basic understanding of real analysis, so I invite anyone else who knows more to explain why this happens.

Since $log_210$ is about 3.32, all numbers above a certain point will have more than three times the number of digits in base 2 than in base 10. It looks like this turning point is about $10^{9.031}$.

This means that the number of digits in base 2 of this largest number must be 30; taking $2^{30}-1$ (as $2^{30}$ is a 31-digit number in base 2) gives us a final answer of 1073741823.

$\endgroup$
2
  • $\begingroup$ does PSE support LaTeX orz $\endgroup$ Nov 11 '20 at 23:22
  • 4
    $\begingroup$ PSE does support MathJax. For inline math use $ ... $ and for block math $$ ... $$. $\endgroup$
    – Bubbler
    Nov 11 '20 at 23:23
6
$\begingroup$

The first part (without resorting to graphs)

The number of binary digits of a positive integer $n$ is $\lfloor\log_2 n\rfloor +1 $, and for decimal it is $\lfloor\log_{10} n\rfloor + 1$. Therefore we're finding the value of $n$ that satisfies $\lfloor\log_2 n\rfloor +1 = 3(\lfloor\log_{10} n\rfloor +1) $.

Using a power of ten, as in $n=10^x$ will give the lower bound of ratio of the binary and decimal digits in the range $[10^x, 10^{x+1}) $. Plugging it into the equation above gives the following result:

$$ \lfloor\log_2 10^x \rfloor + 1 = 3( \lfloor\log_{10} 10^x \rfloor + 1) = 3(x+1) \\ \lfloor x \log_2 10 \rfloor = 3x + 2 \\ x \log_2 10 < 3x + 3 \\ x < \frac{3}{\log_2 10 - 3} \approx 9.3 $$

Indeed $10^9$ has ten digits in decimal and 30 digits in binary. Then we can conclude that the number we're trying to find is the maximal number that has 30 digits in binary, which is

$2^{30}-1 = 1073741823$

Higher than that, the digit count ratio is too high for both $2^{30} \le n < 10^{10}$ (31+ binary vs. 10 decimal) and $10^{10} \le n$ (as proven using powers of 10).

The second part (fast brute-force program)

from itertools import combinations_with_replacement as cwr

collect = {}
for r in range(1,10):
    for comb in cwr([10**i for i in range(8)], r):
        n = sum(comb) + 10**9
        if n >= 2**30: continue
        b = bin(n)[2:]
        if b.count('1') == 3 * (r+1):
            collect[n] = b

print(len(collect), 'solutions found')
for n in sorted(collect):
    print(n, collect[n])

Try it online!

It finds 230 solutions in the range $10^9 \le n < 2^{30}$, the maximum of which confirms Paul Panzer's answer of

$ 1040100000 = 111101111111101010101010100000_2 $

$\endgroup$
3
$\begingroup$

Largest number with 3 times as many bits as digits

$2^{30}-1 = 1,073,741,823$

Largest number with 3 times as large bit sum compared to digit sum

$0b11,1101,1111,1110,1010,1010,1010,0000 = 1,040,100,000$

Found by:

1. Trying $2^3-1,2^6-1,2^9-1$ etc. 2. Brute forcing backward from 1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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