We say a non-negative integer $n$ "contains" another non-negative integer $m$, if the digits of its decimal expansion appear consecutively in the decimal expansion of $n$. For example, $2016$ contains $2$, $0$, $1$, $6$, $20$, $16$, $201$, and $2016$. Find the largest integer $n$ that does not contain a multiple of $7$.
Problem
Source:
Tags: Mexico, number theory
Continuum
18.11.2016 11:15
let the number be $N=\overline{a_1 a_2\dots a_n}$ it is obvious that there is no $$a_i \equiv 0\pmod{7}$$next, if there exist $$a_i+a_{i+1}+\dots+a_j \equiv a_i+a_{i+1}+\dots+a_k\pmod{7}$$we get that $$a_{j+1}+a_{j+2}+\dots+a_k \equiv 0\pmod{7}$$so if $n \geq 7$ then we get $\{a_1,a_1+a_2,a_1+a_2+a_3,\dots,a_1+a_2+\dots+a_7\}$ is a complete residue system$\mod{7}$ so we get that $N$ contains a multiple of $7$. This means the largest $N$ is $999999$ WRONG
EDIT:the proof above is false(because i misunderstood the problem ) correct(?) proof is below
let the number be $N=\overline{a_na_{n-1}\dots a_1}$ it is obvious that there is no $$a_i \equiv 0\pmod{7}$$next, if there exist $$a_j\times10^{j-1}+a_{j-1}\times10^{j-2}+\dots+a_i\times10^{i-1} \equiv a_k\times10^{k-1}+a_{k-1}\times10^{k-2}+\dots+a_i\times10^{i-1}\pmod{7}$$$j>k$ we get that $$a_{j}\times10^{j-1}+a_{j-1}\times10^{j-2}+\dots+a_k\times10^{k-1} \equiv 0\pmod{7}$$so if $n \geq 7$ then we get $\{a_1,a_1+a_2\times 10,a_1+a_2\times 10+a_3\times 10^2,\dots,a_1+a_2\times 10+\dots+a_7\times 10^6\}$ is a complete residue system$\mod{7}$ so we get that $N$ contains a multiple of $7$. This means the largest $N$ is $999993$
ralk912
18.11.2016 11:40
Yes to the argument, however $999999$ is divisible by $7$. The answer is $999993$.
ilikemath40
13.09.2021 04:17
Notice that $111111 \equiv 0 \pmod{7}$. Thus we can use the number $99999$ as the "base" number and add digits to this "base" number. Testing out the digits from $0-9$ we see that only $3$ works. Then we have the number $999993$ as the new "base" number. Testing out the digits we don't see any of them that work and we can conclude that $999993$ is the largest such number.