8

For $x>0$ consider the following three functions:

$$\begin{align} f(x)&=x+1;\\g(x)&=2x;\\t(x)&=3x \end{align}$$


Let $A(x)$ be the minimum number of operations using only functions $f(x)$ and $g(x)$ needed to get $X$ from $0$.
Let $B(x)$ be the minimum number of operations using only functions $f(x) $ and $t(x)$ needed to get $X$ from $0$.

Endless or no set of numbers for which $A(x)<B(x)$.

mookid
  • 28,236
Andrew
  • 303
  • 1
  • 11
  • Have you tried to convert the number to binary and ternary number systems? – Antony Oct 14 '14 at 09:39
  • Just to be clear: you want to know whether the set of numbers $x$ for which $A(x)<B(x)$ is finite of infinite? – Pierre-Guy Plamondon Oct 22 '14 at 14:34
  • 4
    To produce $2^k$ is going to require $k+1$ steps with the binary functions, but about $(2\log 2 / \log 3) k$ steps with the ternary functions. So we expect $A(x)<B(x)$ for infinitely many values of $x$ that are powers of $2$. However, the density of numbers for which $A(x)<B(x)$ is expected to go to zero as $x\rightarrow\infty$. – mjqxxxx Oct 22 '14 at 21:03

1 Answers1

2

To expand on Antony's suggestion, for a number $x$, $A(x)$ is simply the sum of the digits of the binary representation of the number, plus the number of digits $\lfloor log_2(x) \rfloor$. Similarly, $B(x)$ is the sum of the digits of the ternary representation of the number, plus the number of digits $\lfloor log_3(x) \rfloor$.

The expected value of $A(x)$ and $B(x)$ for a "random" integer would be:

$E(A(x)) = \frac{3\lfloor log_2(x) \rfloor + 1}2$ and

$E(B(x)) = 2 \lfloor log_3(x) \rfloor + 1$, which means that with $x$ taken to infinity $\frac{E(A(x))}{E(B(x))} = \frac{3 log_2(3)}4 \approx 1.1887...$

Therefore it is to be expected that $A(x)$ is usually larger than $B(x)$. However, statistically any number which has a binary representation with less $1$'s than $2 \lfloor log_3(x) \rfloor + 1 - \lfloor log_2(x) \rfloor$, which comes out roughly $(\frac2{log_2(3)}-1)log_2(x) + 1 \approx 0.26186log_2(x) + 1$. Meaning that if a number has in its binary expansion roughly a quarter or less of the digits (excluding the highest digit, which we eliminate with the $+1$ as it must be $1$) as $1$s, then chances are $A(x) < B(x)$. This means that as $x \to \infty$, the number of integers with $n$ digits that we can expect $A(x) < B(x)$ is approximately $\binom{n}{n/4}$, which isn't very much compared with $2^n$, but still tends to infinity.

That said, in order to answer the question, we need to try and find an infinite set of $x$ which we can be sure $A(x)<B(x)$. The powers of 2 suggested by mjqxxxx appear to be good candidates because they minimize $A(x)$, however I'm not sure how you can prove $B(x)$ is bigger even for this sequence (some numbers may by very small chance have a very low $B(x)$ value as well).

Alon Navon
  • 1,455