Mmmmmm...Tasty!

The post below has been deleted. Click to close.

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

whatshisbucket

975 posts

whatshisbucket

#1 h Jun 26, 2017, 7:03 AM • 8 Y

Y by Davi-8191, naw.ngs, centslordm, megarnie, green_leaf, Adventure10, Mango247, Funcshun840

An integer $n>2$ is called tasty if for every ordered pair of positive integers $(a,b)$ with $a+b=n,$ at least one of $\frac{a}{b}$ and $\frac{b}{a}$ is a terminating decimal. Do there exist infinitely many tasty integers?

Proposed by Vincent Huang

Z K Y

The post below has been deleted. Click to close.

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

kk108

2649 posts

kk108

#2 h Jun 26, 2017, 7:24 AM • 4 Y

Y by megarnie, centslordm, Adventure10, Mango247

Well this is definitely tasty's tasty problem!

This post has been edited 1 time. Last edited by kk108, Jun 26, 2017, 7:25 AM

Z K Y

The post below has been deleted. Click to close.

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

babu2001

402 posts

babu2001

#3 h Jun 26, 2017, 7:45 AM • 14 Y

Y by shinichiman, kk108, Tugsuu, vjdjmathaddict, JasperL, tarzanjunior, Anar24, OlympiadIneqByBruteForce, centslordm, denistusk, skyguy88, qwedsazxc, Adventure10, Mango247

The answer is definitely a big $\text{NO}$ . Call a number "bitter" if and only if it is not "tasty".

$\text{Claim :}$ If a number $n$ is "bitter", then so are all its multiples.

$\text{Proof :}$ Let $(a, b)$ such that $a+b=n$ be a tuple which destroys the "tasty" nature of $n$ . Then $(ka, kb)$ trivially destroys the "tasty" nature of any multiple $nk$ . So the claim is proven. $\square$

For any primes $p\geq 5$ , observe that $(p-3,3)$ or $(p-6,6)$ destroys the "tasty" nature of most primes $p$ . If they do not, then $p-3$ is power of $2$ and $p-6$ is a power of $5$ . Then $(p-9,9)$ requires that $(p-9)$ is a power of $2$ . So we have powers of two with difference $6$ , they are $(p-3),(p-9)$ which is not possible for primes $>11$ . So the claim proves that any number divisible by a prime $>11$ is "bitter". For primes $2, 3, 5,7,11$ observe that $(3,13)$ destroys "tasty" nature of $2^4$ , $(13,14)$ destroys the "tasty" nature of $3^3$ , $(13,12)$ destroys the "tasty" nature of $5^2$ , $(26,23)$ destroys the "tasty" nature of $7^2$ and $(60,61)$ destroys the "tasty" nature of $11^2$ so the claim shows that any tasty number is a divisor of $2^3\cdot 3^2\cdot 5\cdot 7\cdot 11=9240$ hence there are finitely many "tasty" numbers.

Note : Since we know that all "tasty" numbers divide $9240$ we can actually obtain all of them. They are $\{3,4,5,6,7,8,9,11,12,15,21\}$ .

EDIT : Yikes!! I thought only one of $\frac{a} {b}$ and $\frac{b} {a}$ has to be non-terminating. Sorry, this does not change the solution much though. Made relevant changes.

This post has been edited 8 times. Last edited by babu2001, Jun 26, 2017, 11:44 AM

Z K Y

The post below has been deleted. Click to close.

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

SAUDITYA

250 posts

SAUDITYA

#4 h Jun 26, 2017, 7:47 AM • 3 Y

Y by centslordm, Adventure10, Mango247

No ,
We will show that there is no tasty number $n > 2^{2017}$ .
See that a rational number written in lowest form has terminating decimal expansion if and only if its denominator is of form $2^a5^b$ .
Now,
Assume that $\exists n > 2^{2017}$ such that $n$ is tasty!
See that " $\frac{a}{b}$ or $\frac{b}{a}$ " is terminating if and only if " $\frac{n}{a}$ or $\frac{n}{b}$ " is terminating(Here we have $a+b =n$ !)
Now,
By Bertrand's Postulate there exists primes $p,q$ in between $\frac{n}{8} \ge p , q \ge \frac{n}{64}$
See that $n >> 64\sqrt{n} => \frac{n}{8} > p,q > \sqrt{n} > 5$ .See that $pq >n => pq\nmid n$ . So WLOG $=> p \nmid n$ and $n-4p > 4p$
Consider the pairs $(n-p,p) , (n-2p,2p), (n-3p,3p)$ and $(n-4p,4p)$
See that $\frac{n}{pk} \forall k = (1,2,3,4)$ is never terminating because $p >5$ will always divide the denominator even when written in lowest form
Now,
See that $\frac{n}{n-kp} \forall k = (1,2,3,4)$ has to be terminating or else $n$ will be
Case 1. $n$ is even
See that $2 | n-2p => 2 \nmid n-p$ and $n-3p$ or else $2|p$ ,contradiction!
Now,
$n-p > 7p >35$ and $gcd(n,n-p) =1 => n-p = 5^a > 5 => a >0$
$n-3p >5p > 25$ and $gcd(n,n-3p) = 1$ or $3=> n-3p = 5^c$ or $3.5^c > 15 => c>0$
$=> 5|n-p$ and $5|n-3p => 5|2p$ ,contradiction!

Case 2. $n$ is odd
see that $2| n-3p => 2 \nmid n-2p$ and $n-4p$ or else $2|p$ ,contradiction!
Now,
$n-2p > 6p >30$ and $gcd(n,n-2p) = 1 => 5|n-2p$
$n-4p > 4p >20$ and $gcd(n,n-4p) = 1 => 5|n-4p$
So $5|2p$ , contradiction!

Hence $n$ is not tasty! , contradiction

Z K Y

The post below has been deleted. Click to close.

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

rmtf1111

698 posts

rmtf1111

#5 h Jun 26, 2017, 7:49 AM • 4 Y

Y by kk108, centslordm, Adventure10, Mango247

I like to overkill-PNT, Mihailescu, LTE, Case-bashing aaand also not-so-well written

The answear is NO

Lemma 1 (Trivial)
Case 1
Case 2
Case 3
Case 4

This post has been edited 1 time. Last edited by rmtf1111, Jun 26, 2017, 7:50 AM

Z K Y

The post below has been deleted. Click to close.

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

TheDarkPrince

3042 posts

TheDarkPrince

#6 h Jun 26, 2017, 7:50 AM • 7 Y

Y by RMO17geek, Maths_Guy, centslordm, denistusk, Adventure10, Mogmog8, Mango247

We say $k$ is yummy if $k$ is of the form $2^i5^j$ for $i,j \in \mathbb{N}_{0}$ .
We know that a fraction is terminating if and only if the denominator is yummy.
Let $S = \{1,2,..,n-1\}$
$n = a+b$ , so $b = n-a$ , where $a \in S$ .
So a number $n$ is tasty if for every $a$ , atleast one of $a$ and $n-a$ is yummy $a \in S$ .

So for a number $n$ to be tasty we need atleast $\lceil\left(\frac{n-1}{2}\right)\rceil$ of the elements of $S$ is of yummy.(This condition is just a minimal condition not a strong one)

We know that the number of numbers in $S$ of the form $2^k$ and of the form $5^m$ are $[\log_2 n]$ and $[\log_5 n]$ respectively, where $[x]$ is the greatest integer less than $x$ .

So $n$ is tasty if atleast, $\lceil\frac{n-1}{2}\rceil \leq \text{The number of numbers in $S$ that are yummy} \leq ([\log_2 n] + 1)([\log_5 n] + 1) \leq (\log_2 n +1)(\log_5 n +1)$ Let $n = 2^k$ for $k \in \mathbb{R}^{+}$ .
As $5>2^2$ , $\frac{k}{2}=\frac{\log_2 n}{2}>\log_5 n$ .

So, $(\log_2 n +1)(\log_5 n +1) \leq (k+1)(k/2 + 1) = \frac{(k+1)(k+2)}{2}$
For $k\geq 6$ , $\frac{(k+1)(k+2)}{2} \leq \frac{(2^k - 1)}{2} = \frac{n - 1}{2}$ .

But we had $\frac{n-1}{2} \leq (\log_2 n +1)(\log_5 n +1)$ .

So none of the numbers greater than $64$ are tasty.
So we have that there doesn't exist infinite tasty numbers.

Z K Y

The post below has been deleted. Click to close.

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

shinichiman

3212 posts

shinichiman

#7 h Jun 26, 2017, 7:51 AM • 5 Y

Y by Tawan, Anar24, centslordm, Adventure10, Mango247

We prove that there doesn't exist infinitely many tasty numbers. Assume the contrary, consider sufficient large tasty number $n$ . Let $p_k$ be the smallest prime so that $p_k \nmid n$ and $p_k >5 \; (k \ge 3)$ . Let $p_1<p_2< \ldots, p_{k-1}$ be all primes less than $p_k$ and $p_i \mid n$ for all $1 \le i \le k-1$ . We have $n \ge p_1 \cdots p_{k-1} > 3^{k-2}(p_k+1)$ (since $2p_{k-1}>p_k$ according Bernard postulate and $p_i \ge 2$ for all $i \ge 2$ ).

Pick $a=p_k$ then $b=n-p_k$ so $\frac ba$ is not terminating decimal. Hence, $\frac ab$ must be or $b=n-p_k=2^x5^y$ .
Pick $a=2p_k$ then similarly $b=n-2p_k=2^m5^l$ . Pick $a=3p_k$ then similarly $b=n-3p_k=2^u5^v$ .

If $x=0$ then $n$ is even and $y \ge 1$ so $n=p_k+5^y > 3^{k-2}(p_k+1)$ . Thus, $5 \mid n-p_k$ . Since $n$ is even then $u=0$ so $n=3p_k+5^v$ which follows $v \ge 1$ . Thus, $5 \mid n-3p_k$ . Hence, $5 \mid 2p_k$ , a contradiction.

If $x \ge 1$ then $n$ is odd so $m=0$ so $l \ge 1$ to get $n=2p_k+5^l>3^{k-2}(p_k+1)$ . Thus, $5 \mid n-2p_k$ . Since $n$ is odd so $u \ge 1$ . Since $5 \mid n-2p_k$ so $v=y=0$ . Thus, $n=3p_k+2^u=2p_k+5^l=p_k+2^x$ which follows $p_k=5^l-2^u=2^{x-1}-2^{u-1}$ . Thus, $u=1$ or $n=3p_k+2<3^{k-2}(p_k+1)$ , a contradiction.

Thus, there doesn't exist infinitely many tasty number $n$ .

Z K Y

The post below has been deleted. Click to close.

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

whatshisbucket

975 posts

whatshisbucket

#8 h Jun 26, 2017, 7:57 AM • 3 Y

Y by centslordm, Adventure10, Mango247

For those wondering, the complete set of tasty numbers is $\{3,4,5,6,7,8,9,11,12,15,21\}.$

Z K Y

The post below has been deleted. Click to close.

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

Ankoganit

3070 posts

Ankoganit

#9 h Jun 26, 2017, 8:09 AM • 4 Y

Y by kk108, shinichiman, centslordm, Adventure10

The answer is $\textsc{No}$ . We will show that $n$ can't be tasty for sufficiently large values of $n$ .

First, we'll prove a lemma:

Lemma: $\varphi(n)\ge \sqrt{\frac{n}{2}}$ for all $n>1$ .
Proof: Note that the inequality $p^{a-1}(p-1)\ge \sqrt{p^a}$ holds for all prime $p\ge 3$ and for positive integers $a$ . Indeed, For $a>1$ , this is simply $p^{\frac{a}{2}-1}(p-1)\ge 1$ , which is true, and for $a=1$ , this is $p-1\ge p^{\frac12}$ , which is again true. Also, this is true for $p=2$ and $a>1$ , as seen from the above proof. So if $n$ is odd or divisible by $4$ , the above inequality can be multiplied for all prime power divisors of $n$ to yield $\varphi(n)\ge \sqrt{n}$ , which is stronger than the desired result. For $n=2m$ with $m$ odd, note that $\varphi(n)=\varphi(2)\varphi(m)\ge 1\cdot\sqrt{m}=\sqrt{\tfrac{n}{2}}$ , as desired. $\square$

Consider some large $n$ . Consider the $\tfrac{\varphi (n)}{2}$ pairs of integers $(i,n-i)$ for $1\le i<\tfrac{n}{2}$ , with $(i,n)=1$ . For any such pair $(i,n-i)$ , we need that one of $\tfrac{i}{n-i}$ and $\tfrac{n-i}{i}$ is terminating. Note that $\tfrac{i}{n-i}=\tfrac{n}{n-i}-1$ and $\tfrac{n-i}{i}=\tfrac{n}{i}-1$ , so this is same as saying one of $\tfrac{n}{i}$ and $\tfrac{n}{n-i}$ is terminating. Since both the denominators are relatively prime with $n$ , this implies at least one of $i$ and $n-i$ is a number of the form $2^a5^b$ for non-negative integers $a,b$ . So there are at least $\tfrac{\varphi(n)}{2}$ numbers of the form $2^a5^b$ not exceeding $n$ . But $a$ can't exceed $\log_2n$ and $5$ can't exceed $\log_5n$ , so the total number of such numbers less than or equal to $n$ can't be bigger than $(\log_2 n+1)(\log_5n+1)$ , which is smaller than $\tfrac{1}{2}\sqrt{\tfrac{n}{2}}$ and hence smaller than $\tfrac12\varphi(n)$ for large enough $n$ , because asymptotics. This proves our claim. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Ankoganit

3070 posts

Ankoganit

#11 h Jun 26, 2017, 8:25 AM • 2 Y

Y by centslordm, Adventure10

TheDarkPrince wrote:

We know that a fraction is terminating if and only if the denominator is yummy.

That's not true. $\frac 36$ has a terminating decimal expansion but $6$ isn't yummy.

Z K Y

The post below has been deleted. Click to close.

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

kk108

2649 posts

kk108

#12 h Jun 26, 2017, 8:44 AM • 3 Y

Y by centslordm, Adventure10, Mango247

Yeah I was about to say that...

Z K Y

The post below has been deleted. Click to close.

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

vjdjmathaddict

502 posts

vjdjmathaddict

#13 h Jun 26, 2017, 8:47 AM • 3 Y

Y by centslordm, Adventure10, Mango247

perhaps the easiest problem on the test.

Z K Y

The post below has been deleted. Click to close.

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

TheDarkPrince

3042 posts

TheDarkPrince

#14 h Jun 26, 2017, 9:24 AM • 4 Y

Y by Maths_Guy, centslordm, Adventure10, Mango247

Ankoganit wrote:

TheDarkPrince wrote:

We know that a fraction is terminating if and only if the denominator is yummy.

That's not true. $\frac 36$ has a terminating decimal expansion but $6$ isn't yummy.

Yup I agree, I made a mistake.

Z K Y

The post below has been deleted. Click to close.

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

MSTang

6012 posts

MSTang

#15 h Jun 26, 2017, 8:37 PM • 4 Y

Y by Wave-Particle, centslordm, Adventure10, Mango247

We prove that all sufficiently large $n$ are not tasty.

Suppose $n > 2$ is tasty. Choose some integer $a \in \{1, 2, \ldots, n-1\}$ with $\gcd(a, n) = 1$ ; there are $\phi(n)$ such $a$ . Defining $b = n-a$ , note that $\gcd(b, n) = 1$ , and either $\tfrac{a}{b} = \tfrac{n}{b} - 1$ or $\tfrac{b}{a} = \tfrac{n}{a} - 1$ terminates. Thus either $\tfrac{n}{a}$ or $\tfrac{n}{b}$ terminates. Since $\gcd(a, n) = \gcd(b, n) = 1$ , either $a$ or $b$ is of the form $2^e5^f$ for some integers $e, f \ge 0$ . Thus there are at least $\tfrac12\phi(n)$ integers in the interval $\{1, 2, \ldots, n-1\}$ of the form $2^e5^f$ for some $e,f \ge 0$ . Note that $2^e5^f \le n \implies 2^{e+f} \le n \implies e+f\le \log_2(n).$ Hence there are at most $\tfrac12 (\log_2(n) + 1)(\log_2(n) + 2)$ such pairs $(e,f)$ . Thus we need $\tfrac12 \phi(n) \le \tfrac12 (\log_2(n) + 1)(\log_2(n) + 2).$ But recall that $\sum_{d \mid n} \phi(d) = n,$ and furthermore we have the fact $d \mid n \implies \phi(d) \mid \phi(n)$ . Thus $\sum_{d \mid n} \phi(d) \le \sum_{d \mid n} \phi(n) = \tau(n)\phi(n)$ , so $\phi(n) \ge \frac{n}{\tau(n)}$ . Furthermore, $\tau(n) \le 2\sqrt{n}$ since divisors of $n$ come in pairs, one greater than $\sqrt{n}$ and one less than $\sqrt{n}$ . Thus $\phi(n) \ge \tfrac12 \sqrt{n}$ , so $\sqrt{n} \le 2(\log_2(n)+1)(\log_2(n)+2)$ which fails for sufficiently large $n$ . $\square$

Z K Y

The post below has been deleted. Click to close.

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

smy2012

688 posts

smy2012

#16 h Jun 29, 2017, 8:42 AM • 3 Y

Y by centslordm, Adventure10, Mango247

My solution involves finding a class of "untasty" numbers.
That is for prime $p$ , $p^l$ is not tasty if $p^{l-1}(p-1)>2\log_2 p\cdot \log_5 p$
Thus, exists a $N$ s.t. for any prime power $p^s>N$ , $p^s$ is untasty. We can only have finitely many possible tasty number.

This post has been edited 1 time. Last edited by smy2012, Jun 29, 2017, 8:43 AM

Z K Y

The post below has been deleted. Click to close.

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

atmchallenge

980 posts

atmchallenge

#17 h Jul 1, 2017, 5:47 PM • 3 Y

Y by centslordm, Adventure10, Mango247

Problem 4

Could someone look over my solution and let me know where I went wrong? I personally can't seem to find the error

.

Z K Y

The post below has been deleted. Click to close.

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

tree3

641 posts

tree3

#18 h Jul 3, 2017, 4:23 AM • 9 Y

Y by Ankoganit, JustAnAverageAopser, vjdjmathaddict, atmchallenge, SD2014, Wizard_32, centslordm, Adventure10, Mango247

I think this is new.
Problem 4

This post has been edited 7 times. Last edited by tree3, Jul 3, 2017, 10:39 PM

Z K Y

The post below has been deleted. Click to close.

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

Superguy

354 posts

Superguy

#20 h May 29, 2018, 4:26 AM • 3 Y

Y by centslordm, Adventure10, Mango247

So here is my lengthy solution.
Solution

This post has been edited 1 time. Last edited by Superguy, May 29, 2018, 4:31 AM

Z K Y

The post below has been deleted. Click to close.

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

aadhitya

98 posts

aadhitya

#21 h Feb 20, 2019, 7:31 PM • 2 Y

Y by centslordm, Adventure10

Not sure if my solution is correct.....

Let $n$ be a tasty number.
Let $d$ be a natural number less than $n$ and relatively prime to $n$ . Also $d$ is not of the form $2^x.5^y$ .

Notice that $\frac{n-d}{d}$ can't have a terminating decimal representation because $n-d$ and $d$ are co prime and d contains some prime factors other than $2$ and $5$ .
So $\frac{p}{n-p}$ has a terminating decimal representation. This would imply that $n - p$ is of the form $2^x.5^y$ .

So $\phi(n)$ $-X$ $\leq X$ where $X$ denotes the number of numbers less than $n$ that are of the form $2^x.5^y$ .
$\implies \phi(n) \leq 2X$ .

One can easily show that $X < (\log_2(n) +1) . (\log_5(n)+1)$ and $\phi(n) \geq \frac{\sqrt{n}}{\sqrt{2}}$ .

So, we have $\frac{\sqrt{n}}{\sqrt{2}} \leq (\log_2(n) +1) . (\log_5(n)+1)$ . But clearly this is not true for large $n$ since square root function grows more rapidly than logarithmic function.

Therefore, the answer is NO

This post has been edited 1 time. Last edited by aadhitya, Feb 21, 2019, 6:58 AM

Z K Y

The post below has been deleted. Click to close.

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

NMN12

26 posts

NMN12

#23 h Feb 11, 2020, 2:21 PM • 2 Y

Y by centslordm, Adventure10

Answer: No all numbers greater than 21 are not tasty.
Claim: If a number $m$ is not tasty then all $km$ for k natural are not tasty.
Proof: Consider the pair $(a,b)$ for which $m$ is not tasty then $(ka,kb)$ shows that $km$ is not tasty.
Claim: All numbers $n$ greater than 21 are not tasty.
Proof: 11 and 13 are not tasty. Then $n$ is not multiple of 11 nor 13. Consider the pairs $(11,n-11)$ and $(13,n-13)$ either one of them shows that $n$ is not tasty. Because if not both $n-11$ and $n-13$ will be of the form $2^x5^y$ and we will have an exponential equation, which can be solved by using mod 8 and mod 5

This post has been edited 4 times. Last edited by NMN12, Feb 11, 2020, 2:23 PM

Z K Y

The post below has been deleted. Click to close.

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

green_leaf

225 posts

green_leaf

#24 h Feb 29, 2020, 3:04 PM • 4 Y

Y by lilavati_2005, Polynom_Efendi, char2539, centslordm

First note that $2,3,5,7$ are tasty.
Let $p>7$ be a prime. We will prove that if $p$ is tasty, then $p=11$ .
See that at least one of $\frac{p-3}{3}$ or $\frac{3}{p-3}$ has a terminating decimal expansion. $\frac{p-3}{3}$ is irreducible and also the denominator is not of the form $2^i5^j$ so the $\frac{3}{p-3}$ must be terminating. So $p-3=2^a5^b$ .
Similarly, taking $(6, p-6)$ gives $p-6=2^c5^d$ .
Finally, $p-7=2^e5^f$ . So, $2^e5^f+4=2^a5^b$ . So clearly, $f=b=0$ and $e=2, a=3$ .
Hence, $p=8+3=11$ . We can verify that $11$ is indeed tasty.

So, all tasty primes are in the set $S= \{2, 3, 5, 7, 11 \}$ .
Now, suppose that some $n$ is not tasty.
So, there exists $a,b$ with $a+b=n$ and $\frac{a}{b}$ and $\frac{b}{a}$ are both irreducible.
Now, consider $kn$ for any natural $k$ .
Clearly, if we choose $(ka, kb)$ , we get $\frac{ka}{kb}=\frac{a}{b}, \frac{kb}{ka} = \frac{b}{a}$ which are clearly both irreducible by choice of $a,b,n$ .

Hence any multiple of non-tasty integer is also non-tasty.
From this, it is clear that all tasty integers have only prime divisors in $S$ .
Let a tasty integer $n=2^a3^b5^c7^d11^e$ where $n$ is sufficiently large.
Now consider $(13, n-13)$ , we get $\frac{n-13}{13}$ is clearly irreducible and also non terminating.
Hence, for $n$ to be tasty, $\frac{13}{n-13}$ must be terminating.
So, $n-13=2^a3^b5^c7^d11^e-13=2^r5^s$ .
Similarly, for $17$ we have $n-17=2^a3^b5^c7^d11^e-17=2^t5^u$ . So $2^r5^s-4=2^t5^u$ . Hence we can only have $r=3, s=0, t=2, u=0$ .
So, $n-13=2^3=8 \implies n=21$ is the max value of $n$ .
So, there are only finitely many values of $n$ 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.

ducktility

20 posts

ducktility

#25 h Jul 13, 2020, 5:03 PM • 1 Y

Y by centslordm

whatshisbucket wrote:

An integer $n>2$ is called tasty if for every ordered pair of positive integers $(a,b)$ with $a+b=n,$ at least one of $\frac{a}{b}$ and $\frac{b}{a}$ is a terminating decimal. Do there exist infinitely many tasty integers?

Proposed by Vincent Huang

Nice problem.

We consider the $\phi (n)$ numbers which are co-prime to $n$ . Suppose $(a, b)$ are a pair of such numbers such that $a+b = n$ . Then, either of the two can be expressed as $2^\alpha 5^\beta$ . In total, there are at most $log _2(n)log _5 (n) + log _2(n) + log _5 (n) + 1$ such numbers. So, $(log_2(n) +1)(log_5(n)+1) \geq \frac{1}{2}\phi (n)$ . Now, we use $\frac{1}{2}\phi (n) \geq \frac{1}{4}\sqrt{n}$ and get $4(log_2(n) +1)(log_5(n)+1) \geq \sqrt{n}$ which is not true for $n \geq 10^8$ (Not the best bound but it works and I know really really really huge bound but it does our job). Hence, the number of such tasty numbers is finite.

This post has been edited 3 times. Last edited by ducktility, Jul 13, 2020, 5:14 PM

Z K Y

The post below has been deleted. Click to close.

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

hakN

429 posts

hakN

#26 h Jun 4, 2021, 5:33 PM • 1 Y

Y by centslordm

Lets call the pairs $(a,b) , a + b = n$ , with $a<b$ and $\gcd{(a,b)} = 1$ lucky. In a lucky pair $(a,b)$ , we must have at least one of $a,b$ of the form $2^{x}\cdot 5^{y} , x,y \geq 0$ . Now consider big enough $n$ .
It is clear that there are $\frac{\varphi(n)}{2}$ lucky pairs. Also since $a,b < n$ and at least one of them must be of the form $2^x \cdot 5^y$ , there are at most $(\log_2n + 1)(\log_5n + 1)$ such pairs.
So we must have $\frac{\varphi(n)}{2} \leq (\log_2n + 1)(\log_5n + 1) < (\log_2n + 1)^2$ .
Now, using the inequality when $n\geq 7$ , $\varphi(n) \geq \sqrt{n}$ , we must have
$\frac{\sqrt{n}}{2} < (\log_2n + 1)^2$ .
But that is clearly false for large enough $n$ , and so there are finitely many $n$ satisfying the condition.

This post has been edited 2 times. Last edited by hakN, Jun 4, 2021, 5:34 PM
Reason: fixed typo

Z K Y

The post below has been deleted. Click to close.

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

mathlogician

1051 posts

mathlogician

#27 h Jul 8, 2021, 12:52 AM

Y by

The answer is no. Define a number that can be expressed in the form $2^m5^n$ for positive integers $(m,n)$ as rare. Remark that if $n$ is tasty, then for each pair of relatively positive integers $(a,b)$ such that $a+b=n$ , at least one of $a$ or $b$ must be rare. This implies that we must have at least $\tfrac{\varphi(n)}{2}$ rare numbers less than $n$ . On the other hand, the number of rare integers less than $n$ is at most $(\log_2(n)+1)(\log_5(n)+1),$ so if $n$ is tasty, it must follow that $(\log_2(n)+1)(\log_5(n)+1) \geq \frac{\varphi(n)}{2}.$ I claim that this inequality is false for all sufficiently large $n$ . It fact, since logarithmic functions grow much slower than the square root function, it suffices to prove the following well-known claim:

Claim: $\varphi(n) \geq \tfrac{1}{2} \sqrt{n}$

Proof: We will prove this by strong induction. First, note that if $n$ is a power of $2$ , $\varphi(n) = \tfrac{1}{2}n \geq \tfrac{1}{2} \sqrt{n}.$ Otherwise, let $p$ be the greatest (odd) prime divisor of $n$ , and write $n = p^ek$ for some positive integers $e$ and $k$ . Then note that $\varphi(n) = \varphi(p^e)\varphi(k) \geq \frac{\varphi(p^e) \sqrt{k}}{2} = \frac{p^{e-1}(p-1) \sqrt{k}}{2} \geq \frac{\sqrt{pk}}{2} = \frac{1}{2} \sqrt{n},$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

CT17

1481 posts

CT17

#28 h Nov 22, 2021, 9:56 PM

Y by

We claim the answer is no.

First, if $n = ab$ where $a$ is not tasty, then there is some pair $c+d=a$ such that neither $\frac{c}{d}$ nor $\frac{d}{c}$ is a terminating decimal. Writing $n = bc + bd$ implies $n$ is not tasty, so a number is not tasty if any of its divisors is not tasty.

For any prime $p > 13$ , at least one of the pairs $(p-11,11)$ , $(p-12,12)$ , and $(p-13,13)$ implies that $p$ is not tasty.

$(6,7)$ implies that $13$ is not tasty.

$(3,118)$ implies that $121$ is not tasty.

$(3,46)$ implies that $49$ is not tasty.

$(3,22)$ implies that $25$ is not tasty.

$(13,14)$ implies that $27$ is not tasty.

$(3,13)$ implies that $16$ is not tasty.

Since only finitely many positive integers are multiples of none of the above numbers, we are done.

This post has been edited 1 time. Last edited by CT17, Nov 22, 2021, 10:00 PM

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5608 posts

megarnie

#29 h Dec 21, 2021, 10:30 PM

Y by

We claim the answer is $\boxed{\text{no}}$ .

Call an integer that isn't tasty disgusting.

Claim: If an integer $n$ is disgusting, then all multiples of $n$ are disgusting.
Proof: Suppose $a+b=n$ and $\frac{a}{b}$ and $\frac{b}{a}$ are repeating decimals. Obviously $\frac{ka}{kb}=\frac{a}{b}$ and $\frac{kb}{ka}=\frac{b}{a}$ are repeating for any positive integer $k$ , which proves our claim.

Claim: All primes $p\ge 13$ are disgusting.
Proof: Let $P(a,b)$ denote the given assertion.

If $p\equiv 1\pmod 3$ , then $P(p-7,7)$ works since $3|p-7$ and $7\nmid p-7$ .

If $p\equiv 2\pmod3$ , then $P(p-11,11)$ works since $3|p-11$ and $11\nmid p-11$ .

Now we will find powers of $2,3,5,7,11$ which are disgusting.

$P(7,9)\implies 16$ is disgusting.

$P(13,14)\implies 27$ is disgusting.

$P(12,13)\implies 25$ is disgusting.

$P(12,37)\implies 49$ is disgusting.

$P(13,108)\implies 121$ is disgusting.

Thus, a tasty number must be a divisor of $2^3\cdot 3^2\cdot 5\cdot 7\cdot 11$ , which solves the problem.

Next, we find all tasty integers.

If $n$ is the power of some prime, we get $n=\boxed{\{4,8,3,9,5,7,11\}}$ all work.

Now suppose two primes $p$ and $q$ , with $p<q$ divide $n$ .

Case 1: $p=2$ .
Then by $P(3,7)$ , we find $10$ is disgusting, so $q\ne5$ .

By $P(3,11)$ , $14$ is disgusting, so $q\ne7$ .

By $P(9,13)$ , $22$ is disgusting, so $q\ne11$ .

Thus, $q=3$ .

$P(7,11)\implies 18$ is disgusting.

So $\nu_3(n)=1$ .

$P(11,13)\implies 24$ is disgusting.

Thus, our solutions here are $\boxed{\{6,12\}}$ , which both work.

Case 2: $p=3$ .
Then $P(13,20)\implies 33$ is disgusting.

Thus, $q\in\{5,7\}$ .

$P(11,34)\implies 3^2\cdot 5$ is disgusting.

$P(11,52)\implies 3^2\cdot 7$ is disgusting.

So $\nu_3(n)=1$ , which gives $\boxed{\{15,21\}}$ , which both work.

Case 3: $p>3$ .
$P(13,22)\implies 5\cdot 7$ is disgusting.

$P(13,42)\implies 5\cdot 11$ is disgusting.

$P(19,58)\implies 7\cdot 11$ is disgusting.

So there are no solutions for this case.

Thus, our solution set in increasing order is $\{3,4,5,6,7,8,9,11,12,15,21\}$ .

Z K Y

The post below has been deleted. Click to close.

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

guptaamitu1

656 posts

guptaamitu1

#30 h Feb 6, 2022, 10:54 PM

Y by

The answer is NO. We will show all sufficiently large $n$ are not tasty. We look at the ordered pairs when $\gcd(a,b) = 1$ . This equals $\phi(n)$ . Let $M$ satisfy $2^M \le n < 2^{M+1}$ . Observe $n$ has at most $M$ distinct prime divisors. If we denote by $p_i$ the $i$ -th prime, then
$\phi(n) \ge n \cdot \prod_{i=1}^M \left(1 - \frac{1}{p_i} \right) \ge n \cdot \prod_{i=1}^M \left( 1 - \frac{1}{i+1} \right) = n \cdot \frac{1}{M+1} = \frac{n}{M+1} \ge \frac{2^M}{M+1}$ Call a number \emph{good} if $2,5$ are its only prime divisors. Now note when $\gcd(a,b) = 1$ , then for $n$ to be tasty $a,b$ must be good. Observe any numbers $\le n$ has $v_2,v_5 < M+1$ . Hence number of good numbers $\le n$ is at most $(M+1)^2$ . So number of ordered pairs $(a,b)$ with $\gcd(a,b) = 1$ is at most $(M+1)^4$ . This forces the inequality
$\frac{2^M}{M+1} \le (M+1)^4$ Since this cannot hold for large $M$ , so all large enough $n$ are not tasty, as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

BarisKoyuncu

577 posts

BarisKoyuncu

#31 h Apr 12, 2022, 5:28 AM • 1 Y

Y by SerdarBozdag

Here is a different solution.

First of all, see that if a number is not tasty, then so are all its multiples.

Now, check that $13,17,19$ is not tasty since $13=6+7, 17=6+11, 19=6+13$ .

Choose an integer $n>22$ . If $n$ is divisible by any of $13,17,19$ ; then we are done. Assume that $(n,13\cdot 17\cdot 19)=1$ .

Now consider the pairs $(13,n-13), (17,n-17)$ and $(19,n-19)$ . Since these pairs are relatively prime, all the numbers $n-13, n-17, n-19$ should be in the form $2^x\cdot 5^y$ .
See that at most one of them is divisible by $5$ . Hence at least two of them is a power of $2$ . But, observe that this implies $n=22$ . We assumed $n\ge 23$ , contradiction. Hence, none of the numbers greater than $22$ is tasty.

This post has been edited 1 time. Last edited by BarisKoyuncu, Apr 12, 2022, 5:29 AM

Z K Y

The post below has been deleted. Click to close.

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

ricegang67

26 posts

ricegang67

#32 h Feb 21, 2023, 9:54 PM

Y by

The answer is no.

Claim. If $n$ is tasty, then any factor of $n$ is also tasty.

Proof. Let $d > 2$ be a factor of some tasty $n$ . Then, for all choices of $a$ and $b$ such that
$\frac{n}{d}a + \frac{n}{d}b = n,$ we must have $a + b = d$ and $\frac{na/d}{nb/d} = \frac{a}{b}$ is terminating. Thus for all $(a, b)$ with $a + b = d$ , $\frac{a}{b}$ terminates as required. $\square$

Now, it suffices to show that there are only finitely many tasty prime powers. First, we will show that any $p^k$ with $p \ge 13$ is not tasty. This is simple: consider the pairs $(6, p - 6)$ and $(12, p - 12)$ . Clearly $\gcd(6, p - 6) = \gcd(12, p - 12) = 1$ , so if $p$ is tasty, then $p - 6$ and $p - 12$ must both be of the form $2^x 5^y$ . However, $p - 6$ and $p - 12$ are odd, so they are powers of 5, but there are no powers of 5 that differ by 6, so this is impossible.

We therefore only need to show that there are finitely many powers of 2, 3, 5, 7, and 11 which are tasty. Applying identical logic to above on the pairs $(17, p^{k} - 17)$ and $(19, p^{k} - 19)$ shows that this is the case.

This post has been edited 1 time. Last edited by ricegang67, Feb 21, 2023, 9:56 PM
Reason: make sol more concise

Z K Y

The post below has been deleted. Click to close.

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

peppapig_

281 posts

peppapig_

#33 h Mar 16, 2023, 2:21 PM • 1 Y

Y by mulberrykid

We claim that all integers greater than $1323$ cannot be tasty. We can take this in cases.

Case 1: $\nu_3{(n)}>2$
$27$ itself is not tasty, so for any multiple of $27$ , $27k$ is also not tasty because $\frac{13k}{14k}=\frac{13}{14}$ , of which neither itself nor its reciprocal are terminating decimals.

Case 2: $\nu_7{(n)}>1$
Similarly, $49$ is not tasty ( $49=3+46$ ), therefore no multiple of $49$ is tasty.

Case 3: $\nu_3{(n)}=0$ , $\nu_7{(n)}=0$
Since all numbers greater than $21$ relatively prime to both $3$ and $7$ , $n$ can be expressed as $3x+7y$ for some $x$ and $y$ , $n$ cannot be tasty. This is because when simplified, one side will be a multiple of $7$ and the other will be a multiple of $3$ . Therefore no numbers in this case greater than $1323$ are tasty.

Case 4: $\nu_3{(n)}=1$ , $\nu_7{(n)}=0$
Similarly, every $n>63$ in this case can be expressed as $9x+21y$ for some $x$ , $y$ , making $n$ not tasty.

Case 5: $\nu_3{(n)}=2$ , $\nu_7{(n)}=0$
Similarly, every $n>189$ in this case can be expressed as $27x+63y$ for some $x$ , $y$ , making $n$ not tasty.

Case 6: $\nu_3{(n)}=0$ , $\nu_7{(n)}=1$
Similarly, every $n>147$ in this case can be expressed as $3x+49y$ for some $x$ , $y$ , making $n$ not tasty.

Case 7: $\nu_3{(n)}=1$ , $\nu_7{(n)}=1$
Similarly, every $n>441$ in this case can be expressed as $9x+147y$ for some $x$ , $y$ , making $n$ not tasty.

Case 8: $\nu_3{(n)}=2$ , $\nu_7{(n)}=1$
Similarly, every $n>1323$ in this case can be expressed as $27x+441y$ for some $x$ , $y$ , making $n$ not tasty.

Therefore no $n>1323$ can be tasty, proving that there are not infinitely many tasty integers, and we are done.

This post has been edited 3 times. Last edited by peppapig_, Mar 16, 2023, 2:23 PM
Reason: grrrr

Z K Y

The post below has been deleted. Click to close.

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

blackbluecar

303 posts

blackbluecar

#34 h Jul 11, 2023, 3:22 PM

Y by

There are finitely many tasty numbers. Note that $a/b$ is terminating if and only if $b$ is not divisible by any primes other than $2$ and $5$ given that $\gcd(a,b)=1$ . We call a positive integer not divisible by any primes other than $2$ and $5$ stringy

Claim: If $F(n)$ denotes the number of stringy positive integers not exceeding $n$ then $\varphi(n) > 10^{100} \cdot F(n)$ for all sufficiently large $n$ .

Indeed, note that for all large $n$ we have $\varphi(n) > \sqrt{\frac{n}{2}} > 10^{100} \cdot \log_2(n) \cdot \log_5(n) > 10^{100} \cdot F(n)$ as desired. $\square$

Note that $\varphi(n)/2$ denotes the number of ways to pick $a$ and $b$ so that $a+b=n$ and $\gcd(a,b)=1$ . Since $\varphi(n)/2$ exceeds $F(n)$ for all large $n$ , we may choose $\gcd(a,b)=1$ obeying $a+b=n$ and $b$ not only having prime divisors $2$ and $5$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8866 posts

HamstPan38825

#35 h Nov 27, 2023, 6:04 AM • 1 Y

Y by MihaiT

The answer is no; there are finitely many. Take $n$ sufficiently large and consider pairs $(a, b)$ with $a+b=n$ where $\gcd(a, n) = 1$ .

Note that for $a/b$ or $b/a$ to be terminating among these pairs, one of $a, b$ must be of the form $2^k \cdot 5^\ell$ . Since each such value for $a$ corresponds to a unique pair, the number $P$ of pairs must be loosely bounded above by $\log_2 n \cdot \log_5 n$ . On the other hand, we have $\sqrt n < \phi(n) = P < \log_2 n \cdot \log_5 n$ which is an obvious contradiction for $n$ large.

(It is well-known that $\phi(n) > \sqrt n$ for $n \neq 2, 6$ ; this can quickly be checked by multiplicativity of $\phi$ .)

Z K Y

The post below has been deleted. Click to close.

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

N3bula

276 posts

N3bula

#36 h Sep 21, 2024, 8:54 AM

Y by

Note that if $m$ is not tasty any multiple of $m$ is not tasty. If a prime $p>21$ we get that there is a multiple of $3$ such that $3n<p$ and $7\mid 3n-p$ which means that if a value is
tasty it can only be divisible by primes smaller than $21$ , if a value is only divisible by primes smaller than $21$ call this value $n$ and has the property $n>23\dot 29$ ,
we get that there is a multiple of 23 such that $23m<n$ and $29\mid n-23m$ which suffices to prove there are only finitely many tasty values.

Z K Y

The post below has been deleted. Click to close.

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

pie854

243 posts

pie854

#37 h Feb 16, 2025, 5:14 PM

Y by

Let $n$ be sufficiently large and suppose that it is tasty. Let $a$ be such that $\gcd(a,n)=1$ . Then, $\gcd(n-a,a)=1$ . Since either $a/(n-a)$ or $(n-a)/a$ must be terminating, we must have that either $a$ or $n-a$ must be of the form $2^a 5^b$ . Thus, the number of integers of the form $2^a 5^b$ less than $n$ must be greater than $\phi(n)/2$ . But, this is obviously wrong for large enough $n$ .

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

632 posts

cursed_tangent1434

#38 h Feb 25, 2025, 11:11 AM

Y by

We claim that the answer is in fact no. It is well known that the fraction $\frac{a}{b}$ is a terminating decimal if and only if the denominator $b$ is of the form $b=2^k\cdot 5^l$ for non negative integers $k$ and $l$ .

Now, consider sufficiently large $n$ . We shall show that it is not tasty. Since $n=(n-3)+3$ we must have $n-3=2^u5^v$ and since $n=(n-7)+7$ we must have $n-7=2^x5^y$ . Plugging in one expression for $n$ into the other we obtain the diophantine,
$2^x5^y+4=2^u5^v$ We have two cases.

Case 1 : If $y>0$ , then the left hand side is clearly $4 \pmod{5}$ which implies that $v=0$ . The equation then rewrites to,
$2^x5^y+4=2^u$ for sufficiently large $n$ we must have $u>3$ so,
$2^{x-2}5^y +1=2^{u-2}$ But then clearly the left hand side is odd and the right hand side is even unless $x=2$ . Then,
$5^y+1=2^{u-2}$ which has no solutions by Mihailescu's Theorem.

Case 2 : If $y=0$ then,
$2^x +4=2^u5^v$ once again for sufficiently large $n$ we are required to have $x>3$ so,
$2^{x-2}+1=2^{u-2}5^v$ But if $u>2$ the right hand side is even while the left hand side is odd which is a clear contradiction. Thus, $u=2$ and we have,
$2^{x-2}+1=5^{v}$ which once again has no solutions when $v>1$ by Mihailescu's Theorem. But for sufficiently large $n$ we must have $v>1$ so this case fails to generate infinite solutions as well.

Thus, it is clear that the number of tasty integers is in fact finite, as desired.

Z K Y