Maximum number of m-tastic numbers

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

311,486 topics

12 users

TOPICS

No tags match your search

Maximum number of m-tastic numbers

G H J

Reveal topic tags

IMO Shortlist

number theory

decimal representation

Digits

IMO

IMO 2017

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2017 N4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Tsukuyomi

31 posts

Tsukuyomi

#1 h Jul 10, 2018, 1:11 PM • 6 Y

Y by a28546, anantmudgal09, donotoven, megarnie, RedFlame2112, Adventure10

Call a rational number short if it has finitely many digits in its decimal expansion. For a positive integer $m$ , we say that a positive integer $t$ is $m-$ tastic if there exists a number $c\in \{1,2,3,\ldots ,2017\}$ such that $\dfrac{10^t-1}{c\cdot m}$ is short, and such that $\dfrac{10^k-1}{c\cdot m}$ is not short for any $1\le k<t$ . Let $S(m)$ be the set of $m-$ tastic numbers. Consider $S(m)$ for $m=1,2,\ldots{}.$ What is the maximum number of elements in $S(m)$ ?

This post has been edited 2 times. Last edited by v_Enhance, Jan 20, 2022, 1:01 AM
Reason: fix "the the"

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Generic_Username

1088 posts

Generic_Username

#2 h Jul 10, 2018, 6:53 PM • 9 Y

Y by qubatae, pad, PIartist, donotoven, RedFlame2112, sabkx, Adventure10, Mango247, MS_asdfgzxcvb

We claim that the largest possible value of $|S(m)|$ is $807.$ Since powers of $2,5$ that divide $c,m$ don't change the short-ness of a rational number, we only consider $\gcd(c,10)=\gcd(m,10)=1.$ Then for each $(c,m),$ by the uniqueness of the order, $t$ is uniquely determined. This proves that $|S(m)|\leq |\{1\leq c\leq 2017 | \gcd(c,10)=1\}|=2017-\left\lfloor\frac{2017}{2}\right\rfloor-\left\lfloor\frac{2017}{5}\right\rfloor+\left\lfloor\frac{2017}{10}\right\rfloor=807.$
We now show this is achieveable by choosing $m$ such that $\text{ord}_{10}(cm)$ is distinct for all $c$ with $\gcd(10,c)=1,c\leq 2017.$ Indeed, let $P$ be the set of all primes less than or equal to $2017,$ and let $m=\left(\prod_{p \in P}p\right)^{n}$ for sufficiently large $n.$ Before showing this works, we need two lemmas on orders:

Lemma 1: For relatively prime integers $a,b,$ we have $\text{ord}_{10}(ab)=\text{lcm}(\text{ord}_{10}(a),\text{ord}_{10}(b)).$
Proof: Since $a|10^{\text{ord}_{10}(ab)}-1,$ we see that $\text{ord}_{10}(a)|\text{ord}_{10}(ab)$ (else minimality is contradicted by Euclidean algorithm). Similarly, $\text{ord}_{10}(b)|\text{ord}_{10}(ab)$ and minimality concludes.

Lemma 2: Let $p$ be a prime relatively prime to $10,$ and let $k=\nu_p(10^{\text{ord}_{10}(p)}-1).$ Then for all $m\geq k,$ $\nu_p(10^{\text{ord}_{10}(p^m)}-1)=m.$
Proof: We proceed by induction on $m.$ Since $\text{ord}_{10}(p^k)|\text{ord}_{10}(p^{k+1}),$ LTE gives us
$\begin{align*}m+1&\geq \nu_p(10^{\text{ord}_{10}(p^{m+1})}-1)\\&=\nu_p((10^{\text{ord}_{10}(p^m)})^{\frac{\text{ord}(p^{m+1})}{\text{ord}(p^m)}}-1) \\&=\nu_p\left(\frac{\text{ord}_{10}(p^{m+1})}{\text{ord}_{10}(p^{m})}\right)+\underbrace{\nu_p(10^{\text{ord}_{10}(p^m)}-1)}_{=m}.\end{align*}$
But $\text{ord}_{10}(p^{m+1})=p\cdot\text{ord}_{10}(p^m)$ works, and it is minimal. This proves the lemma, and it proves the more useful fact that $\boxed{\text{ord}_{10}(p^m)=p^{m-k}\cdot\text{ord}_{10}(p^{k})}$ for $m>k.$

Returning back to the problem at hand, assume $\text{ord}_{10}(am)=\text{ord}_{10}(bm)$ for some $a\neq b.$ Let $p$ be a prime s.t. $\nu _p(a)>\nu _p(b),$ and let $a=\prod_{p_i\in P}p_i^{a_i}$ By lemma 1, we have
$\nu_p(\text{ord}_{10}(am))=\nu_p(\text{lcm}_i(\text{ord}_{10}(p_i^{a_i+n})))=\text{max}(\nu_p(\text{ord}_{10}(p_i^{a_i+n}))).$
By the boxed statement in lemma 2, taking $n$ sufficiently large will cause the maximum power of $p$ among the $\text{ord}(p_i),$ to come from $p_i=p,$ since increasing $n$ increases only $\text{ord}_{10}(p^{\nu_p(a)+k}).$ But now lemma 2 again gives $\begin{align*}\nu_p(\text{ord}_{10}(am))&=\nu_p(\text{ord}_{10}(p^{\nu_p(a)+k}))\\&=\nu_p(a)+n-k+\nu_p(\text{ord}(p^k))\\&>\nu_p(b)+n-k+\nu_p(\text{ord}(p^k))\\&=\nu_p(\text{ord}_{10}(p^{\nu_p(b)+k}))\\&=\nu_p(\text{ord}_{10}(bm)),\end{align*}$ an evident contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

juckter

322 posts

juckter

#3 h Jul 10, 2018, 7:56 PM • 4 Y

Y by donotoven, RedFlame2112, Adventure10, Mango247

First, some definitions. Say a number is simple if it is relatively prime to $10$ . Denote by $d(n)$ the largest simple divisor of a number $n$ . Given a positive integer $k \in \{1, 2, \dots, 2017\}$ , we will say that $k$ enables $t$ if $t$ is $m$ -tastic when choosing $c = k$ . Notice that a rational number $r$ is short if and only if $10^nr \in \mathbb{Z}$ for some $n$ . This implies that $\frac{10^t - 1}{cm}$ is short if and only if

$v_p(cm) \leq v_p(10^t - 1)$
Holds for every prime $p$ other than $2$ and $5$ . Notice that each element of $\{1, 2, \dots 2017\}$ enables at most one integer, because if it enabled two integers $a < b$ then $a$ being $m$ -tastic would contradict the fact that $b$ is the smallest integer $t$ such that $\frac{10^t - 1}{cm}$ is short. We now claim that for any $k$ , if $k$ enables $t$ then $d(k)$ enables $t$ . Assume for the sake of contradiction that $t$ is not $m$ -tastic for $c = d(k)$ . Clearly

$\frac{10^t - 1}{md(k)}$
Is short, because it is an integer multiple of $\frac{10^t - 1}{mk}$ , which is short. Because $t$ is not $m$ -tastic under $c = d(k)$ , it follows that there must exist an $s < t$ such that $\frac{10^s - 1}{md(k)}$ is short. Because $\frac{k}{d(k)}$ has no primes other than $2$ or $5$ , it follows that $\frac{10^s - 1}{mk}$ is also short. However this contradicts the fact that $t$ is $m$ -tastic. Thus the claim is proven. It follows that every $m$ -tastic number has a simple enabler, and thus the quantity of $m$ -tastic numbers is less than or equal to the number of simple elements of $\{1, 2,\dots, 2017\}$ , which is

$2017 - \left\lfloor \frac{2017}{2} \right\rfloor - \left\lfloor \frac{2017}{5} \right\rfloor + \left\lfloor \frac{2017}{10} \right\rfloor = 2017 - 1008 - 403 + 201 = 807$
We now exhibit an $m$ for which there exist $807$ $m$ -tastic numbers, which completes the problem. Let $S$ be the set of primes less than or equal to $2017$ and let $P$ be the product of all elements of $S$ . Then $\gcd(P, 10) = 1$ and thus $10$ has a multiplicative order $\pmod{P}$ . Let $g$ be this order, and set

$m = \prod_{p \in S} p^{v_p(10^g - 1)}$
We claim that each simple $c \in \{1, 2, \dots, 2017\}$ enables $gc$ . Assume that $\frac{10^t - 1}{cm}$ is short, then $v_p(c) + v_p(m) = v_p(cm) \leq v_p(10^t - 1)$ . In particular every prime in $S$ must divide $10^t - 1$ , and therefore $g$ must divide $t$ . Let $t = gk$ . Then by LTE, for every $p \in S$ we have $v_p(10^{gk} - 1) = v_p(10^g - 1) + v_p(k) = v_p(m) + v_p(k)$ by our choice of $m$ . Thus $v_p(k) \geq v_p(c)$ for each $p \in S$ , and because all prime factors of $c$ are in $S$ it follows that this happens if and only if $c$ divides $k$ , and so $gc$ is indeed the smallest number for which the required expression is short. It follows that $c$ enables $gc$ , implying that there are exactly $807$ $m$ -tastic numbers, because the numbers $gc$ are all distinct.

This post has been edited 1 time. Last edited by juckter, Jul 10, 2018, 7:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MarkBcc168

1594 posts

MarkBcc168

#4 h Jul 11, 2018, 1:51 PM • 3 Y

Y by neyft, RedFlame2112, Adventure10

Really tastic problem, with rich flavor of number theory.

The answer is $\boxed{807}$ . First, we can made the assumption that $\gcd(m,10)=1$ . Call the number $c$ as \emph{chef} of $t$ . For convenience, let $\mathcal{C}=\{n\in\mathbb{Z}^+\mid n\leqslant 2017,\ \gcd(n,10)=1\}$

Note that if $c$ is a chef of $t$ , then $c'= \frac{c}{2^a5^b}$ is also a chef of $t$ . Thus WLOG, we can assume that $\gcd(c,10)=1$ .

Now observe that if $c\in\mathcal{C}$ is a chef of $t$ then $\gcd(cm,10)=1$ so
$cm\mid 10^t-1 \text{ but } cm\nmid 10^k-1\text{ for any }k<t \implies t=\mathrm{ord}_{cm}(10).$ Thus each $c\in\mathcal{C}$ is a chef of a unique tastic number $t$ . Hence $S(m)\leqslant |\mathcal{C}| = 807$ claimed.

Now we have to construct $m$ which $\mathrm{ord}_{cm}(10)$ are all distinct for each $c\in\mathcal{C}$ . To do that, we enumerate primes $p_1<p_2<...<p_k = 2017$ , disregarding $2,5$ . And define
$a_i = \nu_{p_i}(10^{p_i-1}-1)\text{ for each } i =1,2,...,k$ By Lifting The Exponent Lemma, we easily find that
$\nu_{p_i}(a^n-1) = a_i + \nu_{p_i}(n)\implies \mathrm{ord}_{p^t}(10) = {p_i}^{t-a_i}(p_i-1)$ for any $t\geqslant a_i$ . Now for each $i=1,2,...,k$ , let $b_i= a_i + 2018$ and let $m=\prod\limits_{i=1}^k {p_i}^{b_i}$ . From discussions above, we get
$\mathrm{ord}_{cm}(10) = \mathrm{lcm} \{{p_i}^{c_i+2018}(p_i-1)\}$ where $c_i = \nu_{p_i}(c)$ . Since $v_{p_i}(p_j-1)<2018$ for any $i,j\leqslant k$ , we get
$\nu_{p_i}(\mathrm{ord}_{cm}(10)) = c_i+2018 = \nu_{p_i}(c)+2018$ so for any prime $p\in \{p_1,p_2,...,p_k\}$ ,
$\nu_{p}(\mathrm{ord}_{c_1m}(10)) = \nu_{p}(\mathrm{ord}_{c_2m}(10)) \iff \nu_{p}(c_1) = \nu_{p}(c_2).$ But this is true for arbitrary prime $p$ which may divide some elements in $\mathcal{C}$ so the numbers $\{\mathrm{ord}_{cm}(10)\mid c\in\mathcal{C}\}$ are distinct as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6870 posts

v_Enhance

#5 h Jul 11, 2018, 6:51 PM • 9 Y

Y by pavel kozlov, mijail, v4913, PIartist, HamstPan38825, RedFlame2112, sabkx, Adventure10, Funcshun840

The answer is $807$ .

We restrict our attention to $c$ and $m$ such that $\gcd(c,10) = \gcd(m,10) = 1$ , since stripping factors of $2$ or $5$ doesn't change anything. In that case, since $t$ is determined by $c$ and $m$ in a fantastic triple (the order of $10 \pmod{cm}$ ), we have $\begin{align*} \#S(m) &\le \#\{ 1 \le c \le 2017 \mid \gcd(c,10) = 1 \} \\ &= 2017 - \left\lfloor \frac{2017}{2} \right\rfloor - \left\lfloor \frac{2017}{5} \right\rfloor + \left\lfloor \frac{2017}{10} \right\rfloor \\ &= 807. \end{align*}$ The main point of the problem is to achieve this bound.

Let $T$ be a large composite integer such that $M = 10^T - 1$ is divisible by every primes at most $2017$ other than $2$ and $5$ . (Thus $T$ is the order of $10 \pmod M$ .)

Claim: The order of $10 \pmod{cM}$ is $cT$ .

Proof. This essentially follows by exponent lifting lemma. Indeed, the order of $10 \pmod{cM}$ must be divisible by $T$ . Now pick a prime $p \mid c$ . If $T'$ is the order of $10 \pmod{cM}$ , then $T'$ must be divisible by $T$ ; now compute $\begin{align*} \nu_p(c) + \nu_p(M) &\le\nu_p(10^{T'}-1) \\ &= \nu_p\left( (10^T)^{T'/T} - 1 \right) \\ &= \nu_p (10^T-1) + \nu_p(T') - \nu_p(T) \\ \iff \nu_p(T') &\ge \nu_p(cT). \end{align*}$ This completes the proof. $\blacksquare$

Hence, the relevant fantastic triples are $(cT,c,M)$ for each $c \le 2017$ relatively prime to $10$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anantmudgal09

1979 posts

anantmudgal09

#6 h Jul 16, 2018, 11:43 AM • 3 Y

Y by RedFlame2112, Adventure10, Mango247

Tsukuyomi wrote:

Call a rational number short if it has finitely many digits in its decimal expansion. For a positive integer $m$ , we say that a positive integer $t$ is $m-$ tastic if there exists a number $c\in \{1,2,3,\ldots ,2017\}$ such that $\dfrac{10^t-1}{c\cdot m}$ is short, and such that $\dfrac{10^k-1}{c\cdot m}$ is not short for any $1\le k<t$ . Let $S(m)$ be the the set of $m-$ tastic numbers. Consider $S(m)$ for $m=1,2,\ldots{}.$ What is the maximum number of elements in $S(m)$ ?

Answer. $807$ .

Note that $x \in \mathbb{Q}$ is short if for all primes $p \nmid 10$ we have $v_p(x) \ge 0$ . Now we show $\max_{m \in \mathbb{N}} |S(m)| \le 807$ . Let $X \overset{\text{def}}{:=} \{ 1 \le c \le 2017 | \gcd(c,10)=1\}$ then we have $|X|=807$ .

Suppose $|S(m)| \ge 808$ for some $m \in \mathbb{N}$ . To each $t$ that is $m$ -tastic, assign the maximum divisor of the corresponding $c$ that is coprime to $10$ . Note that this assignment is a function from $S(m)$ to $X$ ; so it cannot be injective. However if $t_1<t_2$ are both assigned the same $c \in X$ then $\frac{10^k-1}{c \cdot m}$ is not short for all $k<t_2$ and $\frac{10^{t_1}-1}{c\cdot m}$ is short; contradiction!

Now we prove equality can be obtained. Let $M=\phi\left(\prod_{x \in X} x\right)$ and $m=10^{M}-1$ . Then $c \in X \implies c \mid m$ . Now we pick any $p \nmid 10$ prime; let $d$ be the order of $10$ mod $cm$ . Then $m \mid 10^d-1 \implies M \mid d$ so let $d=Mj$ with $j$ minimal. Now $c \cdot m \mid 10^{Mj}-1 \iff v_p(c)+v_p(m) \le v_p(10^{M}-1)+v_p(j)$ for all primes $p \nmid 10$ ; so $v_p(c) \le v_p(j) \implies c \mid j$ . Thus, $d=Mc$ as $j$ is minimal. Now for all $t \in \{Mx | x \in X\}$ we conclude that there is some $c \in X$ such that $\frac{10^{t}-1}{cm}$ is short but for any $k<t$ the number $\frac{10^k-1}{cm}$ isn't; proving the equality.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#7 h Aug 23, 2018, 7:33 AM • 3 Y

Y by RedFlame2112, Adventure10, Mango247

WOW this problem is amazing! Idk why I like it so much but I do

Anyways, here it is in all its glory.

First, note that the problem is a little contrived in its wording, as it is clear that $\frac{a}{b}$ is short if and only if $\frac{a}{\frac{b}{2^{\nu_2(b)}5^{\nu_5(b)}}}$ is short. The point is, $S(m)=S\left(\frac{m}{2^{\nu_2(m)}5^{\nu_5(m)}}\right)$ , and we can restrict our attention to $c\in[2017]$ such that $\gcd(c,10)=1$ . Let $S$ be the set of such $c$ , and its easy to see that $|S|=807$ .

Now, WLOG we have $\gcd(m,10)=1$ and $\gcd(c,10)=1$ . Then, $\frac{10^r-1}{cm}$ is short if and only if $cm\mid 10^r-1$ . Therefore, the statement of the problem is saying that $t=\mathrm{ord}_{cm}(10)$ . Thus,
$S(m) = \{\mathrm{ord}_{cm}(10):c\in S\}.$ Thus, we have $|S(m)|\le|S|=807$ , and we show that equality is in fact achieved, making the answer $\boxed{807}$ .

Here are the key lemmas.

Lemma 1: Suppose $\gcd(a,b)=\gcd(a,10)=\gcd(b,10)=1$ . Then, $\mathrm{ord}_{ab}(10)=\mathrm{lcm}(\mathrm{ord}_a(10),\mathrm{ord}_b(10))$ .

Proof of Lemma 1: Let $t_1=\mathrm{ord}_a(10)$ , $t_2=\mathrm{ord}_b(10)$ , and $t=\mathrm{ord}_{ab}(10)$ . We see that $10^t\equiv 1\pmod{ab}$ , so $10^t\equiv 1\pmod{a}$ and $10^t\equiv 1\pmod{b}$ , so $t_1,t_2\mid t$ . Also, if $t_1,t_2\mid t$ , then $10^t\equiv 1\pmod{a}$ and $10^t\equiv 1\pmod{b}$ , so by CRT, $10^t\equiv 1\pmod{ab}$ . Therefore, we have that $ab\mid 10^t-1$ if and only if $\mathrm{lcm}(t_1,t_2)\mid t$ , so the minimum such $t$ is $\mathrm{lcm}(t_1,t_2)$ , as desired. $\blacksquare$

Lemma 2: Let $p$ be a prime and let $w=\mathrm{ord}_p(10)$ . Then,
$\mathrm{ord}_{p^\ell}(10)=w\cdot p^{\max\{0,\ell-\nu_p(10^w-1)\}}.$ In particular, there exists a constants $f(p)\in\mathbb{Q}$ and $g(p)$ (read: don't depend on $\ell$ ) such that $\mathrm{ord}_{p^\ell}(10)=f(p)p^\ell$ for all $\ell\ge g(p)$ .

Proof of Lemma 2: Suppose $t=\mathrm{ord}_{p^\ell}(10)$ . Then, we see that $10^t\equiv 1\pmod{p}$ , so $w\mid t$ . Therefore, by LTE,
$\nu_p(10^t-1) = \nu_p((10^w)^{t/w}-1) = \nu_p(10^w-1)+\nu_p(t/w).$ Thus,
$p^\ell\mid 10^t-1\iff\nu_p(t/w)+\nu_p(10^w-1)\ge \ell,$ so the minimum $t$ that works is $w\cdot p^{\max\{0,\ell-\nu_p(10^w-1)\}}$ , as desired. $\blacksquare$

Now, pick $m=\prod_{\substack{p\text{ prime}\\ p\le 2017}}p^{g(p)}$ . Suppose $c=p_1^{e_1}\cdots p_k^{e_k}$ where $p_1,\ldots,p_k$ are all the primes that are at most $2017$ . Then,
$cm=\prod_{i=1}^k p_i^{g(p_i)+e_i},$ so by Lemmas 1 and 2, we have that
$\mathrm{ord}_{cm}(10) = \mathrm{lcm}\left(h(p_i)p_i^{e_i}\right)_{i=1}^k$ where $h(p_i)=f(p_i)p_i^{g(p_i)}$ , and note that $h(p_i)\in\mathbb{Z}$ (actually I think that $h(p_i)=w=\mathrm{ord}_{p_i}(10)$ though I'm not sure). The point then is that there is a constant $A$ such that
$\mathrm{ord}_{cm}=Ac,$ so each $c\in S$ produces a different values of $t$ , so then $S(m)=S$ as desired. Therefore the maximum size of $S(m)$ is $|S|=\boxed{807}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IndoMathXdZ

691 posts

IndoMathXdZ

#8 h Nov 1, 2019, 2:00 PM • 2 Y

Y by RedFlame2112, Adventure10

Thought this was ugly but this is a really nice Number Theory problem!

The answer is $\textbf{807}$ .
Firstly, notice that we could let $(c,10) = (m,10) = 1$ as it won't affect the short-ness of a fraction. Therefore, we define a number short if and only if for every prime $p \not= 2, 5$ , we have
$\nu_p \left( \frac{10^t - 1}{cm} \right) \ge 0$ and therefore, we could redefine $S(m)$ as:
$S(m) = \{ \text{ord}_{10} (cm) | c \le 2017 , \ (c,10) = 1, \ (m,10) = 1 \}$ We will now set the obvious upper bound, which is
$S(m) \le 2017 - \left \lfloor \frac{2017}{2} \right \rfloor - \left \lfloor \frac{2017}{5} \right \rfloor + \left \lfloor \frac{2017}{10} \right \rfloor = \textbf{807}$ We will now show it is attainable by constructing a value $m$ such that for all values $(c,10) = 1$ and $c \le 2017$ , we have $ord_{10} (cm)$ being distinct.
We'll start off by a few lemmas.
$\textbf{Lemma 01.}$ For relatively prime positive integers $a$ and $b$ , we have
$\text{ord}_{10} (ab) = \text{lcm} \{ \text{ord}_{10} (a) , \text{ord}_{10} (b) \}$ $\textit{Proof.}$ Notice that
$a | ab | 10^{\text{ord}_{10} (ab)} - 1$ Therefore, $\text{ord}_{10} (a) | \text{ord}_{10} (ab)$ . Similarly, $\text{ord}_{10} (b) | \text{ord}_{10} (ab)$ . We are then done by the definition of order.

$\textbf{Lemma 02.}$ Let $v_p (10^{\text{ord}_{10} (p)} - 1 ) = m$ . Therefore, for all values $k \ge m$ , we have
$v_p (10^{\text{ord}_{10} (p^k)} - 1) = k$ $\textit{Proof.}$ We'll prove that $\text{ord}_{10} (p^k) = p^{k - m} \cdot \text{ord}_{10} (p^m)$ .
We know that by Lifting The Exponent Lemma,
$p^{k + 1} | 10^{\text{ord}_{10} (p^m )\cdot p^{k - m}} - 1$ Suppose for some $k \ge m$ , we have $\text{ord}_{10} (p^k) = p^{\alpha} \cdot x$ , where $x \not= \text{ord}_{10} (p^m)$ and not divisible by $\text{ord}_{10} (p^m)$ , then we have
$p^m | 10^{\gcd(p^{k-m} \cdot \text{ord}_{10} (p^m), p^{\alpha} \cdot x)} - 1$ Then it must be divisible by $\text{ord}_{10} (p^m)$ . Moreover, by the definition of order and lifting the exponent lemma, we have $\text{ord}_{10} (p^k) = p^{k - m} \cdot \text{ord}_{10} (p^m)$ . This contradicts the definition of order.

Let $\mathbb{P}$ be set of all primes less than or equal to $2017$ . Now, we consider taking $m = \prod_{p \in \mathbb{P}} p^K$ with $K$ being arbitrarily large.
Define $m_p = v_p (10^{ord_{10} (p) } - 1)$ .
This gives us
$\begin{align*} \text{ord}_{10} (cm) &= \text{lcm}_{p \le 2017} \ \text{ord}_{10} \left( p^{K + v_p(c)} \right) \\ &= \text{lcm}_{p \le 2017} \ p^{K - m_p + v_p(c)} \cdot \text{ord}_{10} \left( p^{m_p} \right) \\ \end{align*}$ Since $m_p$ is fixed for every prime $p$ , therefore we could choose $K$ such that
$K \ge v_p \left( \text{ord}_{10} (p^{m_p}) \right)$ By choosing such value of $K$ , we can have
$\text{lcm}_{p \le 2017} \ p^{K - m_p + v_p(c)} \cdot \text{ord}_{10} \left( p^{m_p} \right) = \prod_{p \le 2017} p^{K - m_p + v_p(c)} = c \cdot \prod_{p \le 2017} p^{K - m_p}$ Therefore, for every $c$ , we can ensure that $\text{ord}_{10} (cm)$ are all distinct for $c \le 2017$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Stormersyle

2785 posts

Stormersyle

#9 h Mar 27, 2020, 2:38 PM • 1 Y

Y by RedFlame2112

We claim the answer is $807$ . First note that $x$ is short iff for all $p\ne 2, 5$ , $\nu_p(x)\ge 0$ . Next, note that powers of of 2 and 5 dividing $c$ or $m$ have no impact on whether $\frac{10^i-1}{cm}$ is short and thus are pretty much irrelevant, so we can WLOG let $c, m$ not be divisible by 2 or 5. Thus, $(t, c, m)$ is fantastic iff $ord_{cm} 10=t$ , so $S(m)$ is the number of distinct values $ord_{cm}10$ can take on as $c$ runs through all the integers in $[1, 2017]$ which are prime to 10. By PIE there are $807$ such integers, so thus we have the bound $S(m)\le 807$ .

Now, for the construction, let $m=10^T-1$ , such that $m$ is divisible by all the primes $\le 2017$ except for $2, 5$ . We claim that for all $c$ , $ord_{c(10^T-1)}10=cT$ , which would immediately imply that the construction works. To prove this claim, let $d=ord_{c(10^T-1)}10$ ; then, we first need $10^T-1|10^d-1$ , so $T|d$ , so let $d=zT$ . We are trying to minimize $z$ . Now, for $z$ to work, note that the following is necessary and sufficient: for all $p|c$ , $\nu_p(10^{zT}-1)\ge \nu_p(c(10^T-1))$ . But since $p|10^T-1$ , by LTE this inequality becomes $\nu_p(10^T-1)+\nu_p(z)\ge \nu_p(c)+\nu_p(10^T-1)\iff \nu_p(z)\ge \nu_p(c)$ , and hence the minimum value of $z$ is $c$ , which also works. Thus, $d=cT$ , and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_pi_rate

1218 posts

math_pi_rate

#10 h May 12, 2020, 8:10 PM • 3 Y

Y by amar_04, MatBoy-123, RedFlame2112

Great problem! Here's my solution: Call such a $c$ to be a friend of an $m$ -tastic number. Note that for each $c \in [2017]$ , it is the friend of at most $1$ $m$ -tastic integer. Also, if $c$ has $t$ as its friend, then $\frac{c}{2^x5^y}$ also has $t$ as its friend, where $x=\nu_2(c)$ and $y=\nu_2(5)$ . So WLOG take $\gcd(c,10)=1$ . Similarly, we can assume $\gcd(m,10)=1$ . In particular, this means that $\frac{10^t-1}{cm}$ is short iff $cm \mid 10^t-1$ , or in other words, $t=\text{ord}_{cm}(10)$ . Now, as $c \leq 2017$ with $\gcd(c,10)=1$ for any element of $S(m)$ , so using Principal of Inclusion-Exclusion, we have $|S(m)| \leq 2017-1008-403+201=807$ We claim that $807$ is achievable. Let $e=\text{ord}_m(10)$ , and for each $c \leq 2017$ with $\gcd(c,10)=1$ , let $em_c=\text{ord}_{cm}(10)$ . It suffices to show that all such $m_c$ 's are distinct for a suitable $m$ . Let $m=10^e-1$ for $e=\text{lcm}(\text{ord}_p(10))$ where $p$ is a prime less than $2018$ with $\gcd(p,10)=1$ . Then, for all such primes $p$ , we have $p \mid 10^e-1$ . So LTE gives $\nu_p(m)+\nu_p(c)\leq \nu_p(10^{em_c}-1)=\nu_p(10^e-1)+\nu_p(m_c)=\nu_p(m)+\nu_p(m_c) \Rightarrow \nu_p(m_c) \geq \nu_p(c)$ Since this is true for all prime divisors of $c$ , and $m_c$ is the smallest such number, so we must have $m_c=c$ . Thus, all $m_c$ 's are distinct, as desired, giving the required answer as $807$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#11 h Jun 13, 2020, 6:30 AM • 1 Y

Y by RedFlame2112

Solved with william122.

The condition tells us that $t$ is the order of 10 mod $cm$ . So $t$ is a unique function of $c$ , assuming we fix $m$ . If $\gcd(c,10)>1$ , then the order is not well-defined, so $t$ is not $m$ -tastic. Therefore, there are at most $2017-\lfloor \tfrac{2017}{2} \rfloor-\lfloor \tfrac{2017}{5} \rfloor+\lfloor \tfrac{2017}{10} \rfloor=807$ elements of $S(m)$ . We can achieve this bound if we can do the following.

New Problem wrote:

We want to find an $m$ such that the order of 10 mod $cm$ is different for each $c\le 2017$ coprime of 10.

Let $\mathrm{ord}_{10}(x)$ be the order of 10 mod $x$ . Suppose $a,b\le 2017$ both coprime to 10, such that $\mathrm{ord}_{10}(a)=\mathrm{ord}_{10}(b)$ . We want to pick an $m$ such that $\mathrm{ord}_{10}(am) > \mathrm{ord}_{10}(bm)$ .

Lemma: If $x,y$ are coprime numbers, then $\mathrm{ord}_{10}(xy) = \text{lcm} \{ \mathrm{ord}_{10}(x), \mathrm{ord}_{10}(y) \}$ .
Proof: Trivial by CRT. $\blacksquare$

Claim: $\mathrm{ord}_{10}(p^{\ell+1}) = p\cdot \mathrm{ord}_{10}(p^{\ell})$ for all $\ell \ge L$ for some constant $L$ .
Proof: We induct on $\ell$ to show that $v_p(10^{\mathrm{ord}_{10}(p^\ell)}-1) = \ell$ for $\ell \ge L$ for some $L$ . We will show how this implies the desired result.

Base case: The following is quite tricky. We claim $L=v_p(10^{\mathrm{ord}_{10}(p)}-1)$ works. Then $p^L = 10^{\mathrm{ord}_{10}(p)}-1$ . Let $k=\mathrm{ord}_{10}(p^L)$ , then $k$ is the minimal number such that $10^k \equiv 1 \pmod{p^L}$ . But by construction, this is simply $k=\mathrm{ord}_{10}(p)$ . Now, $\mathrm{ord}_{10}(p^{L+1})$ cannot be $k$ , since we would then have $10^k \equiv 1 \pmod{p^{L+1}}$ , which would imply $L = v_p(10^{\mathrm{ord}_{10}(p)}-1)+1$ . This proves the base case.
Inductive step: We know $\mathrm{ord}_{10}(p^{\ell}) \mid \mathrm{ord}_{10}(p^{\ell+1})$ , so let $\mathrm{ord}_{10}(p^{\ell+1}) = p' \cdot \mathrm{ord}_{10}(p^{\ell})$ . Therefore, $p'$ is the minimal number such that $10^{\mathrm{ord}_{10}(p^\ell) \cdot p'} \equiv 1 \pmod{p^{\ell+1}}.$ By LTE, $v_p(10^{\mathrm{ord}_{10}(p^\ell) \cdot p'}-1) = v_p(10^{\mathrm{ord}_{10}(p^\ell)}-1) + v_p(p') \ge \ell+1.$ We know $v_p(10^{\mathrm{ord}_{10}(p^\ell)}-1) = \ell$ by induction, so $v_p(p') \ge 1$ . Since $p'$ is minimal, we have $p'=p$ . Now, the inductive step follows, and we have shown that $\mathrm{ord}_{10}(p^{\ell+1}) = p \cdot \mathrm{ord}_{10}(p^{\ell})$ , as desired.

This proves the claim. $\blacksquare$

In particular, the claim tells us that $v_p(\mathrm{ord}_{10}(p^{\ell})) = \ell + C$ for some constant $C$ for large enough $\ell$ .

Suppose $\mathrm{ord}_{10}(a) = \mathrm{ord}_{10}(b)$ for some $a,b$ . Let $v_p(a)=e$ . Choose a prime $p$ with $v_p(a) > v_p(b)$ , and multiply $a$ and $b$ by $m=p^N$ for a sufficiently large $N$ . Let $a=p_1^{e_1}\cdots p_f^{e_f} p^e$ be the prime factorization of $a$ . Now, $\begin{align*} \mathrm{ord}_{10}(am) &= \mathrm{ord}_{10}(ap^N) = \mathrm{ord}_{10}(p_1^{e_1} \cdots p_f^{e_f} p^{e+N}) \\ &= \text{lcm} \{ \mathrm{ord}_{10}(p_1^{e_1}),\ldots, \mathrm{ord}_{10}(p_f^{e_f}), \mathrm{ord}_{10}(p^{e+N})\} \\ \implies v_p(\mathrm{ord}_{10}(am)) &= \max \{ v_p(\mathrm{ord}_{10}(p_1^{e_1})),\ldots, v_p(\mathrm{ord}_{10}(p_f^{e_f})), \ \ v_p(\mathrm{ord}_{10}\left(p^{e+N})\right)\}. \end{align*}$ All the terms above except the last are fixed. Hence, making $N$ sufficiently large makes the $p$ -term dominate, and we get $\begin{align*} v_p(\mathrm{ord}_{10}(am)) &= v_p(\mathrm{ord}_{10}(p^{e+N})) = e+N+C = v_p(a) + N + C \\ &> v_p(b) + N + C = v_p(\mathrm{ord}_{10}(p^{e+N}))= v_p(\mathrm{ord}_{10}(bm)). \end{align*}$ Therefore, $v_p(\mathrm{ord}_{10}(am)) > v_p(\mathrm{ord}_{10}(bm))$ . And multiplying by $m$ again and again will not change this fact; clearly multiplying by coprime numbers won't, and multiplying by more multiples of $p$ won't either, since we took sufficiently large powers of $p$ as $m$ anyways. Now, iterate this over all primes $p\le 2017$ (this utilizes the bounded part!), to get $\mathrm{ord}_{10}(am) > \mathrm{ord}_{10}(bm)$ . Continue this process for all equal pairs $(a,b)$ , and eventually we will get all distinct orders.

Remarks

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jj_ca888

2726 posts

jj_ca888

#12 h Sep 6, 2020, 2:20 AM • 1 Y

Y by RedFlame2112

Note that if a rational number has a repeating block then it is not short. Hence, all short rational numbers in lowest terms have denominators of the form $2^a5^b$ where $a, b$ are nonnegative integers. In other words, $v_p(r)$ for a short rational $r$ is nonnegative. Furthermore, it is clear that powers of $2$ or $5$ do not affect shortness so assume WLOG that $\gcd(c, 10) = \gcd(m, 10) = 1$ .

Next we clear up a bit of notation. The set $S(m)$ is just the set of all positive integers $t$ for which there exists $c \leq 2017$ so that $t$ is the order of $10$ modulo $cm$ , or in other words, the set of distinct values $\text{ord}_{cm}(10)$ can take as $c$ runs through numbers relatively prime to $10$ from $1 \to 2017$ . We see that by PIE, $c$ runs through at most $2017 - \left\lfloor\frac{2017}{2}\right\rfloor - \left\lfloor\frac{2017}{5}\right\rfloor + \left\lfloor\frac{2017}{10}\right\rfloor = 807$ distinct values. We now prove that it is possible to achieve this bound. Consider $M = 10^n - 1$ for some large composite number $n = \prod (p - 1)$ over all primes $\leq 2017$ that are not $2$ or $5$ . By size the order of $10$ modulo $cM$ is clearly $n$ . The key claim is that for each $c \leq 2017$ relatively prime to $10$ that the order of $10$ modulo $M$ is $cn$ .

We will do this with LTE. First of all note that $p \mid 10^n - 1$ for all primes $p \leq 2017$ not $2$ or $5$ . By our definition of $M$ , the primeset of $M$ and $cM$ is the same so it is necessary that $n \mid \text{ord}_{cM} 10$ . Next we take a prime $q \mid c$ . If $kn$ is the desired order, then by LTE, $\begin{align*} v_q(c) + v_q(M) &\leq v_q(10^{kn} - 1)\\& = v_q(10^n - 1) + v_p(k) \end{align*}$ and since by definition $M = 10^n - 1$ we get $v_q(c) \leq v_p(k)$ hence the order is $cn$ as desired. $\square$

Lastly, we do see that each $c \leq 2017$ relatively prime to $10$ provides a distinct order, and thus our answer of $\boxed{807}$ is indeed achievable. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aryan-23

558 posts

Aryan-23

#13 h Oct 22, 2020, 7:27 AM • 1 Y

Y by RedFlame2112

We claim that the answer is $807$ .

We can obviously assume $(m,10)=1$ .
Call $c$ to be a parent of $t$ . First note that if $c$ is a $t$ -parent, so is $\tfrac {c}{2^{\nu_2(c)}5^{\nu_5(c)}}$ , so we can WLOG assume that $(c,10)=1$ . Hence, after removing all multiples of $2$ or $5$ from $\{1,2,\dots,2017\}$ , we get $\vert S(m) \vert \leq 807$ .

We know construct a $m$ such that $807$ is attainable.

Motivation

Choose $m=10^x-1$ , such that $m$ is divisible by all primes $\leq 2017$ (excluding $2,5$ ). We claim that the order of $10\pmod (cm)$ is just $cx$ . This obviously finishes. Firstly note that $x \mid \operatorname {ord}_{cm}10$ , so suppose the order is $xy$ . We prove that $v_p(y) =v_p(c)$ for all primes $p\mid c$ , which finishes.

We have :
$v_p(c)+v_p(10^x-1) \leq v_p(10^{xy}-1) = v_p(10^x-1) + v_p(y) \implies v_p(y) \ge v_p(c)$
In the above step we only used the fact that $p\mid 10^{xy}-1$ . Hence when $xy$ is order, equality must hold in the above expression so $y=c$ . Done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5000 posts

IAmTheHazard

#14 h Jun 27, 2021, 7:30 PM • 2 Y

Y by centslordm, RedFlame2112

The largest possible value of $|S(m)|$ is $807$ . Powers of 2 and 5 dividing $cm$ don't change the shortness of $\tfrac{10^k-1}{cm}$ , so we only need to consider $\gcd(cm,10)=1$ . It is then clear that for a fixed $m$ , the value of $t$ is determined by the choice of $c$ . Since there are
$2017-\left\lfloor\frac{2017}{2}\right\rfloor-\left\lfloor\frac{2017}{5}\right\rfloor+\left\lfloor\frac{2017}{10}\right\rfloor=807$ choices of $c$ with $\gcd(c,10)=1$ , it follows that $|S(m)|\leq 807$ . It remains to show that $|S(m)|=807$ is achievable. Let $P$ be the set of primes at most $2017$ which are not equal to $2$ or $5$ . Next, define $f(p)=\nu_p(10^{\operatorname{ord}_p(10)}-1)$ for primes $p \neq 2,5$ and let
$X=\operatorname{max}\{f(p)\}_{p \in P},$ and consider $m=\left(\prod_{p \in P}p\right)^X$ . I claim that this works. Note that $\tfrac{10^k-1}{cm}$ is short if and only if $\nu_p(cm) \leq \nu_p(10^k-1)$ for all $p \in P$ . Let $q$ be a prime in $P$ , which must divide $m$ and therefore $cm$ . Then if $\tfrac{10^k-1}{cm}$ is short, we clearly must have $\operatorname{ord}_q(10) \mid k$ , otherwise $q \nmid 10^k-1$ . Then, from Lifting the Exponent:
$\nu_q(10^k-1)=\nu_q((10^{\operatorname{ord}_q(10)})^{k/\operatorname{ord}_q(10)}-1)=\nu_q(10^{\operatorname{ord}_q(10)}-1)+\nu_q\left(\frac{k}{\operatorname{ord}_q(10)}\right)=\nu_q(10^{\operatorname{ord}_q(10)}-1)+\nu_q(k),$ where the last equality comes from the fact that $\operatorname{ord}_q(10)<q$ , so $\nu_q(\operatorname{ord}_q(10))=0$ . It follows that it is necessary and sufficient to have
$\nu_q(k) \geq \nu_q(c)+\nu_q(m)-\nu_q(10^{\operatorname{ord}_q(10)}-1).$ Observe that the RHS is always positive by our definition of $m$ , hence the least possible value of $k$ occurs when equality holds everywhere. Now note that for values of $c$ whose prime factorization differs for primes other than $2,5$ , the resulting minimal values of $k$ will be different. Thus, for this choice of $m$ , all $807$ values of $c$ with $\gcd(c,10)=1$ give a unique value of $t$ , so there are $807$ $m$ -tastic numbers. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheUltimate123

1740 posts

TheUltimate123

#15 h Jul 15, 2021, 4:15 AM • 1 Y

Y by RedFlame2112

Solved with Elliott Liu and Raymond Feng.

The answer is 807.

Proof of upper bound: Let $f(x)$ denote the largest divisor of $x$ not divisible by 2 or 5. If $t$ is $m$ -tastic for a particular choice of $c$ , then $t=\operatorname{ord}(10\bmod f(cm))$ . In particular $\begin{align*} S(m)&=\{\operatorname{ord}(cm\bmod10)\mid 1\le c\le2017\}\\ &=\{\operatorname{ord}(cm\bmod10)\mid c=1,3,7,9,\ldots,2017\}, \end{align*}$ which has at most 807 distinct elements.

Proof of lower bound: It will suffice to find $m$ such that $\operatorname{ord}(cm\bmod10)$ are distinct over $c=1,3,7,9,\ldots,2017$ . Indeed, take $m=10^t-1\quad\text{such that}\quad p\mid m\;\forall p\le2017,\; p\ne2,5.$ It follows that $\operatorname{ord}(m\bmod10)=t$ , and moreover $\nu_p(10^{tk}-1)=t+\nu_p(k),$ implying for all $c=p_1^{e_1}\cdots p_k^{e_k}$ with $p_i\le2017$ and $p_i\ne2,5$ , we have $\operatorname{ord}(cm\bmod10)=p_1^{e_1}\cdots p_k^{e_k}\operatorname{ord}(m\bmod10)=c\operatorname{ord}(m\bmod10),$ which are all distinct.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#16 h Dec 5, 2021, 10:21 PM • 2 Y

Y by RedFlame2112, Lcz

The answer is $\boxed{807}$ .

Proof of Bound. Observe that for every pair $(m, c)$ , there exists exactly one unique $t$ satisfying the fantastic condition. Furthermore, if $(t, qc, m)$ is fantastic for some $t$ and $q = 2^{k_1} \cdot 5^{k_2},$ then $(t, c, m)$ is fantastic as well. Hence we can ignore all multiples of 2 and 5 because they give nonunique $t$ , for at most $2017 - \left \lfloor \frac{2017}2 \right \rfloor - \left \lfloor \frac{2017}5 \right \rfloor + \left \lfloor \frac{2017}{10} \right \rfloor = 807$ distinct $t$ .

Construction. Take $m$ to be the product of sufficiently large powers of all the primes less than or equal to 2017. First, note that the minimum $t = \text{ord}_{cm} 10,$ which is obvious by definition. Now, take some $c_1 \neq c_2$ . Then there must exist some prime $p$ such that $\nu_p(c_2) \neq \nu_p(c_1)$ .

Claim. For prime $p$ , we have $\nu_p\left(\text{ord}_{p^k}10\right)= k-\nu_p\left(10^{\text{ord}_p 10}-1\right).$ Proof. Set $r = \text{ord}_p(10)$ and $s$ such that $r \mid s$ . By the LTE lemma $\nu_p(10^s - 1) = \nu_p\left(\frac sr \right) + \nu_p(10^r-1),$ so the order of 10 mod $p^k$ for $k > \nu_p(10^r-1)$ is unique. Now set $s = \text{ord}_{p^k} 10$ , and rearrange to get $\nu_p\left(\frac sr\right) = \nu_p(10^s-1) - \nu_p(10^r-1) = k - \nu_p(10^r-1).$ Note that $\nu_p(r) = 0$ because $r<p$ , from where we obtain the desired conclusion. $\blacksquare$

In addition, obviously $\text{ord}_{ab} 10 = \text{lcm}(\text{ord}_a 10, \text{ord}_b 10)$ for $a, b$ relatively prime.

Back to the problem. Consider $\nu_p(\text{ord}_{cm} 10) = \nu_p(\text{ord}_{p^{\nu_p(cm)}} 10)$ for $\nu_p(m)$ sufficiently large. We can make this conversion because splitting $\text{ord}_{cm} 10$ into its LCM form, all the terms are of the form $q^k \text{ord}_q 10$ for a prime $q \leq 2017$ (because $cm$ contains no prime factors over 2017 by our construction). Because $\text{ord}_q 10 < 2017$ and $\nu_p(m)$ is sufficiently large, this term is unable to override the $\text{ord}_{p^{\nu_p(cm)}}$ term. By the claim, we can rewrite $\nu_p(\text{ord}_{p^{\nu_p(cm)}} 10) = \nu_p(c) + \nu_p(m) - \nu_p(10^{\text{ord}_p 10} - 1).$ Replacing $c$ with $c_1$ and $c_2$ respectively, the $\nu_p$ of the two orders are distinct, and thus the two orders must be distinct. Across all possible $c_1, c_2$ , this finishes the proof. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Inconsistent

1455 posts

Inconsistent

#17 h Mar 28, 2022, 4:22 AM

Y by

How many points off for forgetting to WLOG out $\gcd(m, 10) \neq 1$ cases?

Sentence: Death by LTE.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mogmog8

1080 posts

Mogmog8

#18 h Sep 4, 2022, 8:08 PM • 2 Y

Y by centslordm, Mango247

Solved with a LOT of hints

WLOG let $\gcd(m,10)=1.$ For any $n\in\mathbb{N},$ let $n'=\frac{n}{2^{\nu_2(n)}\cdot 5^{\nu_5(n)}}.$ For any $c,$ notice $t=\operatorname{ord}_{c'm}10$ so the number of $t$ for any fixed $m$ is at most the number of $c',$ which is $2017-\left\lfloor\frac{2017}{2}\right\rfloor-\left\lfloor\frac{2017}{5}\right\rfloor+\left\lfloor\frac{2017}{10}\right\rfloor=807.$ We claim $807$ is achievable, letting $m=10^T-1$ where we choose $T$ such that $p\mid m$ for all primes $p\le 2017.$ This can be done by having $p-1\mid T$ for all such primes. Notice $T\mid\operatorname{ord}_{c'm}10$ as $T=\operatorname{ord}_m 10.$ Hence, let $\operatorname{ord}_{c'm}10=\ell T.$ By LTE, $\nu_p(c'm)\le\nu_p(10^{\ell T}-1)=\nu_p(10^T-1)+\nu_p(\ell),$ where $p\le 2017$ is a prime. Therefore, $\nu_p(c')\le\nu_p(\ell)$ so $c'\mid\ell.$ Since we are looking for the minimal $\ell,$ we see $\ell=c'$ and $\operatorname{ord}_{c'm}10=c'T.$ This means $t$ is distinct for all distinct $c',$ so there are $807$ values for $t.$ $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

akasht

83 posts

akasht

#19 h Dec 20, 2022, 5:42 AM • 2 Y

Y by Mango247, Mango247

The answer is $807$ .

Bound: Let $f(m)$ be the largest divisor of $m$ which is not divisible by $2$ or $5$ . A rational number is short if its denominator $d$ satisfies $f(d)=1$ . Thus, notice that if $f(c_1)=f(c_2)$ , then the $m$ -tastic number given by $c=c_1$ and $c=c_2$ will be the same. Hence $|S(m)|$ is at most the number of values of $f$ from $1$ to $2017$ , which is precisely the number of integers from $1$ to $2017$ that are not divisible by $2$ or $5$ . Using PIE, we get that this number is $2017 - \left \lfloor \frac{2017}2 \right \rfloor - \left \lfloor \frac{2017}5 \right \rfloor + \left \lfloor \frac{2017}{10} \right \rfloor =807$
Construction: Let $P$ be a large number such that all primes (except $2,5$ ) $\le 2017$ divide $10^P-1$ . Write $P=Mk$ , where $k$ is some integer which is coprime to $2017!$ , and $M|2017!$ . I claim $S(M)=807$ . Consider a value of $c$ with $\gcd(c,10)=1$ (there are $807$ of these from earlier)I

Claim: The order of $10$ modulo $cM$ is $cP$ (which implies $cP$ is $m$ -tastic)

Proof: Clearly the order of $10$ modulo $cM$ is divisible by $P$ , say it is $aP$ for some integer $a$ . By LTE, for any prime $p \le 2017$ , $v_p(10^{aP}-1) = v_p(10^P-1)+v_p(a)=v_p(M)+v_p(a) \implies v_p(a)=v_p(c)$ which implies $a=c$ .

Hence, for each $c$ with $\gcd(c,10)=1$ , $cP$ is $m$ -tastic, which leads to $S(M)=807$ as desired.

This post has been edited 1 time. Last edited by akasht, Dec 20, 2022, 5:52 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cj13609517288

1878 posts

cj13609517288

#20 h Feb 21, 2023, 2:33 PM

Y by

The answer is $\boxed{807}$ . Clearly there exists exactly one fantastic $t$ for any $cm$ .

Construction: First define $f(p)=10^{\text{ord}_p(10)}-1$ . Then I claim that
$m=\prod_{p\text{ prime},\,p\le 2017,\,p\notin\{2,5\}}p^{\nu_p\left(f(p)\right)}$ works. In fact, $\text{ord}_{cm}(10)=\text{ord}_m(10)\cdot c$ for all positive integers $c\le 2017$ where $\gcd(c,10)=1$ due to a direct application of LTE.

Proof of maximality: Simply note that multiplying $c$ by a number of the form $2^a 5^b$ does not change the fantastic $t$ . So the answer has to be at most the number of positive integers $c\le 2017$ such that $2\nmid c$ and $5\nmid c$ , which is just
$\phi(10)\cdot\left\lfloor\frac{2017}{10}\right\rfloor+3=807.$

This post has been edited 3 times. Last edited by cj13609517288, Feb 21, 2023, 2:36 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VicKmath7

1386 posts

VicKmath7

#21 h May 26, 2023, 2:13 PM

Y by

Solution

This post has been edited 2 times. Last edited by VicKmath7, May 27, 2023, 9:52 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

trying_to_solve_br

191 posts

trying_to_solve_br

#22 h Jun 23, 2023, 10:34 PM

Y by

Solution with the walkthrough

This is a weird problem since I didn't know what to expect from it. Firstly, I thought "why can't $S(m)$ be infinite?", then I saw it was trivial: The numbers on the set $S$ is disjoint on $c$ 's, that is, if $x,y \in S(m)$ had the same $c$ with $x>y$ , then $y=k$ on the statement of the problem would lead to a contradiction. Also, I noticed fastly that if $c$ had a 2 or 5 factor wouldn't matter. If for some $t$ his $c$ was a multiple of 2,5, we could take those factors away and just work with the $c$ we had.

Hence, I knew that there were at most $807$ numbers on $S(m)$ for all $m$ , since this is the numbers of integers coprime to 10 from 1 to 2017.

Now, let's solve the hard part: the construction!

Notice that we want, for each $c$ on the mentioned set, a number $t$ for which the number $\dfrac{10^t-1}{c\cdot m}$ is short; and since there are at most 807 $t$ 's, we want a bijection between each $t$ and $c$ . Now, let's construct our $m$ in a way that for all $p\neq 2,5$ , $v_p(c)+v_p(m) \leq v_p(10^t - 1)$ .

For each $c$ we will create a vector $(x_1,x_2,...,x_i)$ with $x_i=v_{p_i}(c)$ , with $x_i \ge 0$ and $p_i \leq 2017$ . The idea here is to make equality occur on the inequality above. To do this, we make $m=(p_1p_2...p_i)^W$ , where $W$ is a big integer. To generate our $t$ 's, we make $C=\{c_1,...,c_{807}\}$ the set of the coprime to 2,5 integers between 1 and 2017. I will show some $t_i$ exists, and that for each $c$ they are all different.

I will try to construct formally, but the idea is to use LTE on $ord_p 10=o$ and making $t=o.z$ , and controlling $v_p(10^o - 1)+v_p(z)$ .

Now, take $t_i=\prod_{\substack{p_j\text{ prime}\\ p_j\le 2017}}p_j^{v_j}.X$ . I will choose $v_j,X$ in such a way that as we vary $p_j$ by the primes, $W+x_j=v_{p_j}(10^{t_i}-1)$ .
Now, denote $o_j=ord_{p_j^W} 10 = p_j^{r_j}.d_j$ for some $d_j$ coprime to $p_j$ , $v_{p_j}(10^{o_j}-1)=l_j$ ; taking $X=\prod d_j/Y$ , $v_j=W+x_j-l_j+r_j$ , then by LTE we have:
$v_{p_j}(10^{t_i} -1)=v_p(10^{o_j} - 1)+v_p(t_i/o_j)=l_j+v_p(t_j)-v_p(o_j)=l_j+v_p(t_j)-r_j=W+x_j$ , as we wanted. Notice here the importance of having a big $W$ : $W>l_j$ for all $j$ is necessary for $v_j$ to be positive.

Now, notice this choice of $X,v_j$ might not generate the minimal $t_i$ for which this works. But the exponent of $v_p(10^t -1)$ must be at least what we generated. Hence the prime exponents can't change, because if they did, something would go wrong with the orders of 10.

To solve this issue, we just take $X$ to be the minimal integer such that this whole product is multiple of all the orders, with $X$ coprime to all $p's$ , that is, make $Y$ so that $X$ is coprime to $p_j$ and is still a multiple of all the orders.

Now, we've shown/created a construction that generates minimal $t's$ for each $c$ . But why does this choices of $t_i$ only work each for one $c$ ? Notice that, as we made equality true, for each $c$ there is at least one $x_j$ that is different from the other $c$ 's: that is, each vector is unique and as $r_j,X,l_j,W$ are all fixed, for each $c_i \in C$ a different $t_i$ is created, as at least one exponent of one the primes must be different, since all of them depend only on $x_j$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huashiliao2020

1292 posts

huashiliao2020

#23 h Sep 3, 2023, 6:05 AM

Y by

Literally this construction is so weird

The answer is 807. There's obviously exactly one t per c with fixed m, and since an extra factor of 2 or 5 does not influence the finiteness of 0s in the fraction, we see that the answer is at most the number of c relatively prime to 10; there are 807 of these such numbers.

For construction, choose $m=10^k-1$ , where $m=\prod_{\text{primes p}\le 2017}p$ (excluding $2,5$ ). We claim that the order of $10\pmod{cm}$ is $ck$ . Indeed, note that $k\mid \text{ord}_{cm}10=kx$ (since 10^{ord_{cm}10}-1 is divisible by m, so the order of 10 mod m which is k divides that); we'll prove that $\nu_p(x) =\nu_p(c)$ for all primes $p\mid c$ : $\nu_p(c)+\nu_p(10^k-1) \le \nu_p(10^{kx}-1) = \nu_p(10^k-1) + \nu_p(x) \implies \nu_p(x) \ge \nu_p(c).$ Since $p\mid 10^{kx}-1$ , for $kx$ to be the order, equality must hold; in particular, $x=c$ , as desired. $\blacksquare$

This post has been edited 6 times. Last edited by huashiliao2020, Sep 3, 2023, 4:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1683 posts

awesomeming327.

#24 h Dec 25, 2023, 4:17 PM

Y by

We change the definition of $m-$ tastic to suit our needs. Call a number $t$ $m-$ tastic if $\tfrac{10^t-1}{m}$ is short, and such that $\tfrac{10^k-1}{m}$ is not short for any $1\le k<t$ . Clearly, for any $m$ , there exists exactly one value of $t$ that works. Let this number be $f(m)$ . The value $|S(m)|$ becomes the number of distinct values in $\{f(m),f(2m),\dots,f(2017m)\}$ . Note that if a rational number $q$ is short, then $2^a5^bq$ is short for all integers $a$ , $b$ . Thus, $f(m)=f(2^a5^bm)$ for any $m$ coprime to $10$ and nonnegative integers $a$ and $b$ . Thus, if $x$ is not coprime to $10$ then there exists a positive integer $y<x$ such that $f(ym)=f(xm)$ , so $f(xm)$ is not a distinct value. Thus, the number of total distinct values is at most the number of positive integers coprime to $10$ , at most $2017$ , which is $807$ .

To prove that $807$ is achievable, we simply have to find a construction for which $f(cm)$ is distinct for all $c$ coprime to $10$ . Let $N$ be a number such that for all $p\le 2017$ and $\gcd(p,10)=1$ , $p\mid 10^N-1$ . Let $N'$ be the result if we divide out all primes not less than $2017$ from $10^N-1$ . Suppose $\gcd(c,10)=1$ then we claim that $f(cN')=cN$ .

Evidently, $cN'\mid 10^{f(cN')}-1$ , since if a rational number's denominator is coprime to $10$ and the rational number is short, then it is an integer. Note that $N\mid f(cN')$ . By LTE,
$\nu_p(10^{f(cN')}-1) = \nu_p(10^N-1)+\nu_p\left(\frac{f(cN')}{N}\right)=\nu_p(N')+\nu_p\left(\frac{f(cN')}{N}\right)$ for all primes $p\le 2017$ . This implies that $f(cN')=cN$ , so it is distinct.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4175 posts

john0512

#25 h Jan 2, 2024, 4:23 AM

Y by

For this entire solution, assume when a prime $p$ is mentioned, $p\neq 2$ and $p\neq 5$ .

The answer is $807$ . The problem is asking essentially asking for all values of $m$ , find the maximum possible number of distinct orders of 10 mod $cm$ for $c$ from 1 to $2017$ .

Factors of 2 and 5 are irrelevant, so we only needed to consider the $807$ values of $c$ that are relatively prime to 10. We claim that there exist $m$ such that the orders of $10$ mod $m$ , $3m$ , $7m$ , $9m$ , $11m$ , all the way to $2017m$ are all distinct.

Consider $m=2017!^n$ for sufficently large $n$ . For any given prime $p$ , eventually by LTE the order of 10 mod $p^k$ will just multiply by $p$ each time we increase the exponent. Due to this, if $m$ has sufficently many copies of each prime, for any given $p$ the prime $p$ itself will be the decider of the exponent of $p$ in the LCM of the orders of 10 mod each prime power, since adding factors of other primes will eventually stop increasing the $v_p$ of its order but adding factors of $p$ will keep increasing the $v_p$ of the order. This means, combined with the LTE fact, that the order of $cm$ is just $c$ times the order of $m$ , once this happens the multiplier to the order is the same as the multiplier to the modulus.

This post has been edited 1 time. Last edited by john0512, Jan 2, 2024, 4:24 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#26 h Feb 12, 2024, 8:27 PM

Y by

The answer is $\boxed{807}$ .

Notice that multiplying factors of $2$ or $5$ to $c$ does not change the fantastic $t$ , hence we can assume we are only working with numbers $c$ and $m$ relatively prime to $10$ .

Each $c$ can result in at most one $t$ . Then, it is clear that

$|S(m)| \le | \{ 1 \le c \le 2017 \mid \gcd(c, 10) = 1 \}| = 807.$
To show this bound, we make a claim.

Claim: Let $x$ be the smallest positive integer such that $n=10^x-1$ is divisible by every prime less than or equal to $2017$ . The order of $10$ modulo $cn$ is $cx$ .

Proof: Pick an arbitrary prime $p \mid c$ . If we let the order of $10$ modulo $cn$ be $x'$ , we must have $x \mid x'$ ; by LTE, compute that

$\begin{align*} \nu_p(cn) = \nu_p(c)+\nu_p(n) & \le \nu_p(10^{x'}-1) \\ & = \nu_p(10^{x \cdot (x'/x)}-1) \\ & = \nu_p(10^x-1)+ \nu_p \left(\frac{x'}{x} \right) \\ & = \nu_p(n)+\nu_p(x')-\nu_p(x). \end{align*}$
This implies that

$\nu_p(x') \ge \nu_p(cx),$
so we are done. $\square$

At this point, the triples $(cx,c,n)$ are the desired solution set.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

atdaotlohbh

171 posts

atdaotlohbh

#27 h Jun 14, 2024, 4:30 PM

Y by

We will use the following obvious lemma without proof:
Lemma: a positive rational number is short iff in the denominator of its irreducible fraction all prime factors are $2$ and $5$

Now note that we don't care about all twos and fives in $c$ , so let's delete all of them. Now we have $(c,10)=1$ and $c \leq 2017$ . There are exactly $2017-1008-403+201=807$ such numbers, that is our bound.
Now let $MS=\prod_{p \leq 2017, p \neq 2,5} p$ be product of almost all primes not exceeding $2017$ . Let $d=ord_{MS} (10)$ .
Let $X$ be a super big number.
We will construct $m$ as follows:
$m=MS^X$
Then by LTE we clearly must have $D=ord_{m} (10)=d\prod_{p \leq 2017, p \neq 2,5} p^{X-v_p(10^d-1)}$ and here $v_p(10^D-1)=v_p(m)$ for every prime $p \leq 2017, p\neq 2,5$
And now we just need to check that if we have $c_1 \neq c_2, (c_1,10)=1, (c_2,10)=1$ , then $ord_{c_1m} (10) \neq ord_{c_2m} (10)$
It is true because by LTE once again we must have $ord_{c_1m} (10)=Dc_1$ and $ord_{c_2m} (10)=Dc_2$ and this two numbers are different. Done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kotmhn

57 posts

kotmhn

#28 h Sep 13, 2024, 2:37 PM

Y by

Claim:
$2017 - \lfloor\frac{2017}{2}\rfloor - \lfloor \frac{2017}{5}\rfloor + \lfloor \frac{2017}{10}\rfloor = 807$ is the desired value.
Clearly this is the best as the $2,5$ exponents in the denominator do not matter.
Construction:
Let $S = \prod_{p \leq 2017}$
Let $M = 10^{T} -1$ where $T = \operatorname{ord}_{S}(10)$ . We are omitting all the $c$ divisible by $2,5$ as mentioned earlier, and henceforth
c obeys this condition
\begin{claim}
$\forall c$ the ord of 10 $\pmod{cM}$ is a just $cT$
\end{claim}
\begin{proof}
Let $t$ be the order of $10 \pmod{cM}$ then clearly $T\mid t$ and then taking a prime $p$ that divides $c$ we get
$\begin{align*} \nu_p(cM) &\leq \nu_p(10^t -1)\\&= \nu_p((10^{T})^{\frac{t}{T}} -1)\\&= \nu_p(10^T - 1) + \nu_p(t) - \nu_p(T)\\ &\iff \nu_p(t) \geq \nu_p(cT) \end{align*}$ And this show that the $\operatorname{ord}_{cM}(10) = cT$
\end{proof}
Hence we get $807$ distinct vals and are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5550 posts

megarnie

#29 h Jan 4, 2025, 1:46 PM

Y by

Solved a while ago but forgot to post

The answer is $\boxed{807}$ .

We can assume that $\gcd(c,10)$ is $1$ , because otherwise we get the same value of $t$ if we replace $c$ with $\frac{c}{c^{\nu_2(c)}\cdot c^{\nu_5(c)} }$ .

There are $201\cdot \phi(10) + 3 = 807$ values of $c\le 2017$ that are relatively prime to $10$ . Thus, $|S(m)|\le 807$ .

We now give a construction for $S(m) = 807$ .

Set $m = 10^k - 1$ , so that $\mathrm{lcm}(1,3,7,9,11,13,17,19,\ldots, 2013,2017)\mid m$
Notice that if $\frac{10^t - 1}{cm}$ is short, then it is an integer because $\gcd(cm,10) = 1$ . Thus $S(m)$ is the set of all $\mathrm{ord}_{cm}(10)$ as $c$ varies.

Claim: For $c\le 2017$ relatively prime to $10$ , $\mathrm{ord}_{cm}(10) = ck$ .
Proof: It's clear that this order must be a multiple of $k$ because $\mathrm{ord}_m{10} = k$ Now suppose the order is $a\cdot k$ . Then $cm\mid 10^{ak} - 1$ .

Now for any prime $p\le 2017$ , we have $\nu_p(cm) \le \nu_p(m) + \nu_p(a),$ by LTE, which implies $\nu_p(c) = \nu_p(a)$ . Since $c$ only has prime factors $\le 2017$ , we have $c\mid a$ . It remains to show that $cm\mid 10^{ck} - 1$

Again for any prime $p\le 2017$ , we have $\nu_p(cm) = \nu_p(10^{ck} - 1)$ . Note that $m = 10^k - 1\mid 10^{ck} - 1,$ so any prime factor greater than $2017$ dividing $cm$ also divides $10^{ck} - 1$ .

Let $q>2017$ be a prime number dividing $10^{ck} -1$ . We have $\nu_q(10^{ck} - 1) = \nu_q(m) + \nu_q(c) = \nu_q(cm),$ as desired. Thus for any prime $p\mid cm$ , we have $\nu_p(cm) = \nu_p(10^{ck} - 1)$ , so $cm\mid 10^{ck} - 1 \ \ \ \square$
Now we get $S(m)$ is the set of all $ck$ , for $c\le 2017$ relatively prime to $10$ , which implies $|S(m)| = 807$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kotmhn

57 posts

kotmhn

#30 h Mar 30, 2025, 12:06 PM

Y by

The answer is 807.

First obs that for any $c$ which is not coprime to $10$ the value of $t$ that satisfies is the same as the value of $t$ for $\frac{c}{2^{\nu_{2}(c)} \cdot 5^{\nu_2(c)}}$ .

So we can have at most
$2017-\left\lfloor\frac{2017}{2}\right\rfloor-\left\lfloor\frac{2017}{5}\right\rfloor+\left\lfloor\frac{2017}{10}\right\rfloor=807$ elements in $S$ .

Construction:
Let $t_i$ be the minimum value for each $i$ .
Let $s = \prod_{p\le 2017, (p,10) = 1} p$ and let $t_1 = ord_s(10)$ and take $m = 10^{t_1} -1$
Then we have
$\begin{align*} \nu_p(c) +\nu_p(m) &\le \nu_p(10^{t_c} -1) \\ &=\nu_p((10^{t_1})^{\frac{t_c}{t_1}} -1) \\ &=\nu_p(10^{t_1} -1) + \nu_p(\frac{t_c}{t_1}) \\ &\therefore \nu_p(c) \le \nu_p(\frac{t_c}{t_1}) \\ &\implies \nu_p(ct_1) \le \nu_p(t_c) \end{align*}$
This shows that all successive $t_c$ are larger (it is precisely $c\cdot t_1$ ) hence $|S| = 807$ , here the $LTE$ was possible as $t_1 \mid t_c$ due to orders, and $p \mid 10^{t_1} -1$ due to the construction.

Remark: this was motivated by the conditions $t_1 \mid t_c$ and that
$\begin{align*} & \nu_p(cm) \le \nu_p(10^{t_c} -1) \\ & \nu_p(m) \le \nu_p(10^{t_1} -1) \end{align*}$ So i wanted to use the divisibility and putting $t_c$ divisible by $t_1$ motivated $LTE$ , and finally the value of $m$ was taken to be $10^{t-1} -1$ for the cancellation in the ineq. Also the prod of prime idea was for the $LTE$ to work out.

Z K Y

N Quick Reply