The answer is only the obvious ones: $f(x) = 10^e x$, $f(x) = k$, and $f(x) = 10^e x + k$, for any choice of $k \in K$ and $e > \log_{10} k$ (with $e \ge 0$). Now assume $f$ satisfies $f(K) \subseteq K$; such polynomials will be called stable. We first prove the following claim which reduces the problem to the study of monomials. Lemma: [Reduction to monomials] If $f(x) = a_0 + a_1 x + a_2 x^2 + \dots$ is stable, then each monomial $a_0$, $a_1 x$, $a_2 x^2$, \dots is stable. Proof. For any $x \in K$, plug in $f(10^e x)$ for large enough $e$: the decimal representation of $f$ will contain $a_0$, $a_1 x$, $a_2 x^2$ with some zeros padded in between. $\blacksquare$ Let's tackle the linear case next. Here is an ugly but economical proof. Claim: [Linear classification] If $f(x) = cx$ is stable, then $c = 10^e$ for some nonnegative integer $e$. Proof. We will show when $c \ne 10^e$ then we can find $x \in K$ such that $cx$ starts with the digit $7$. This can actually be done with the following explicit cases in terms of how $c$ starts in decimal notation: For $9 \cdot 10^e \le c < 10 \cdot 10^e$, pick $x = 8$. For $8 \cdot 10^e \le c < 9 \cdot 10^e$, pick $x = 88$. For $7 \cdot 10^e \le c < 8 \cdot 10^e$, pick $x = 1$. For $4.4 \cdot 10^e \le c < 7 \cdot 10^e$, pick $11 \le x \le 16$. For $2.7 \cdot 10^e \le c < 4.4 \cdot 10^e$, pick $18 \le x \le 26$. For $2 \cdot 10^e \le c < 2.7 \cdot 10^e$, pick $28 \le x \le 36$. For $1.6 \cdot 10^e \le c < 2 \cdot 10^e$, pick $38 \le x \le 46$. For $1.3 \cdot 10^e \le c < 1.6 \cdot 10^e$, pick $48 \le x \le 56$. For $1.1 \cdot 10^e \le c < 1.3 \cdot 10^e$, pick $58 \le x \le 66$. For $1 \cdot 10^e \le c < 1.1 \cdot 10^e$, pick $x = 699\dots9$ for suitably many $9$'s. \qedhere $\blacksquare$ The hardest part of the problem is the case where $\deg f > 1$. We claim that no solutions exist then: Claim: [Higher-degree classification] No monomial of the form $f(x) = cx^d$ is stable for any $d > 1$. Proof. Note that $f(10x+3)$ is stable too. We have \[ f(10x+3) = 3^d + 10d \cdot 3^{d-1} \cdot x + 100 \binom d2 \cdot 3^{d-1} x^2 + \dots. \]and so on. By applying the lemma the linear monomials $10d \cdot 3^{d-1} x$ is stable, hence $10d \cdot 3^{d-1}$ is a power of $10$, which can only happen if $d = 1$. $\blacksquare$ Thus the only nonconstant stable polynomials with nonnegative coefficients must be of the form $f(x) = 10^e x + k$ for $e \ge 0$. It is straightforward to show we then need $k < 10^e$ and this finishes the proof.

How many points would someone get for only the first lemma?

The solutions are of the form $f(x) = \lambda$ for $\lambda \in K$ and $f(x) = 10^e x + \lambda$, where $e$ is a nonnegative integer, $\lambda < 10^e$, and $\lambda \in K \cup \{0\}$. It is easy to see that they work. Now let $f(x) = a_nx^n + \dots + a_0$ denote a polynomial satisfying the problem condition. Assume that $f$ is nonconstant. Lemma 1. If $\lambda$ is a positive integer such that $\lambda m \in K$ whenever $m \in K$, then $\lambda$ is a power of 10. Proof. In particular, the numbers $1, \lambda, \lambda^2, \dots$ all belong to $K$. If $\lambda$ is not a power of 10, then $\log_{10} \lambda$ is irrational, so some $\lambda^k$ begins with the digit 7. $\square$ Lemma 2. If $r_1, \dots, r_n \in K$, then $n! a_n r_1 \cdots r_n \in K$. Proof. Consider the number \[m = 10^{e_1} r_1 + \dots + 10^{e_n} r_n,\]where no nonnegative linear combination of $\{e_i\}$ is near $e_1 + \dots + e_n$. Then $m \in K$, so $f(m) \in K$ too. Its decimal expansion contains a block of the form $n! a_n r_1 \cdots r_n$, so this number also belongs to $K$. $\square$ Claim. $\deg f = 1$. Proof. Suppose $\deg f \ge 2$. By selecting $r_2 = 3$ and $r_3 = \cdots = r_n = 1$ in Lemma 2, we obtain $m \in K \implies 3 \cdot n!a_n m \in K$. Hence by Lemma 1 the number $3 \cdot n! a_n$ is a power of 10, which is not possible. $\square$ Thus $f(x) = a_1 x + a_0$. Choosing $x = 10^e r$ for $e \gg 0$ and $r \in K$, it follows that $f(x)$ consists of blocks $a_1 r$ and $a_0$. Hence $a_0 \in K$ and also $r \in K \implies a_1 r \in K$, so by Lemma 1 it follows $a_1$ is a power of 10. Set $a_1 = 10^e$, say. All we need to prove now is that $a_0 < 10^e$. Suppose not: let $\gamma = \lfloor \log_{10} a_0 \rfloor$, and then one of the numbers $f(0 \cdot 10^{\gamma - e})$, ..., $f(6 \cdot 10^{\gamma - e})$, $f(8 \cdot 10^{\gamma - e})$, $f(9 \cdot 10^{\gamma - e})$ will contain a 7 in the $10^\gamma$ position (because $a_0$ has a nonzero digit in that position), contradiction.

redacted

I had half the test to do this.... and I got nowhere....

Funny problem! Here's a sketch: Say $xy\in K$ for all $y \in K$. Then, if $x$ ends in $2, 4, 6, 8$ we can pick $y\in K$ so that $xy$ ends in $72$, if $x$ ends in $5$ we can pick $y\in K$ so that $xy$ ends in $75$, and if $x\in \{3, 7, 9\}$ we can pick $y\in K$ so that $xy$ ends in $7$. If $x$ ends in $1$ and $x > 1$, we can pick $y\in K$ so that $xy$ ends in $700\cdots 01$ for some number of zeroes. Finally, if $x$ ends in $0$ replace $x$ with $x/10$ and repeat. So, if $xy\in K$ for all $y\in K$, $x$ is a power of ten. Now plug in $f(k\cdot 10^N)$ for $N$ big and we get that $ak^d\in K$ for $k\in K$, where $a$ is the leading coefficient and $d$ is the degree. Now $a(x+10^Ny)^d\in K$ for $x,y\in K$ and $N$ big, so $adx^{d-1}y\in K$ for all $x,y\in K$. So, $adx^{d-1}$ is a power of $10$ for all $x\in K$ which forces $d = 1$ or $d = 0$. If $f\equiv mx+b$ is linear then take $n = k\cdot 10^N$ for $n$ big to get that $mk\in K$ for $k\in K\implies m$ is a power of $10$, then it's easy to get that $b < m$ as well and $b\in K$ or $b=0$. If $f$ is constant we must have $f\equiv k\in K$.

I suppose no one got a 7 on this problem if you know what I mean

yayups wrote: I suppose no one got a 7 on this problem if you know what I mean apparently pro people did

samuel wrote: yayups wrote: I suppose no one got a 7 on this problem if you know what I mean apparently pro people did woosh

samuel wrote: yayups wrote: I suppose no one got a 7 on this problem if you know what I mean apparently pro people did You are missing the point lmao edit: sniped

I proved that linear functions would have to be of the above forms, and then i did the following(sketch): Note that if the degree of \(f\) is \(c \ge 2\), then if \(f\) satisfies the condition, so does \(f^k\) for any positive integer \(k\). Let \(a_0\) be the leading coefficient of \(f\) Then note that by plugging in any sufficiently large power of 10 into \(f^k\), we get that the leading coefficient of it, \(a_0^k\), is in \(K\), and hence \(a_0\) is a power of 10. Then I just said that this implies that by plugging in \(t \cdot 10^i\) for \(t \in K\) and \(i\) sufficiently large, we see that \(t^c \in K\) for all \(t\). I stated that this was impossible without proof. How many points would this get?

How many points is forgetting $cx$ as in the solution set? I think I put $cx+b$ for $0\leq b < c, b \in K$ @Below but $0$ is not in $K$

Muriatic wrote: How many points is forgetting $cx$ as in the solution set? I think I put $cx+b$ for $0\leq b < c, b \in K$ 7 because u wrote b>=0

How much will I get for writing the correct lemmas, basically same as above, without actually proving cuz running out of time to bash. I was just like always possible to get leading digit of 7 since x^n if n>=2 can always have any k leading digits you want with enough zeros and random digits behind it.

Muriatic wrote: How many points is forgetting $cx$ as in the solution set? I think I put $cx+b$ for $0\leq b < c, b \in K$ @Below but $0$ is not in $K$ LOL do they give 6s for stuff like this

FlakeLCR wrote: Muriatic wrote: How many points is forgetting $cx$ as in the solution set? I think I put $cx+b$ for $0\leq b < c, b \in K$ @Below but $0$ is not in $K$ LOL do they give 6s for stuff like this Nah I think he's fine.

How many points is proving the lemma and the claim but not the last lemma?

Call these polynomials that satisfy the condition interesting . Lemma 1: If $f(x)=cx$ is interesting then $c=10^e$ . $1,c,c^2,c^3,...$ all belong to $K$.However $log_{10}c$ is irrational so we can choose $c^k$ having $7$ as the first digit. @thanks above Lemma 2:If $f(x)=c_kx^k+...+c_1x+c_0$ is interesting then all terms $c_ix^i$ are interesting. Setting $x=10^Nx$ for large enough $N$ we get the decimal representations of $c_ix^i$ separated by $0's$. Lemma 3: No monomial of the form $f(x)=cx^d$ ,$d>1$ is interesting. $f(10x+3)$ would be interesting .Expanding and applying lemma 2 we get that the linear term is interesting. Namely $10cd3^{d-1}x$ is interesting which is not possible. The previous lemmas suggest that the only possible interesting (nonconstant)polynomials are $f(x)=10^ex+k$ for $k<10^e$.

When I first read the solutions I thought the $e$ variable was the actual value of $e$ and I was so confused... Was this an easy problem?

Call a polynomial imperfect if it satisfies the problem condition. Let $f(x) = a_0 + a_1x + \dots + a_nx^n$. First plug in $x = 10^My$ for gigantic $M$ and $y \in K$ to get $$f(x) = a_0 + 10^M(a_1y) + 10^{2M}(a_2y^2) + \dots + 10^{nM}(a_ny^n)$$ If $M$ is large enough (formally, greater than any $\log_{10}(a_ny^n)$) then this result gives the decimal representations of each $a_iy^i$ concatenated with some zeroes inbetween. As this holds for any $y \in K$ it follows that all $a_iy^i$ are imperfect, so it suffices to solve for polynomials of this form. Clearly $f(x) = a$ is imperfect iff $a \in K$. We'll show later that $f(x) = ax$ is imperfect iff $a = 10^m$ for some $m$. We now claim that $ax^n$ is never imperfect if $n \geq 2$. Let $x = 10^py + d$ where $y, d \in K$ and $p$ is huge. We get $$f(x) = a(10^py + d)^n = \sum_{k = 0}^n 10^{kp}\left(a\binom{n}{k} d^{n - k}y^k\right)$$ So applying the same argument we get that all $a\binom{n}{k} d^{n - k}y^k$ are imperfect polynomials. For $k = 1$ we get $and^{n - 1}y$ imperfect for all $d \in K$, which is clearly impossible unless $n - 1 = 0$ as $and^{n - 1}$ must be a power of $10$ for any $d \in K$. Finally we must show that if $ax$ is imperfect then $a$ is a power of $10$. The least painful way to prove this is probably to notice that $1, a, a^2, \dots$ are all in $K$ by this condition. By a classical result there is a power of $a$ starting with any string of digits you want unless $a$ is a power of $10$, so in particular you can make it start with $7$, which contradicts $a^m \in K$ for all $a$. Therefore $a$ is a power of $10$ as desired.

Here's an outline of my solution: Assume for contradiction a polynomial of degree $n \geq 2$ works. Suppose the leading term of $f(x)$ is $ax^n$, and let $x_{(b,c)}$ be the integer formed by concatenating $b$ copies of $10^c$. It is clear that for sufficiently large $b$ and $c$, the decimal expansion of $x_{(b,c)}^n$ starts with a sequence of $(n-1)$-simplex numbers, spaced $c$ digits apart (for example, 1010101010101^3 = 103061015...), and the length of this sequence increases in $b$ and $c$. Since $(n-1)$ - simplex numbers grow polynomially and therefore slower than exponentially, we can find consecutive $(n-1)$-simplex numbers which contain numbers starting with $10, 11, 12, 13, ..., 99$. It is clear that one of these numbers, when multiplied with $a$, starts with 7. But by taking sufficiently large $c$, noting that for large enough $x$, the leading term of the polynomial dominates, we can ensure that the numbers are spaced far enough to ensure that this occurs in the decimal expansion of $f(x)$. This is a contradiction, and so $n \leq 1$. Clearly any constant $f(x)$ works if the constant is in $K$. If $f(x) = ax+k$ works, then take any $10^d x$ where $x \in K$ and $10^d > k$. Then $x \in K \implies ax \in K \implies a^e \in K \; \forall e \in \mathbb{N}$. Taking $\log_{10}$ of these numbers and then considering the fractional part, we can start with any string if $\log_{10}{a}$ is irrational. So $a$ is a power of 10, and it is easy to check that $k$ must be 0 or an element of $K$ less than $a$.

Here's another proof that monomials with degree $\ge 2$ fail on the assumption that the only monomials which work are of form $10^kx$: First, we'll show that no monomials of the form $a x^2$ work. Note that if we take $x=10^N+y$ for $N$ large and any $y\in K$, then $ax^2=a(10^N+y)^2 = a\cdot 10^{2N} + 2ay\cdot 10^N + y^2$. If we take $N$ large enough, then we need $2ay\in K$ whenever $y\in K$. By the previous assumption, this forces $2a$ to be a power of $10$, so it follows $a=5\cdot 10^k$ for some $k$. But then taking $x=12$, we get $ax^2 = 5\cdot 10^k\cdot 144 = 720\cdot 10^k$, contradiction! Thus no monomials $ax^2$ work. Now to prove no monomials of the form $ax^k$ work, we once again take $x=10^N+y$ for $N$ large and $y\in K$. Note that $ax^k = a(10^N+y)^k = a\cdot 10^{kN} + kay\cdot 10^{(k-1)N} + \binom{k}{2}ay^2\cdot 10^{(k-2)N} + \cdots$. If we take $N$ large, then we need $\binom{k}{2}ay^2\in K$ whenever $y\in K$. But there's no such value of $a$ for which this can be true, so no higher order monomials work.

Here are some interesting things one can prove about $K$: Lemma 1: For any string $S$ of digits, there exist $x,y\in K$ so that $x y$ contains $S$ as a (contiguous) substring of its decimal representation. Proof: Let $S = \sum a_i 10^{b_i}$ where $0<a_i\le 9$ and the $b_i$ are distinct. Choose a large integer $N$ and let $x=y=0$. Basically for each $a_i 10^{b_i}$ we'll create $a_i$ pairs of terms $u,v$ such that $uv = 10^{b_i}$ and then add $u$ to $x$ and $v$ to $y$ so that $xy$ contains $a_i$ terms of the form $uv = 10^{b_i}$. For instance, to get the $a_110^{b_1}$ term we'll increment $(x,y)$ by $(10^{N+b_1}, 10^{-N}), (10^{2N+b_1}, 10^{-2N}), \dots, (10^{a_1 N + b_1}, 10^{-a_1N})$. Then to get the $a_2 10^{b_2}$ term we increment $(x,y)$ by $(10^{(a_1+1)N + b_2}, 10^{-(a_1+1)N})$ and so on. Then it follows that when we expand $xy$ and group the terms in the product by the "degree" of $10^N$, we get some series of the form $\dots + c_1 10^{1N} + c_0 10^{0N} + c_{-1} 10^{-N} + \dots$, where the $c_i$ don't depend on $N$. Now when $10^N > \text{max} c_i$, it follows that $xy$ contains $c_0$ as a substring of its decimal representation, and $c_0$ is precisely $S = \sum a_i 10^{b_i}$. Now we multiply $y$ by a power of $10$ so that it is an integer, and since the digits of $x,y$ are only $0$s and $1$s, we are done. Lemma 2: For any fixed $m>0$ and string $S$ of digits, there exist $x,y\in K$ so that $mxy$ contains $S$ as a substring. Proof: This follows easily from Lemma 1. Choose a large $n$ and let $z = \left\lfloor \dfrac{10^n S}{m} \right\rfloor$. Let $S'$ be the string consisting of $1$ followed by $N$ zeroes followed by $z$ followed by $N$ more zeroes for a large $N$. The above result shows we can find $x,y\in K$ with $xy$ containing $S'$ as a substring. Now if $N$ is sufficiently large, then in the product $mxy$ the portions of $S$ to the left and right of $z$ will not interfere with the middle section $mz$, hence $mz$ is a substring of $mxy$. But $mz$ is an integer between $10^n S$ and $10^nS + m$, so when $10^n > m$ we find that $S$ is a substring of $mz$, and we're done. Now let's see how these lemmas allow us to finish the problem. Let $f(x) = \sum a_ix^i$. By choosing $x = 10^Nm$ for large $N$, it follows that each $a_i m^i$ must be in $K$ since none of these terms overlap. When $i>1$ I claim this is a contradiction. Indeed, let $m = k_1 10^{x_1} + k_210^{x_2} + 10^{x_3} + 10^{x_4} +\dots + 10^{x_i}$, where the $x_i$ are a fast-growing sequence. Then $a_i m^i = \sum b_j 10^{c_j}$, where the $b_j$ are constants and each $c_j$ is of the form $\sum u_k x_k$ for $\sum u_k = i$. If $\{x_i\}$ grows fast enough then we can force the difference between any two distinct $c_j$ to be at least $\log_{10} b_j$ (eg. $x_i = (i+1+\text{max} \log_{10} b_j)^i$ or something similar), so no two $b_j 10^{c_j}$ terms will overlap, hence in particular $a_im^i$ will contain a term of the form $a_i i! k_1k_2 10^{x_1+x_2+\dots + x_i}$. By Lemma 2 for $m=a_ii!$ we can choose $k_1,k_2\in K$ so that this term contains a $7$, yielding the existence of $m\in K$ with $a_im^i\not \in K$, contradiction unless $a_i=0$. Hence $a_i=0\forall i\ge 2$. Now we've shown $f(x) = ax+b$. From the above we know that for all $m\in K$ we must have $am\in K$. If $a\neq 0$ then it follows inductively that $a, a^2, a^3, \dots$ are all in $K$, so $a$ must be a power of $10$ or else some power of $a$ will begin in the digit $7$ (say, by the irrationality of $\log_{10} a$). If $a=0$ then clearly all $b\in K$ work; if $a=10^m$ then clearly all $b\in K$ with $b<a$ work, along with $b=0$. It's straightforward to show that if $a=10^m$ then $b \ge a$ will fail, so these are all the solutions.

Is it rigorous enough to conclude that from the irrationality of $\log_{10}(n)$, it is possible for any fixed whole numbers $a$ and $d >1$ to find a $n \in K$ such that $an^d$ starts with 7? My fear is that because $K \neq \mathbb{N}$, $K$ might "miss out" on "most" of the possible fractional parts of logs as it obviously does when $d=1$ hence making such a claim false.

mathisawesome2169 wrote: Is it rigorous enough to conclude that from the irrationality of $\log_{10}(n)$, it is possible for any fixed whole numbers $a$ and $d >1$ to find a $n \in K$ such that $an^d$ starts with 7? My fear is that because $K \neq \mathbb{N}$, $K$ might "miss out" on "most" of the possible fractional parts of logs as it obviously does when $d=1$ hence making such a claim false. yea im not sure how true this is. i reduced the problem to proving it when a=1, but proving it may not be as easy

mathisawesome2169 wrote: Is it rigorous enough to conclude that from the irrationality of $\log_{10}(n)$, it is possible for any fixed whole numbers $a$ and $d >1$ to find a $n \in K$ such that $an^d$ starts with 7? My fear is that because $K \neq \mathbb{N}$, $K$ might "miss out" on "most" of the possible fractional parts of logs as it obviously does when $d=1$ hence making such a claim false. More often than not, a "fear" about the rigor of a given step is precisely what should be proven/disproven alongside it . (Unsurprisingly, however, proving this is nontrivial.)

Wrong solution

adamov1 wrote: @above $K$ does not have density $1$ (it actually has density $0$ in a pretty severe way) so your solution doesn't work at all. The reason I know this is https://www.smbc-comics.com/comic/math-translations. Thank you for correction. I actually proved this fact once so I don't know what was I thinking. I guess it was like: I know something about the density of $K$, I know that if dense I'm done so I'm done but I wasn't. At least got a cute lemma out of it.

@above $K$ does not have density $1$ (it actually has density $0$ in a pretty severe way) so your solution doesn't work at all. The reason I know this is https://www.smbc-comics.com/comic/math-translations.

It is easy to verify these functions work: $f\equiv d$, $f(n)\equiv10^en$, and $f(n)\equiv10^en+d$ for $e\ge0$, $d<10^e$, and $d\in K$. We prove they are the only solutions. Say a function is happy if the problem condition is satisfied. The key is the tackle monomials first. In particular, we claim: Lemma: [Monomial case] If a nonconstant function of the form $f(n)\equiv cn^d$ is happy, then $c$ is a power of $10$ and $d=1$. The lemma follows from the following two claims: Claim: If $f(n)=cn$ is happy, then $c$ is a power of $10$. Proof. We have $1$, $c$, $c^2$, $c^3$, $\ldots$ are all elements of $K$, but if $\log_{10}c$ is irrational, then for some $k$ we have $\{\log_{10}c^k\}\in[\log_{10}7,\log_{10}8)$; that is, the leftmost digit of $c^k$ is $7$, contradiction. $\blacksquare$ Claim: If $f(n)=cn^d$ is happy, then $d\in\{0,1\}$. Proof. Assume $d>0$. If $n\in K$, then $10^en+3\in K$ for each $e\ge1$; in particular, \begin{align*} K&\ni f(10^en+3)=c\cdot3^d+cd\cdot3^{d-1}\cdot10^en+c\binom d2\cdot3^{d-2}\cdot10^{2e}n^2+\cdots, \end{align*}so by taking $e$ sufficiently large, $cd\cdot3^{d-1}n\in K$ for all $n$. Thus the function $g(n)=cd\cdot3^{d-1}n$ is happy, so $cd\cdot3^{d-1}$ is a power of $10$ by the first claim. Then $d=1$ follows. $\blacksquare$ Having established the lemma, we now solve the general case. Let $f(n)=a_0+a_1n+a_2n^2+\cdots$, and for each $n$, plug in $f(10^en)$ where $10^e>a_kn^k$ for each $k$. It follows that each of the monomials $a_0$, $a_1n$, $a_2n^2$, $\ldots$ are elements of $K$, so the function $g_k(n)\equiv a_kn^k$ is happy for each $k$. It follows that either $f\equiv d$ or $f(n)\equiv10^en+d$ for some $e$, $d$, and we can directly check that if $d\ne0$, then $d<10^e$ and $d\in K$.

Why "Sad Number Theory"?

Literally the easiest problem from usamo 2019, but also the most annoying one indeed. For every polynomial with the degree of 2 or higher, plugging in x with a sufficiently big power of 10 "isolates" the contribution of every anx^n to the total.

shalomrav wrote: Why "Sad Number Theory"? The opening poster, tastymath75025, generally posts "Sad" before the subject of any problem.

The answers are $f(x)=c$ $f(x)=10^ax+b$ where $b<10^a$ and $b\in K\cup\{0\}$, obviously they satisfy the condition. We call a polynomial good if it satisfies the condition and bad if there exists $n$ such that $n\in K$ but $f(n)\notin K$, and very bad if there exists infinitely many such $n$. Firstly, for all $x\in\mathbb R_{>0}$ define $$g(x)=\frac{x}{10^{\log_{10}x}}$$and $$h(x)=\log_{10}x$$then $x=f(x)\cdot 10^{g(x)}$. Lemma. If $a,b>10$ satisfies $8a=7b$ and $\frac{a}{7}$ is not a power of $10$ then there exists some integers $a<c<b$ such that $c\in K$. Proof. Obvious. Claim. $f(x)=ax$, where $a$ is not a power of $10$ and $f(x)=ax^n$, where $a$ is an integer are all very bad. Proof. Firstly, for the linear polynomial case, we claim that there exists some $n\in K$ and $b\in\mathbb N$ such that $$7\times 10^b<an<8\times 10^b$$Indeed, by the lemma there exists some $n\in K$ such that $\frac{7\times 10^b}{a}<n<\frac{8\times 10^b}{a}$ as desired. Now for $n=2$, notice that at least one of $2a$ and $8a$ is not a power of $10$. Suppose $2a$ is not a power of $10$, by the linear case there exists $x\in K$ such that $2ax\notin k$, then pick a sufficiently large integer $b$ with $10^{b}>2x$, we have $$a(10^b+x)^2=a10^{2b}+2ax\cdot 10^b+ax^2$$since $b$ is sufficiently large, $2ax$ is a substring of $a(10^b+x)^2$ and so $a(10^b+x)^2$ contains a $7$ in its decimal representation since $2ax$ does, the case when $8a$ is not a power is similar. We now proceed by induction on $n$, the base case $n=2$ is proved already. Now suppose the case $n-1$ holds let's consider the case $n$. The idea is similar to the case in $n=2$. Indeed, by inductive hypothesis there exists $n\in K$ such that $anx^{n-1}\notin K$. Therefore, pick a sufficiently large $b$ such that $$\binom{n}{2}10^b>nx$$we have $$a(10^b+x)^n=...+a\binom{n}{2}10^{2b} x^{n-2}+an10^bx^{n-1}+x^n$$Then since $b$ is sufficiently large $anx^{n-1}$ is a substring of $a(10^b+x)^n$, so using similar reasoning we have $a(10^b+x)^n\notin K$. $\blacksquare$ Now suppose $f(x)=\sum_{i=0}^na_ix^i$, if some of the $a_ix^i$ are of one of the form in the Claim, then there exists some $x\in K$ such that $a_ix^i\notin K$, again using the same reasoning we have that $a_ix^i$ is a substring of $f(10^b+x)$ for some sufficiently large integer $b$, but $10^b+x\in K$, contradiction. Therefore, it is easy to see that the polynomial must be as the form claimed.

Redefine $K$ as the set of all nonnegative integers not containing the digit $7$ in their base-$10$ representation for convenience so we can eliminate the $0$ polynomial afterward. Claim: Monomials $cx^d$ with $d\ge 2,c\ge 1$ are bad. Solution: For $d=2$, note there certainly exists an integer $t$ such that $tc$ begins with $7$ even if $c\in K$. Then pick sufficiently large integral $e$ and note that \[\left(10^{(t-1)e}+10^{(t-2)e}+\cdots+1\right)^d = \sum_{i=0}^{2t-2} (t-|i-(t-1)|)10^{ie},\]so multiplying through by $c$ certainly yields a choice of $cx^d$ not in $K$. Now, suppose a monomial $cx^d$ with $d\ge 3$ is good. We claim that $cdx^{d-1}$ is also good. For any fixed $n$, pick sufficiently large $e$ and use the fact that $c(10^en+1)^d\in K$ to yield that result. By iterating this implies the desired. $\fbox{}$ Claim: If polynomial $f=\sum_{i=0}^n a_ix^i$ with $a_n$ nonzero is good, then each $a_ix^i$ is good. Solution: For fixed $n$, we show $a_in^i$ is good by taking $f(10^en)$ for large $e$. $\fbox{}$ Thus we only have to consider linear or constant polynomials by the first claim. Certainly all $f\equiv k$ for $k\in K$ work, so now we work with polynomials $cx+d$: we need $cx$ and $d$ to be good by the second claim. Clearly $d$ is good iff $d\in K$. Claim: If $cx$ is good with $c\ge 1$, then $c$ is a power of $10$. Solution: It is clear that $c\in K$ by setting $x=1$. Let $t$ denote the minimal positive integer with $c^t\not\in K$, which exists by Kronecker's Approximation Theorem on $p,q$ existing with $|q\log_{10} c-p-\log_{10} 7.5|<\epsilon$ for any $\epsilon$ unless $c$ is a power of $10$. Then $c^t = c\cdot c^{t-1}$ contradicts the assumption that $cx$ is good, so done. $\fbox{}$ Claim: $d<c$. Solution: Suppose otherwise. It is clear that for any $k\in K$, $k+K\not\subseteq K$ because then $tk\in K$ for all $t$ which is absurd, so since the portion of $d$ that is added to the ending of $x$ in this case would have to be nonzero, we have a contradiction. $\fbox{}$ So the only solutions are of the form $f(x)=10^ex+k$ with integral $e,k\ge 0$, $k<10^e$, and $k\in K$, and of the form $f(x)=k$ with $k\ge 1$ and $k\in K$.

Call such polynomials good First, put $n = 10^kx$ so the polynomial just outputs the individual terms with $0$'s in between, so every term itself must be good. Say $f(x) = cx^d$ is good, then put $x = 10^k + p$ so we get that the linear term in it is also good. So we will first classify every linear(with constant term $0$) that works. I claim that $f(x) = 10^kx$ is the only such thing. Suppose not, and let $f(x) = cx$, then divide through by any factors of $10$ in $c$. Let $N$ be a sufficiently large number and consider the set of numbers $n$ such that $7.10^N \le cn \le 8.10^N$, there must be at least $\frac{10^N}{c} - 1$ such numbers. But if $f$ was good, then none of these numbers could have had a $7$ in their base $10$ representation, but its easy to see that unless $c$ is a power of $10$, this cant have happened. So suppose $f(x) = cx^d$ works, then putting $x = 10^k + p$ as before, we have that the coefficients must all be powers of $10$ but this can easily be seen to be impossible unless $d \le 1$. So, every term of the polynomial is either linear or constant. So the only solutions are $f(x) = 10^kx + c$ with $10^k > c$, so we are done. $\blacksquare$

Call such polynomials good. Claim: If the polynomial $a_n x^n+a_{n-1}x^{n-1}+\ldots a_1 x+a_0$ is good, then each of the monomials are good. Set $x$ as $10^e x$, where $e$ is sufficiently large. Then $f(10^e x)$ will have $a_0,a_1,a_2\ldots, a_n$ with some zeroes padded in between. First we will work on the linear polynomials. We claim that if $f(x)=cx$ is good, then $c=10^e$. We will actually show that if not, we can find an $x$ so that $cx$ has leading digit $7$. If $9\cdot10^e\le x<10\cdot10^e$, then we pick $x=8$. If $8\cdot10^e\le x< 9\cdot10^e$, then we pick $x=88$ If $7\cdot10^e\le x<8\cdot10^e$, then we pick $x=1$. If $6.4\cdot10^e\le x<7\cdot10^e$, then we pick $x=11$. If $5.9\cdot10^e\le x<6.4\cdot10^e$, then we pick $x=12$. ' If $5.7\cdot10^e\le x<5.9\cdot10^e$, then we pick $x=13$. If $5\cdot10^e\le x<5.7\cdot10^e$, then we pick $x=14$. If $4.4\cdot10^e\le x<5\cdot10^e$, then we pick $x=16$. If $3.9\cdot10^e\le x<4.4\cdot10^e$, then we pick $x=18$. If $3.8\cdot10^e\le x<3.9\cdot10^e$, then we pick $x=20$. If $3.4\cdot10^e\le x<3.8\cdot10^e$, then we pick $x=21$. If $3.1\cdot10^e\le x<3.4\cdot10^e$, then we pick $x=23$. If $2.8\cdot10^e\le x<3.1\cdot10^e$, then we pick $x=25$. If $2.5\cdot10^e\le x<2.8\cdot10^e$, then we pick $x=28$. If $2.2\cdot10^e\le x<2.5\cdot10^e$, then we pick $x=32$. If $1.95\cdot10^e\le x<2.2\cdot10^e$, then we pick $x=36$. If $1.71\cdot10^e\le x<1.95\cdot10^e$, then we pick $x=41$. If $1.6\cdot10^e\le x<1.71\cdot10^e$, then we pick $x=46$. If $1.4\cdot10^e\le x<1.6\cdot10^e$, then we pick $x=50$. If $1.25\cdot10^e\le x<1.4\cdot10^e$, then we pick $x=56$. If $1.1\cdot10^e\le x<1.25\cdot10^e$, then we pick $x=64$. If $1\cdot10^e<x<1.1\cdot10^e$, then we pick $x=69999\ldots$ for sufficiently many $9$'s. So we have shown that $f(x)=cx$ is good iff $c$ is a power of $10$. Now suppose $\deg(f)>1$ and $f(x)=ax^d$. Then we set $x=10x+3$. So $f(x)=a(10x+3)^d$. We note that all the terms here must be good. Looking at the term $a\cdot d\cdot3^{d-1}\cdot10x$, we find that this must also be good. Thus, by our claim for the linear polynomials, $a\cdot d\cdot 3^{d-1}\cdot 10$ must be a power of $10$, so $d=1$, a contradiction. So $\deg(f)\in\{0,1\}$. Case 1: $\deg(f)=0$. Then $f$ is a constant polynomial, so $\boxed{f\equiv c}$, where $c\in K$, which works. Case 2: $\deg(f)=1$. We must have $f(x)=kx+c$, where $c\in K \text{ or }c=0$ and $k$ is a power of $10$. Suppose $e$ is some non negative integer. This gives the solutions, $\boxed{f(x)=10^e x+c}$ for all $c\in K$ and $e>\log_{10}(c)$ (it's easy to see that $e\le \log_{10}(c)$ doesn't work) and $\boxed{f(x)=10^e x}$, which both work.

Solved with rama1728. Call polynomials satisfying the given cool. The only cool polynomials are $f(x) = 10^ex,$ $f(x) = k,$ or $f(x) = 10^ex +k,$ where $k$ is any integer $\in K,$ $e$ is any nonnegative integer, and in the last case, $10^e> k.$ It's easy to see these work. Claim: If $f(x)=\sum_{i=0}^{\deg(f)} a_ix^i$ is cool, then each individual $a_ix^i$ is cool. Proof: Take any $n \in K.$ If $a_in^i$ contains the digit $7,$ then $f(10^en)$ contains the digit $7$ for large enough $e.$ $\square$ Claim: If $a_1x$ is cool, $a_1$ is a power of $10.$ Proof: Otherwise, $\log_{10}{a_1}$ is irrational. Note that the first digit of a positive integer $x$ is $7$ iff $\log_{10}7 \le \{\log_{10}x\} < \log_{10}{8}.$ Also, $a_1^1, a_1^2, a_1^3, \dots $ must all be $\in K$ (just induct) so their first digits are all $\ne 7.$ But this is contradiction: there must be a positive integer $b$ where $\log_{10}7 \le \{b\log_{10}x\} < \log_{10}{8}.$* Then $a_1^{b}$ has first digit $7.$ $\square$ Claim: For any integer $d > 1,$ $a_dx^d$ can never be cool. Proof: If $a_dx^d$ is cool, then $a_d(10x+9)^d$ is cool. But if $d>1,$ the linear term of this polynomial has a coefficient that is a multiple of $9$ and cannot be a power of $10.$ $\square$ So $f(x)$ has degree $0$ or $1.$ If $f(x)$ is constant, the constant is obviously $\in K.$ If $f(x)$ is linear with nonzero constant term, $f(x) = 10^e x + k$ for some $e \ge 0$ and $k \in K.$ Let $10^{g} \le k < 10^{g+1}$ for an integer $g.$ Let $t_1$ be the first digit of $k.$ If $g \ge e$ then consider some digit $t_2 \ne 7$ such that $t_1 + t_2 \equiv 7 \pmod{10};$ this exists since $t_1 \ne 0.$ Then $f(t_2 \cdot 10^{g-e})$ has a $10^{g}$ digit of $7,$ contradiction. So only the three possibilities outlined at the start are possible. $\blacksquare$ *Remark: See my solution to China TST 2017 Test 2 Day 2 P6 for more on this idea.

v_Enhance wrote: The answer is only the obvious ones: $f(x) = 10^ x*y$, $f(x) = k*y$, and $f(x) = 10^ x*y + k$, for any choice of $k \in K$ and $e > \log_{10} k$ and y belonging to K. (with $e \ge 0$) Now assume $f$ satisfies $f(K) \subseteq K$; such polynomials will be called stable. We first prove the following claim which reduces the problem to the study of monomials. Lemma: [Reduction to monomials] If $f(x) = a_0 + a_1 x + a_2 x^2 + \dots$ is stable, then each monomial $a_0$, $a_1 x$, $a_2 x^2$ is stable. Proof. For any $x \in K$, plug in $f(10^e x)$ for large enough $e$: the decimal representation of $f$ will contain $a_0$, $a_1 x$, $a_2 x^2$ with some zeros padded in between. $\blacksquare$ Let's tackle the linear case next. Here is an ugly but economical proof. Claim: [Linear classification] If $f(x) = cx$ is stable, then $c = 10^e$ for some nonnegative integer $e$. Proof. We will show when $c \ne 10^e$ then we can find $x \in K$ such that $cx$ starts with the digit $7$. This can actually be done with the following explicit cases in terms of how $c$ starts in decimal notation: For $9 \cdot 10^e \le c < 10 \cdot 10^e$, pick $x = 8$. For $8 \cdot 10^e \le c < 9 \cdot 10^e$, pick $x = 88$. For $7 \cdot 10^e \le c < 8 \cdot 10^e$, pick $x = 1$. For $4.4 \cdot 10^e \le c < 7 \cdot 10^e$, pick $11 \le x \le 16$. For $2.7 \cdot 10^e \le c < 4.4 \cdot 10^e$, pick $18 \le x \le 26$. For $2 \cdot 10^e \le c < 2.7 \cdot 10^e$, pick $28 \le x \le 36$. For $1.6 \cdot 10^e \le c < 2 \cdot 10^e$, pick $38 \le x \le 46$. For $1.3 \cdot 10^e \le c < 1.6 \cdot 10^e$, pick $48 \le x \le 56$. For $1.1 \cdot 10^e \le c < 1.3 \cdot 10^e$, pick $58 \le x \le 66$. For $1 \cdot 10^e \le c < 1.1 \cdot 10^e$, pick $x = 699\dots9$ for suitably many $9$'s. \qedhere $\blacksquare$ The hardest part of the problem is the case where $\deg f > 1$. We claim that no solutions exist then: Claim: [Higher-degree classification] No monomial of the form $f(x) = cx^d$ is stable for any $d > 1$. Proof. Note that $f(10x+3)$ is stable too. We have \[ f(10x+3) = 3^d + 10d \cdot 3^{d-1} \cdot x + 100 \binom d2 \cdot 3^{d-1} x^2 + \dots. \]and so on. By applying the lemma the linear monomials $10d \cdot 3^{d-1} x$ is stable, hence $10d \cdot 3^{d-1}$ is a power of $10$, which can only happen if $d = 1$. $\blacksquare$ Thus the only nonconstant stable polynomials with nonnegative coefficients must be of the form $f(x) = 10^e x + k$ for $e \ge 0$. It is straightforward to show we then need $k < 10^e$ and this finishes the proof.

I dare people to get more unrigorous than this solution: $f(x) \approx ax^n$. Therefore since $x \approx \sqrt[n]{\frac{x}{a}}$, we have that $\forall r \in \mathbb{N}, \exists s \in \mathbb{Z}$ s.t. $10^{r+sn} \frac{1}{8^{n-1}} \leq a \leq 10^{r+sn} \frac{1}{7^{n-1}}$ for large $x$ since the first digit of the output cannot be $7$ and the intervals become roughly continuous. Obviously at some $r$, $s$ needs to decrease, but then for $n \geq 2$ we have $10^{r+1+(s-1)n}\frac{1}{7^{n-1}} < 10^{r+sn}\frac{1}{8^{n-1}}$ since $70^{n-1} > 8^{n-1}$ which is a contradiction, so $n = 1$. With the same bounding argument, we get $a = 10^r$ for some nonnegative integer $r$, so a trivial check suffices to obtain the answer set.

Let $K \ni f(x)=a_0+a_1x+...+a_nx^n$ where $a_i \in Z_{\ge0},x\in K$.Call such $f$ good. Note that if $x\in K$, then $10^mx \in K$.Now, if we choose bigger enough $m$ and let $x \rightarrow 10^mx$, the expressions $a_0,a_1x,...,a_nx^n$ will have mutliple $0$s between them, forcing $a_ix^i$ be a good polynomial. If $ \deg \{f\}=0$, clearly $f \equiv x$ for any $x \in K$. If $ \deg \{f \}=1$, I claim that $ f \equiv 10^mx+y$ for any $x,y \in K, \log(y)<m$. Assume otherwise, then $f=cx$, $c \neq 10^m$ is good.Letting $x=1,10,10^2,...$ forces $c,c^2,...$ be good. Then for any $k \in \mathbb{N}$, we have $$ c^k \notin [10^m7, 10^m8)$$Take $log_{10^m}$ of both sides, we have $k \log_{10^m}(c) \notin [7,8)$. But since $\log_{10^m}(c)$ is irrational, $k \log_{10^m}(c)$ is not cyclic and is additive, hence it is dense in $[7,8)$, meaning there is infinitely many $k$ such that $k \log_{10^m}(c) \in [7,8)$ , contradiction. Hence $\log_{10^m}(c)$ is rational $\rightarrow$ $c=10^m$, rest is obvious.(using equidistribution is possible too) If $ d=\deg \{ f \} \ge 2$, let $x=10^mk+7$, Then $(10^mk+7)^d$ is good. Expanding, we have: $$(10^mk)^d+...+10^mk d7^{d-1}+7^d$$Choosing arbitraryly bigger $m$, we can conclude each of the expressions above are good, hence $10^mk7^{d-1}$ is good. Since this expression is degree $1$, we must have $10$ power of leading coefficient, therefore $d=1$, hence $\ge2$ is impossible

Let $f(x) = a_nx^n + \cdots + a_1x + a_0$ Lemma: For any $a \geq 2$ there is some $k \in K$ where $ak \not \in K$. Assume WLOG that $10$ does not divide $a$. If $a \not \equiv 1 \pmod{10}$ then we can fix some $k \leq 10$ and not equal to $7$, so $k \in K$, such that $ak \equiv 7 \pmod{10}$ and thus $ak \not \in K$. Now, assume $a \equiv 1 \pmod{10}$. Now, the only case that's left is if $a \equiv 1 \pmod{10}$. Note that $a$ can be expressed as $\overline{b1}$ for some other positive integer $b$. If $b \not \equiv 1 \pmod{10}$ then we can treat $b$ as the previous case and just ignore the last digit. Thus, the only case that's not covered is $a=\overline{11 \cdots 11}$ which are all covered by $k=16 \in K$. We get $ak = \overline{177 \cdots 76} \not \in K$ $\square$ Claim: $a_n x^n \in K$ for all $x \in K$ Indeed, let $N$ be a sufficiently large positive integer. For any $x \in K$ consider \[ f(x \cdot 10^N) = \overline{(a_n x^n) 000 \cdots} \implies a_nx^n \in K\] $\square$ Now, fix a sufficiently large positive integer $M$ and set $x =10^M + r$ for some $r \in K$. Note that $x \in K$. So, \[ a_n \left ( 10^M + r \right )^n \in K \implies \overline{(a_n)000 \cdots 000(na_nr)000 \cdots} \implies na_nr \in K\]if we let $L = na_n$ then we have $Lr \in K$ for all $r \in K$ which contradicts our lemma.

The answer is $f(x) = 10^nx + k$ and $f(x) = k$ for $k \in K$ and $\log_{10}(k) < n$. Label a polynomial $f$ as being sad if it satisfies the property in the problem statement. Notice that if $f(10^nk) \in K$ over all $k$ then $f(k)$ is sad as we can just remove the trailing zeroes. Let $f(x) = \sum_i a_ix^i$ be some sad polynomial. Then note that $f_i(x) = a_ix^i$ must also be sad as we can plug in $f(10^nc)$ for sufficiently large $n$ to obtain all $f_i(c)$ strung together with zeroes in between. Varying $c$ gives us that $f_i(x)$ must also be sad over all $i$, so it suffices to just work on the case where $f$ is a monomial(since we wish to show that $f$ is linear or constant). We will now resolve the case where $deg(f) = 1$. Let $f(x) = cx$, and WLOG $c$ is some terminating decimal $1 < c < 10$ since $c = 1, 10$ can be easily checked to work. Then we will show that letting $x = c^n$ for some choice of $n$ will work; it is sufficient to prove that $m + \log_{10}(7) \leq n\log_{10}(c) < m + \log_{10}(8)$ as this implies that the leading digit of $c^n$ is $7$. However, this is clearly true as $log_{10}(c)$ is irrational, so the fractional part of $n\log_{10}(c)$ is dense over $[0, 1]$ so the fractional part must lie in interval $[\log_{10}(7), \log_{10}(8)]$ as desired. Thus if $c$ is not a power of $10$, we will be able to find $x \in K$ so that $f(x) \not{\in} K$ if $f$ is linear. So now we will show that all monomials $f(x)$ must have degree $0$ or $1$. First let $f(x) = cx^n$ for $n > 1$. Notice that if $f(x) = cx^n$ is sad, then so is $g(x) = c(10x + 9)^n$ since $x \in K$ implies $10x + 9 \in K$. We can expand via binomial theorem to get that the linear coefficient of $g(x)$ is $9^{n-1} \cdot 10c$. However from our previous claims we know that $g_1(x) = 9^{n-1} \cdot 10cx$ must be sad so $9^{n-1} \cdot 10c$ must be a power of $10$ which implies that $n = 1$ which is a contradiction. So then the degree of $f$ is either $1$ or $0$. If $deg(f) = 0$ then $f(x) = k$ for any $k \in K$ is the only thing that works clearly. From earlier we know that if $deg(f) = 1$ then we must have that the linear coefficient is a power of $10$ and our constant term cannot have more digits than the number of trailing zeroes clearly which leads to $\log_{10}(k) < n$ where $k$ is our constant, done.