Call a positive integer "useful but not optimized " (!), if it can be written as a sum of distinct powers of $3$ and powers of $5$. Prove that there exist infinitely many positive integers which they are not "useful but not optimized". (e.g. $37=(3^0+3^1+3^3)+(5^0+5^1)$ is a " useful but not optimized" number) Proposed by Mohsen Jamali
Problem
Source: Iranian TST 2018, second exam day 2, problem 4
Tags: number theory, Iran, Iranian TST, TST
18.04.2018 11:37
#4: mistaken
18.04.2018 12:37
Prove that there exist infinitely many positive integers which they are not "useful but not optimized". what does this mean ?
19.04.2018 09:57
To #2 : your proof seems to be wrong since the maximal power of $5$ is $5^{k+1}$. Anyway it can’t be achieved so easily by considering the upper bound.
19.04.2018 11:56
Huh, I thought the idea of considering the upper bound was fine, anyways, let me try: Claim 1: There exist infinitely many positive integer pairs $(m, n)$, such that $1<\frac{5^m}{3^n}<\frac{5}{3}$. See that the pair $(3,4)$ satisfies. Assume the contrary, take the pair with maximal $m$. Denote $f(m, n)=\frac{5^m}{3^n}$. Now, consider the sequence $f(m+1, n+1), f(m+2, n+2), \ldots$. Take the maximum $k$, such that $f(m+k, n+k)<3$. Now, see that $3<f(m+k+1, n+k+1)=\frac{5}{3}\cdot f(m+k, n+k)<5$, it follows that $1<f(m+k+1, n+k+2)<\frac{5}{3}$, which proves the claim. Observe that in these pairs, $n$ can't be bounded. Claim 2: For such $(m, n)$, $3^n-1$ is "useful but not optimized". The numbers one can use to write $3^n-1$ is $1, 3, \ldots 3^{n-1}$ and $1, 5, \ldots, 5^{m-1}$. The sum of all of them is $\frac{3^n-1}{2}+\frac{5^m-1}{4}<\frac{3^n-1}{2}+\frac{5\cdot3^{n-1}-1}{4}<\frac{11}{4}\cdot 3^{n-1}<3^n-1$, q.e.d.
23.04.2018 10:01
This one reminds me of the BMO 2016/6, the one of charming integers.
07.06.2018 10:06
The numbers that are "useful but not optimized" less than $n$ are at most $$2^{1+log_3n}+2^{1+log_5n}=2(n^{log_32}+n^{log_52})<2(n^{\frac{2}{3}}+n^{\frac{1}{2}}).$$When $n$ goes to infinity, so does $n-2(n^{\frac{2}{3}}+n^{\frac{1}{2}}),$ done.
07.06.2018 10:19
Kirilbangachev wrote: The numbers that are "useful but not optimized" less than $n$ are at most $$2^{1+log_3n}+2^{1+log_5n}=2(n^{log_32}+n^{log_52})<2(n^{\frac{2}{3}}+n^{\frac{1}{2}}).$$When $n$ goes to infinity, so does $n-2(n^{\frac{2}{3}}+n^{\frac{1}{2}}),$ done. Why at most $2^{1+log_3n}+2^{1+log_5n}$?
07.06.2018 20:29
Kirilbangachev wrote: The numbers that are "useful but not optimized" less than $n$ are at most $$2^{1+log_3n}+2^{1+log_5n}=2(n^{log_32}+n^{log_52})<2(n^{\frac{2}{3}}+n^{\frac{1}{2}}).$$When $n$ goes to infinity, so does $n-2(n^{\frac{2}{3}}+n^{\frac{1}{2}}),$ done. It should be $2^{1+log_3n} \times 2^{1+log_5n}$
20.02.2020 22:07
claim: there exist infinitely many integers $n$ such that there exists an integer $m$ $3^{m+1} > 5^n>2.3^m$ proof: suppose the contrary there exists $M : \forall n \ge M$ $3^{m} < 5^n<2.3^m$ $3^{m+3} < 5^{n+3}<2.3^{m+1}$ but $3^{m+4}<5^{n+3}<2.3^{m+1}$ a contradiction now return to our problem if we have $m,n$ such that: $\frac{5^{n+1} -1}{4} + \frac{3^{m+1-1}}{2} < 5^{n+1} <3^{m+1}$ then we're don but notice that that equivalnt to $3^{m+1} > 5^{n+1}>2.3^m$ which is our first claim thus we are done
12.02.2023 06:15
Kirilbangachev wrote: The numbers that are "useful but not optimized" less than $n$ are at most $$2^{1+log_3n}+2^{1+log_5n}=2(n^{log_32}+n^{log_52})<2(n^{\frac{2}{3}}+n^{\frac{1}{2}}).$$When $n$ goes to infinity, so does $n-2(n^{\frac{2}{3}}+n^{\frac{1}{2}}),$ done. It is absolutely wrong!
13.02.2023 05:15