4
$\begingroup$

Is the set of all numbers that can be represented as a sum of distinct powers of $3$ (e.g. $256=3^{0}+3^{1}+3^{2}+3^{5}$ and as a sum of distinct powers of $4$ (e.g. $256=4^{4}$) finite? Equivalently, are there an infinite number of integers that can be represented in base $3$ and $4$ with only $0$s and $1$s for digits?

Relevant OEIS entry: A258981

$\endgroup$
  • 1
    $\begingroup$ In oeis.org/A230360 where the number of these in each length base $4$ are counted it is stated that it is unlikely there are a finite number of these. No justification is given. There are $173552$ of them with $63$ base $4$ digits. $\endgroup$ – Ross Millikan Dec 7 '17 at 1:46
3
$\begingroup$

Here is a very heuristic argument that there should be an infinite number of them. Consider the numbers with $n$ base $4$ digits. There are $4^n-4^{n-1}=3\cdot 4^{n-1}$ of them, of which $2^{n-1}$ numbers have base $4$ digits that are all $0$ or $1$. These numbers have $n\cdot \frac {\log 4}{\log 3} \approx 1.26n$ base $3$ digits. If we assume no correlation between the base $3$ digits and the base $3$ digits we would expect a fraction of $\frac 12\left(\frac 23\right)^{1.26n-1}$ to have all digits $0$ or $1$ in base $3$. If we multiply these, we expect $2^{n-1} \cdot \frac 12\left(\frac 23\right)^{1.26n-1}$ numbers with $n$ base $4$ digits that have all digits $0$ or $1$ in both bases. This goes as about $1.2^n$ so there should be lots of them. It is curious that there are many $n$ for which there are no examples, then some $n$ where there are lots. I suspect the correlation comes from the constant $\frac {\log 4}{\log 3}$ but don't see how.

$\endgroup$
  • $\begingroup$ Do you believe that there might exist a proof? If so, what mathematical topics would it concern? I'm guessing a form of modular arithmetic is involved or related. $\endgroup$ – Cassaundra Smith Dec 7 '17 at 3:15
  • 2
    $\begingroup$ Questions involving middle digits of numbers are very hard. They really don't reflect on the number, more on the base you are working in. The lower digits often reflect modular arithmetic and the highest digits reflect the order of magnitude, but the middle ones do whatever. $\endgroup$ – Ross Millikan Dec 7 '17 at 3:19

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.