We say that a positive integer $n$ is $m$-expressible if it is possible to get $n$ from some $m$ digits and the six operations $+,-,\times,\div$, exponentiation $^\wedge$, and concatenation $\oplus$. For example, $5625$ is $3$-expressible (in two ways): both $5\oplus (5^\wedge 4)$ and $(7\oplus 5)^\wedge 2$ yield $5625$. Does there exist a positive integer $N$ such that all positive integers with $N$ digits are $(N-1)$-expressible? Proposed by Krit Boonsiriseth
Problem
Source: ELMO SL 2018 C2
Tags: combinatorics
30.06.2018 14:45
Yes there exists such N. First note that each number with $n$ digits is $n$- expressible with the use of concatenation . Trivially if number $n$ is $a$ expressible then it is also $b$ expressible with $a<b$ . Now if there is a section of a number $K$($K$ having $N$ digits) with $m$ digits $...e_{k+m}e_{k+m-1}...e_{k+1}...$ which is $(m-1)$-expressible then the whole number $K$ is $N-1$ expressible . If a $m$ digit number $l$ is divisible by $7^5$ then it is $m-1$ expressible. Proof: $l=7^5 * t $ and since $7^5>10000$, $t$ has less than $m-3$ digits so $t$ is $m-3$ expressible and $l=7^5 * t $ is $m-1$ expressible . Thus finding a digit section of $K$ which is divisible by $7^5$ means we are done. To ensure that there is such a section take $N>7^5+1$ If $K=e_N...e_2e_1$ Then take digit sections $$e_1$$$$e_2e_1$$$$...$$$$e_ {7^5+1}...e_2e_1$$Two of which have the same residue $(mod 7^5)$ say $e_k...e_1 = e_{k+m}...e_1 (mod 7^5)$ which gives that if $e_{k+m}e_{k+m-1}...e_{k+1} = l$ then $7^5$ divides $10^{k+1}l$ thus $7^5$ divides $l$ done.
06.04.2019 20:11
Does any other digit work other than $7$ ?
06.04.2019 20:17
Yes. I think in fact $N$ rexists such that all positive integers with $N$ digits are $N\varepsilon$-expressible where $\epsilon$ is any positive real number. Maybe someone can check if my generalization is correct.
Attachments:

06.04.2019 20:41
Continued from above because I couldn't get the pictures to appear in correct order...
Attachments:

30.03.2022 18:09
We claim that $N=59050$ works. Let $n=\overline{d_1d_2\ldots d_N}$ be an $N$ digit number. First, we will find a substring of $n$ of length $m$ divisible by $59049$ (call it $s=d_pd_{p+1}\ldots d_{p+m}$), and then show that the substring must be $m-1$-expressible. This suffices since then $n$ may be expressed as: $$d_1\oplus d_2\oplus\ldots\oplus d_{p-1}\oplus s\oplus d_{p+m+1}\oplus d_{p+m+2}\oplus\ldots\oplus d_N.$$ Claim 1: $s$ is divisible by $59049$ Among the substrings $d_1\ldots d_q$ (of which there are $N$), two of them must have the same remainder$\pmod{59049}$ since $N>59049$. Letting these two substrings be $d_1\ldots d_{p-1}$ and $d_1\ldots d_{p+m}$, we find that the difference of these, $s\cdot10^{p-1}$, is divisible by $6561$. But since $\gcd(10^{p-1},59049)=1$, $s$ is divisible by $59049$. Claim 2: $s$ is $m-1$-expressible Let $s=59049t$. Since $s$ is at most $m+1$ digits, $s$ is at most $10^{m+2}$, so $t$ is at most $\frac{10^{m+2}}{59049}<10^{m-2}$, so $t$ is at most $m-3$ digits. So $t$ is $m-3$-expressible by concatenating its digits. Then $59049=9^\wedge5$ is $2$-expressible, so $s$ is indeed $m-1$-expressible.
04.03.2024 02:36
Let $A = \overline{d_nd_{n-1}\dots d_1}$, with $n = 7^5 + 1$. We will show that this choice of $n$ works over all $A$. Note that if a sub-string $\overline{d_id_{i+1}\dots d_j}$ is $(j - i + 1)-$expressible then $A$ is as well(since we can just concatenate the rest of the digits). Note that $\overline{d_kd_{k-1}\dots d_1}$ and $\overline{d_{k+1}d_{k}\dots d_1}$ are distinct modulo $7^5$ so by pigeonhole, there must be two numbers $g$ and $h$($g \neq h$, $g > h$) so that $\overline{d_gd_{g-1} \dots d_1} \equiv \overline{d_hd_{h-1} \dots d_1} \pmod{7^5}$. It follows that $\overline{d_gd_{g-1}\dots d_{h+1}} \equiv 0 \pmod{7^5}$. Notice that $7^5$ is compromised of $2$ digits and is $> 10^4$ so $\overline{d_gd_{g-1}\dots d_h}$ is $g - h + 1 - 2 = (g - h - 1)$-expressible since $\overline{d_gd_{g -1}\dots d_{h+1}} \div 7^5$ has at most $(g - h - 3)$ digits. So we are done.
04.04.2024 06:13
Call a number which can be expressed in less digits than it has efficient. Then note that any number with an efficient number as a substring must in turn be efficient by concatenation. Let $N = 69^{69^{69}}$. Then any number with more than $N + 1$ nonzero digits has a substring $S$ when taking the last few digits, which is divisible by $N$ by pigeonhole principle. As such, take $A = N^4$. Then if such a nonzero substring $S$ exists, then $S$ is efficient because expressing $S$ as $N \cdot \frac{N}{S}$ takes less than $A-1$ numbers, since $\log(S) - 1 \ge \log\left(\frac{N}{S}\right) + 12 + 3$ where $\log$ is base $10$. Else, there must be a series of at least final $N^2$ zero digits which have a nonzero digit before them, which can be expressed efficiently as $d \cdot 10^{N^2}$ for some digit $d$.