2
$\begingroup$

For any integer, we consider its decompositions into sequences of products by $2$ and integer division by $3$.

For instance: $$ 100 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 /3/3/3/3 \cdot 2 \cdot 2 $$

We consider such sequences of operations are done from left to right: $100 = ((((((2^{11})/3)/3)/3)/3)\cdot 2^2)$.

An integer division by $3$ means that we take the integer part of the result and discard the fractional part: $x/3$ means $\lfloor\frac{x}{3}\rfloor$ here.

We write such a decomposition in a compact way by omitting operators; then, the above decomposition of $100$ is $22222222222333322$.

This decomposition has length $17$. A minimal decomposition is a decomposition of minimal length.

It seems that (some of) the following questions are non-trivial:

  • do all numbers have such a decomposition?
  • what is the minimal length of a given number decompositions?
  • how many minimal decompositions does a given number have?
  • how to find a minimal decomposition of a given number?
  • how to find all minimal decompositions of a given number?

This is a MO rephrasing and extension of this math.se question asked 7 years ago, that received recently some attention but still has no complete answer.

It was empirically established that all numbers from $0$ to more than $4535$ have a decomposition; that the minimal decompositions of $27$ have length $23$ and include $22223222222233232322323$ and $22222322222222333222333$; and that minimal decompositions of $4535$ have length $77$ and include $22222322223323222232222232323322223222232222222223222233322233233223333222233$, $22222322232232322232232222323232222322232232222223232233222233222233222333233$, and $22223222322232322232232222322232232232322232222222333223322233232223322322233$.

More observations are available in the math.se discussion.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ I guess the sample "decomposition" should have $/3$ instead of $\cdot 3$. Every integer $n$ always has "decomposition" of the form $2^a / 3^b$ because (taking logs base 3) all we need is $a \log_3 \! 2 - b$ between $\log_3 n$ and $\log_3 (n+1)$, and since $\log_3 \! 2$ is irrational the positive integer multiples of $\log_3 \! 2$ are equidistributed mod 1 so in particular include infinitely many elements of the interval $(\log_3 n, \log_3 (n+1)) \bmod 1$. $\endgroup$
    – Noam D. Elkies
    Commented Feb 11, 2021 at 3:24
  • $\begingroup$ @NoamD.Elkies: Does your argument give $b\ge 0$? $\endgroup$
    – markvs
    Commented Feb 11, 2021 at 3:36
  • $\begingroup$ Yes, because there are infinitely many $a \geq 0$ and all but finitely many have $2^a \geq n$. $\endgroup$
    – Noam D. Elkies
    Commented Feb 11, 2021 at 3:45
  • $\begingroup$ @NoamD.Elkies: Also $ \lfloor 2^n/3^k\rfloor \ne \lfloor ... \lfloor 2^n /3\rfloor/3\rfloor ... /3\rfloor$ in general. $\endgroup$
    – markvs
    Commented Feb 11, 2021 at 3:46
  • 3
    $\begingroup$ Actually they are always equal; in general, for any positive integers $x,y,z$ we have $\lfloor x/(yz) \rfloor = \lfloor \lfloor x/y \rfloor /z \rfloor$, and likewise for $\lfloor w/(xyz) \rfloor$ etc. $\endgroup$
    – Noam D. Elkies
    Commented Feb 11, 2021 at 3:53

0

Reset to default