f(n+1) = f(n) + 2^f(n) implies f(n) distinct mod 3^2013

The post below has been deleted. Click to close.

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

6874 posts

#1 h Aug 13, 2013, 6:06 AM • 15 Y

Y by Amir Hossein, narutomath96, artsolver, anantmudgal09, anhtaitran, tenplusten, MathPassionForever, rashah76, Purple_Planet, akjmop, HamstPan38825, megarnie, JingheZhang, Adventure10, ehuseyinyigit

Define a function $f: \mathbb N \to \mathbb N$ by $f(1) = 1$ , $f(n+1) = f(n) + 2^{f(n)}$ for every positive integer $n$ . Prove that $f(1), f(2), \dots, f(3^{2013})$ leave distinct remainders when divided by $3^{2013}$ .

Z K Y

The post below has been deleted. Click to close.

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

ISHO95

221 posts

ISHO95

#2 h Aug 13, 2013, 5:24 PM • 1 Y

Y by Adventure10

$f(n+1)-f(n)=2^{f(n)}$ we have these
$f(2)-f(1)=2^{f(1)}$
$f(3)-f(2)=2^{f(2)}$
.......
$f(n)-f(n-1)=2^{f(n-1)}$
then we have that
$f(n)=2^{f(1)}+2^{f(2)}+...+2^{f(n-1)}+1$
$f(1)$ is odd, => $f(n)$ is odd for every natural $n$ => $2^{f(n)}$ leave $2$ remainder when divided by $3$
for every $n \in N$
Assume that
$f(a)-f(b)$ divisible by $3^{2013}$ for $b<a<3^{2013}$
$f(a)-f(b)=2^{f(b)}+2^{f(b+1)}+...+2^{f(a-1)}$ leave $2(a-b)$ remainder when divided by $3^{2013}$ , because $f(a)$ is not equal to $f(b)$ for $a$ is not equal to $b$
$2$ is not divisible by $3$ => $a-b$ divisible by $3^{2013}$ but $a-b<3^{2013}$ => contradiction
=> we have proved problem!

Z K Y

The post below has been deleted. Click to close.

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

dinoboy

2903 posts

dinoboy

#3 h Aug 13, 2013, 11:34 PM • 12 Y

Y by Binomial-theorem, Amir Hossein, narutomath96, Mediocrity, limopanda, Purple_Planet, OlympusHero, megarnie, sabkx, Adventure10, Mango247, and 1 other user

I do not understand ISHO95's solution at all. Here is a solution which I believe is correct.

First, note that $\text{ord}_{3^n}(2) = 2 \cdot 3^{n-1}$ . As $f(1)$ is odd, we know that for all $n$ $f(n)$ is odd, therefore knowing $f(n)$ modulo $3^{m-1}$ is sufficient to determine $f(n+1)$ modulo $3^m$ . Denote $f(0) = 0$ for convenience (note the recursion still works from $0$ to $1$ ).

Now, I claim that for a nonnegative integer $m$ , we have for all nonnegative integers $n$ that $f(n+3^m) \equiv f(n) + 2 \cdot 3^{m} \pmod{3^{m+1}}$ and furthermore that $f(3^m) \equiv 2 \cdot 3^m \pmod{3^{m+1}}$ . We prove this by induction on $m$ .

Its trivially true for $m=0$ . Now assume it holds for all $n$ when $m \le M$ . We prove it works for $m = M+1$ .

First remark that $f(n + 3^{M+1}) \equiv f(n) + 3 \cdot 2 \cdot 3^M \equiv f(n) \pmod{3^{M+1}}$ so we have $3^{M+1}|(f(n + 3^{M+1}) - f(n))$ . In particular we have $3^{M+1}|f(3^{M+1})$ .

Now, remark that: $\begin{eqnarray*} f(n + 1 + 3^{M+1}) - f(n+1) & \equiv & f(n + 3^{M+1}) + 2^{f(n + 3^{M+1})} - f(n) - 2^{f(n)} \\ & \equiv & f(n + 3^{M+1}) - f(n) \pmod{3^{M+2}} \end{eqnarray*}$ utilizing the fact that $f(n + 3^{M+1}) \equiv {f(n) \pmod{3^{M+1}}}$ so $2$ to those respective values are congruent modulo $3^{M+2}$ as they are both odd. Thus it follows by induction on $n$ that $f(n + 3^{M+1}) - f(n) \pmod{3^{M+2}}$ is the same across all values of $n$ . Now we have: $f(3^{M+1}) - f(2 \cdot 3^M) \equiv f(2 \cdot 3^M) - f(3^M) \equiv f(3^M) \pmod{3^{M+2}}$
Therefore we have $f(2 \cdot 3^M) \equiv 2 f(3^M) \pmod{3^{M+2}}$ , so $f(3^{M+1}) \equiv 3 f(3^M) \equiv 2 \cdot 3^{M+1} \pmod{3^{M+2}}$ . Therefore as $f(3^{M+1}) - f(0) \equiv 2 \cdot 3^{M+1} \pmod{3^{M+2}}$ our induction is complete.

Now we apply induction on $m$ to show that $f(1), f(2), ..., f(3^m)$ form a complete residue system modulo $m$ . It is obviously true for $m=0$ . Now suppose it is true for all $m \le M$ and we wish to show it for $M+1$ . Consider an arbitrary number $k$ modulo $3^{M+1}$ . By the inductive hypothesis we have for some integer $1 \le n \le 3^M$ that $k \equiv f(n) \pmod{3^M}$ . Now write $k \equiv f(n) + z \cdot 3^M \pmod{3^{M+1}}$ . Then we have $f(n + 2z 3^M) \equiv k \pmod{3^{M+1}}$ , and then reduce $n + 2z 3^M$ modulo $3^{M+1}$ to get something in $f(1), f(2), ..., f(3^{M+1})$ . Thus they form a complete residue system as every number $k$ is congruent to one of the values modulo $3^{M+1}$ , completing our induction. As them being a complete residue system implies they are distinct, the problem follows by setting $m = 2013$ so we are done.

Overall this is a pretty simple problem, the observation that $f(n)$ modulo $3^m$ gives you $f(n)$ modulo $3^{m+1}$ is the only thing you need to see and from then on its just details.

Z K Y

The post below has been deleted. Click to close.

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

Binomial-theorem

3982 posts

Binomial-theorem

#4 h Aug 15, 2013, 12:09 PM • 8 Y

Y by Amir Hossein, mathroyal, Purple_Planet, OlympusHero, megarnie, Adventure10, megahertz13, and 1 other user

I know my solution is incredibly similar to dinoboy's and his is a lot more concise however I would like to share mine:

Define $f(x)$ to be such that $f(1)=1$ and $f(x+1)=2^{f(x)}+f(x)$ . Define a function $f_{n}(x)$ such that $0\le f_{n}(x)\le 3^n-1$ and $f_{n}(x)\equiv f(x)\pmod{3^n}$ . Next, define $g_{n}(x)$ such that $0\le g_{n}(x)\le \phi(3^n)-1$ and $g_{n}(x)\equiv f(x)\pmod{\phi(3^n)}$ . We re-write the problem statement as if $x,y\in \{1, 2, \cdots, 3^n\}$ we have $f_{n}(x)=f_{n}(y)\iff x=y$ (i.e. $f_{n}(x)$ is distinct). A few nice properties of these:

By Chinese remainder theorem we have $f_{n-1}(x)\equiv f_{n}(x)\equiv g_{n}(x)\pmod{3^{n-1}}$ .
By Euler's totient we have $f_{n}(x)\equiv 2^{g_n(x-1)}+f_{n}(x-1)\pmod{3^n}$ .
From (1) and (2) along with Chinese Remainder Theorem we have $g_{n}(x)\equiv 2^{g_n(x-1)}+g_{n}(x-1)\pmod{\phi(3^n)}$

What we are attempting to prove: The problem statement holds for $n=k$ and we have $f_{k}(x)=f_{k}(x+3^km)$ where $m$ is a positive integer.

We use induction.

Base case: We have $f_{1}(1)=1, f_{1}(2)=0, f_{1}(3)=2$ therefore the problem statement holds for $k=1$ . Notice that $g_{1}(x)=1$ therefore $f_{1}(x)\equiv 2+f_{n}(x-1)\pmod{3}$ from proposition (2). Therefore it is clear that $f_{1}(x)=f_{1}(x+3m)$ .

Induction hypothesis: The problem statement holds for $n=k$ and we have $f_{k}(x)=f_{k}(x+3^km)$ where $m$ is a positive integer.

We now must prove the problem statement holds for $n=k+1$ and we have $f_{k+1}(x)=f_{k+1}(x+3^{k+1}m)$ . From (1) we have $g_{k+1}(x)\equiv f_{k}(x)\pmod{3^{k}}$ . Therefore we have $g_{k+1}(x)$ is distinct mod $3^k$ when $x\in \{1,2,\cdots, 3^k\}$ . We also have that $g_{k+1}(x)=g_{k+1}(x+3^km)$ . This means that we can separate $g_{k+1}(x)$ into three "groups" that have length $3^k$ and are ordered $g_{k+1}(1), g_{k+1}(2), \cdots, g_{k+1}(3^k)$ . This is incredibly useful. (At this point I know all the notation must be incredibly confusing to the reader, so hence I personally have a table made for $g_{2}(x)$ and $f_{2}(x)$ lining up the terms. When you do this out the notation makes a lot more sense, trust me.)

Because $f_{k}(x)\equiv g_{k+1}(x)\equiv f_{k+1}(x)\pmod{3^k}$ we can separate $f_{k+1}(x)$ into three groups all of whose elements correspond to $f_{k}(x)$ . It is also evident that $f_{k+1}(x)=f_{k+1}(x+3^k)=f_{k+1}(x+2\cdot 3^k)\pmod{3^k}$ . Out of these three groups we must now prove the following:

$f_{k+1}(x)=f_{k+1}(x+3^{k+1}m)$ where $m$ is a positive integer.
$f_{k+1}(x)\neq f_{k+1}(x+3^k)\neq f_{k+1}(x+2\cdot 3^k)\pmod{3^{k+1}}$ .

Both of these two statements boil down to (2). We notice that we have $\begin{align*} f_{k+1}(x+3^k)\equiv 2^{g_{k+1}\left(x+3^k-1\right)}+f_{k+1}\left(x+3^k-1\right)\pmod{3^{k+1}} \\ \implies f_{k+1}(x+3^k)\equiv 2^{g_{k+1}\left(x+3^k-1\right)}+2^{g_{k+1}\left(x+3^k-2\right)}+\cdots+2^{g_{k+1}\left(x\right)}+f_{k+1}(x)\pmod{3^{k+1}} \end{align*}$
We now notice that $g_{k+1}\left(y\right)$ takes on all of the odd integers from $1$ to $\phi\left(3^{k+1}\right)-1$ . This is exactly the number of elements we have above henceforth it happens that $\begin{align*} f_{k+1}(x+3^k)\equiv 2^1+2^3+\cdots+2^{\phi\left(3^{k+1}\right)-1}+f_{k+1}(x)\pmod{3^{k+1}} \\ f_{k+1}(x+3^k)\equiv \left(2\right)\left(\frac{2^{\phi(3^{k+1})}-1}{3}\right)+f_{k+1}(x) \pmod{3^{k+1}}.\end{align*}$
Notice that $v_3(2^{\phi(3^{k+1})}-1)=v_3(4^{3^k}-1)=k+1$ via lifting the exponent. Therefore $v_3\left(\frac{2^{\phi(3^{k+1})}-1}{3}\right)=k$ henceforth $f_{k+1}(x+3^k)\equiv f_{k+1}(x)\pmod{3^k}$ but $f_{k+1}(x+3^k)\neq f_{k+1}(x)\pmod{3^{k+1}}$ . We write $f_{k+1}(x+3^k)-f_{k+1}(x)=z3^k$ where $\gcd(z,3)=1$ . Notice that substituting $x=n3^k+x_1$ we arrive at $f_{k+1}(x_1+(n+1)\cdot 3^k)-f_{k+1}(x_1+n3^k)=z3^k$ from which we can derive $f_{k+1}\left(x+a\cdot 3^k\right)-f_{k+1}\left(x+b\cdot 3^k\right)\equiv (a-b)3^k\pmod{3^{k+1}}$
Now, notice that $f_{k+1}(x+3^k)-f_{k+1}(x)=z3^k, f_{k+1}(x+2\cdot 3^k)-f_{k+1}(x+3^k)=z3^k$ and $f_{k+1}(x+2\cdot 3^k)-f_{k+1}(x)=2z3^k$ therefore the first part of our list of necessary conditions is taken care of. Now, notice that substituting $a=3m, b=0$ into the second equation we arrive at the second condition.

Our induction is henceforth complete.

Because the problem statement holds for all $n$ it also holds for $2013$ and we are done.

This post has been edited 1 time. Last edited by djmathman, Jan 6, 2016, 6:41 PM
Reason: fixed latex

Z K Y

The post below has been deleted. Click to close.

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

saynoaha2

16 posts

saynoaha2

#5 h Dec 5, 2015, 6:29 PM • 2 Y

Y by Adventure10, Mango247

Someone still solving that problems?

Z K Y

The post below has been deleted. Click to close.

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

cefer

293 posts

cefer

#6 h Jan 6, 2016, 6:33 PM • 11 Y

Y by tenplusten, BogdanB, pablock, Abbas11235, Kamran011, Purple_Planet, OlympusHero, sabkx, Adventure10, Mango247, ehuseyinyigit

dinoboy wrote:

... furthermore that $f(3^m) \equiv 2 \cdot 3^m \pmod{3^{m+1}}$ . We prove this by induction on $m$ .

Since $f(3)=11\equiv 2 \pmod{9}$ this claim is not true.

dinoboy wrote:

Overall this is a pretty simple problem, the observation that $f(n)$ modulo $3^m$ gives you $f(n)$ modulo $3^{m+1}$ is the only thing you need to see and from then on its just details.

This is also not true since $f(3) \equiv 2 \pmod{9}$ but $f(3)\equiv 11 \pmod{27}$ .

Here is my solution. We will use induction on $k$ to prove that $\{f(1), \ldots, f(3^k)\}$ give distinct residues modulo $3^k$ and $f(3^k+i)\equiv f(i) \pmod{3^k}$ for all $i\geq 0$ . In other words $f(n) \pmod{3^k}$ is periodic with minimum period $3^k$ . It can be easily checked for small values of $k$ . Suppose it is true for $k$ .

Claim: $f(a+1)\equiv f(b+1) \pmod{3^{k+1}}$ if and only if $f(a)\equiv f(b) \pmod{3^{k+1}}$ .
Proof: If $f(a+1)\equiv f(b+1) \pmod{3^{k+1}}$ , then obviously $f(a+1)\equiv f(b+1) \pmod{3^{k}}$ . By induction hypothesis we get $f(a)\equiv f(b) \pmod{3^{k}}$ . Since all $f(n)$ s are odd this gives $f(a)\equiv f(b) \pmod{2\cdot 3^{k}}$ . Therefore $2^{f(a)}\equiv 2^{f(b)} \pmod{3^{k+1}}$ . Hence
$f(a)=f(a+1)-2^{f(a)}\equiv f(b+1)-2^{f(b)}\equiv f(b) \pmod{3^{k+1}}$ Conversely, if $f(a)\equiv f(b) \pmod{3^{k+1}}$ , then $f(a)\equiv f(b) \pmod{3^{k}}$ which gives $f(a)\equiv f(b) \pmod{2\cdot 3^{k}}$ . Hence $2^{f(a)}\equiv 2^{f(b)} \pmod{3^{k+1}}$ and
$f(a+1)=2^{f(a)}+f(a)\equiv 2^{f(b)}+f(b)\equiv f(b+1) \pmod{3^{k+1}}$
From above claim $f(n) \pmod{3^{k+1}}$ is periodic and minimum period is an integer $n_0$ such that $f(n_0+1)\equiv f(1) \pmod{3^{k+1}}$ . Since $n_0$ is also a period of $f(n) \pmod{3^{k}}$ by induction hypothesis $3^k\mid n_0$ . Hence $n_0=\alpha \cdot 3^k$ for some $\alpha \in \{1, 2, 3\}$ . So all we need is to prove that $\alpha=3$ . By induction hypothesis we know that $f(1), \ldots, f(n_0)$ give each residue modulo $3^k$ exactly $\alpha$ times. Since $f(n)$ s are odd we deduce that these numbers give each odd residue modulo $2\cdot 3^k$ exactly $\alpha$ times. Hence
$\begin{align*} f(n_0+1)&=1+2^{f(1)}+2^{f(2)}+\cdots+2^{f(n_0)}\\ &\equiv 1+\alpha\left(2^1+2^3+\cdots+2^{2\cdot 3^k-1}\right) \tag{mod $3^{k+1}$}\\ &\equiv 1+\frac{2\alpha(2^{2\cdot 3^k}-1)}{3} \tag{mod $3^{k+1}$}\ \end{align*}$ Since $2$ is a primitive root modulo $3^{m}$ for all $m$ the numerator of the last fraction is divisible by $3^{k+1}$ but not $3^{k+2}$ . Thus $f(n_0+1)\equiv 1 \pmod{3^{k+1}}$ if and only if $\alpha=3$ .

This post has been edited 1 time. Last edited by cefer, Jan 6, 2016, 9:23 PM

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6874 posts

v_Enhance

#7 h Jan 30, 2017, 11:08 PM • 18 Y

Y by baladin, nguyenhaan2209, MathPassionForever, bobjoe123, rashah76, Purple_Planet, franchester, akjmop, MassimilianoF, aryabhata000, OlympusHero, v4913, XbenX, blackbluecar, Lukas8r20, Assassino9931, Adventure10, Mango247

I'll prove by induction on $k \ge 1$ that any $3^k$ consecutive values of $f$ produce distinct residues modulo $3^k$ . The base case $k=1$ is easily checked ( $f$ is always odd, hence $f$ cycles $1$ , $0$ , $2$ mod $3$ ).

For the inductive step, assume it's true up to $k$ . Since $2^\ast \pmod{3^{k+1}}$ cycles every $2 \cdot 3^k$ , and $f$ is always odd, it follows that $\begin{align*} f(n+3^k) - f(n) &= 2^{f(n)} + 2^{f(n+1)} + \dots + 2^{f(n+3^k-1)} \pmod{3^{k+1}} \\ &\equiv 2^1 + 2^3 + \dots + 2^{2 \cdot 3^k-1} \pmod{3^{k+1}} \\ &= 2 \cdot \frac{4^{3^k}-1}{4-1}. \end{align*}$ Hence $f(n+3^k)-f(n) \equiv C \pmod{3^{k+1}} \qquad\text{where} \qquad C = 2 \cdot \frac{4^{3^k}-1}{4-1}$ noting that $C$ does not depend on $n$ . Exponent lifting gives $\nu_3(C) = k$ hence $f(n)$ , $f(n+3^k)$ , $f(n+2\cdot3^k)$ differ mod $3^{k+1}$ for all $n$ , and the inductive hypothesis now solves the problem.

Z K Y

The post below has been deleted. Click to close.

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

jeff10

1117 posts

jeff10

#8 h Apr 14, 2017, 1:44 AM • 3 Y

Y by Purple_Planet, Adventure10, Mango247

I think this is pretty similar to above solutions (at least v_Enhance's), but I want to practice proof-writing.
Solution

This post has been edited 2 times. Last edited by jeff10, Apr 14, 2017, 1:46 AM

Z K Y

The post below has been deleted. Click to close.

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

Anar24

475 posts

Anar24

#10 h May 12, 2017, 7:04 PM • 2 Y

Y by Adventure10, Mango247

v_Enhance wrote:

I'll prove by induction on $k \ge 1$ that any $3^k$ consecutive values of $f$ produce distinct residues modulo $3^k$ . The base case $k=1$ is easily checked ( $f$ is always odd, hence $f$ cycles $1$ , $0$ , $2$ mod $3$ ).

For the inductive step, assume it's true up to $k$ . Since $2^\ast \pmod{3^{k+1}}$ cycles every $2 \cdot 3^k$ , and $f$ is always odd, it follows that $\begin{align*} f(n+3^k) - f(n) &= 2^{f(n)} + 2^{f(n+1)} + \dots + 2^{f(n+3^k-1)} \pmod{3^{k+1}} \\ &\equiv 2^1 + 2^3 + \dots + 2^{2 \cdot 3^k-1} \pmod{3^{k+1}} \\ &= 2 \cdot \frac{4^{3^k}-1}{4-1}. \end{align*}$ Hence $f(n+3^k)-f(n) \equiv C \pmod{3^{k+1}} \qquad\text{where} \qquad C = 2 \cdot \frac{4^{3^k}-1}{4-1}$ noting that $C$ does not depend on $n$ . Exponent lifting gives $\nu_3(C) = k$ hence $f(n)$ , $f(n+3^k)$ , $f(n+2\cdot3^k)$ differ mod $3^{k+1}$ for all $n$ , and the inductive hypothesis now solves the problem.

Can you explain please what did you assume by induction and i couldn't understand the steps which lead to find C

This post has been edited 1 time. Last edited by Anar24, May 13, 2017, 10:43 AM

Z K Y

The post below has been deleted. Click to close.

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

Anar24

475 posts

Anar24

#11 h May 13, 2017, 10:41 AM • 1 Y

Y by Adventure10

....................

This post has been edited 1 time. Last edited by Anar24, May 13, 2017, 12:35 PM

Z K Y

The post below has been deleted. Click to close.

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

Anar24

475 posts

Anar24

#12 h May 13, 2017, 12:35 PM • 2 Y

Y by Adventure10, Mango247

v_Enhance wrote:

I'll prove by induction on $k \ge 1$ that any $3^k$ consecutive values of $f$ produce distinct residues modulo $3^k$ . The base case $k=1$ is easily checked ( $f$ is always odd, hence $f$ cycles $1$ , $0$ , $2$ mod $3$ ).

For the inductive step, assume it's true up to $k$ . Since $2^\ast \pmod{3^{k+1}}$ cycles every $2 \cdot 3^k$ , and $f$ is always odd, it follows that $\begin{align*} f(n+3^k) - f(n) &= 2^{f(n)} + 2^{f(n+1)} + \dots + 2^{f(n+3^k-1)} \pmod{3^{k+1}} \\ &\equiv 2^1 + 2^3 + \dots + 2^{2 \cdot 3^k-1} \pmod{3^{k+1}} \\ &= 2 \cdot \frac{4^{3^k}-1}{4-1}. \end{align*}$ Hence $f(n+3^k)-f(n) \equiv C \pmod{3^{k+1}} \qquad\text{where} \qquad C = 2 \cdot \frac{4^{3^k}-1}{4-1}$ noting that $C$ does not depend on $n$ . Exponent lifting gives $\nu_3(C) = k$ hence $f(n)$ , $f(n+3^k)$ , $f(n+2\cdot3^k)$ differ mod $3^{k+1}$ for all $n$ , and the inductive hypothesis now solves the problem.

please can you explain the part where you found C??

Z K Y

The post below has been deleted. Click to close.

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

mastermind.hk16

143 posts

mastermind.hk16

#13 h Mar 1, 2019, 4:53 AM • 3 Y

Y by Purple_Planet, Adventure10, Mango247

We will prove by induction that $f(1),f(2), \dots , f(3^n)$ leave distinct remainders modulo $3^n$ .

Base case: $n=1$ . Clearly $1,3,11 \mod 3$ is a complete residue class modulo $3$ .

Induction hypothesis: Assume it holds for $n=k$

Now we will prove it for $k+1$ .
Notice that $\phi (3^{k+1}) =2 \cdot 3^k$ . So $\text{ord}_2(3^{k+1}) \mid 2 \cdot 3^k$ .
If $f(a) \equiv f(b) \mod 3^k$ then $f(a) \equiv f(b) \mod 2 \cdot 3^k$ , since $f(n)$ is odd for all $n$ . Hence $2^{f(a)} \equiv 2^{f(b)} \mod 3^{k+1}$ .

By the induction hypothesis, $f(1), f(2), \dots , f(3^k)$ is a complete residue system modulo $3^k$ . Then $f(3^{k}+1) \equiv f(c) \mod 3^k \Longrightarrow 2^{f(3^k +1)} \equiv 2^{f(c)} \mod 3^{k+1}$ , where $c \leq 3^k$ .
As a result $f(3^k +2) -f(3^k +1) \equiv f(c+1) -f(c) \mod 3^{k+1}$ . Hence $f(3^k +2 ) \equiv f(c+1) \mod 3^k$ . So $f(3^k +3) -f(3^k+2) = f(c+2)-f(c+1)$ . Continuing in this way, $f(3^k+s) - f(3^k+1) \equiv f(c+s-1) -f(c) \mod 3^{k+1}$ .

Now, using the fact that $f$ is always odd, and the IH we have $f(3^k+1) =1+ \sum_{i=1}^{3^k} 2^{f(i)} \equiv 2+2^3 +2^5 +\dots +2^{2 \cdot 3^k -1} \equiv 2 \cdot \frac{2^{2 \cdot 3^k }-1}{3} +1 \mod 3^{k+1}$ But $v_3 (2^{2 \cdot 3^k }-1) =k+1 \Longrightarrow f(3^k + 1) \equiv 1 \mod 3^k$ , but $f(3^k+1) \not \equiv 1 \mod 3^{k+1}$

Hence $f$ is periodic modulo $3^k$ . But $f(3^k) \not \equiv f(1) \mod 3^{k+1}$ . Clearly, this gives $f(1), f(2), \dots f(2 \cdot 3^k)$ are all distinct modulo $3^{k+1}$ . Moreover, $f(2 \cdot 3^k +1)- f(3^k +1) \equiv f(3^k +1)-f(1) \equiv \lambda 3^k \Longrightarrow f(2 \cdot 3^k+1) \equiv 2 \lambda 3^k +1$ where $\lambda \in \{1,2 \}$
But $2 \lambda \not \equiv \lambda \mod 3$ . So $f(2 \cdot 3^k+1)$ is distinct from all previous values. Then using periodicity again, we are done.

This post has been edited 9 times. Last edited by mastermind.hk16, May 29, 2019, 3:29 AM

Z K Y

The post below has been deleted. Click to close.

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

shankarmath

544 posts

shankarmath

#14 h Mar 25, 2019, 4:53 PM • 2 Y

Y by Purple_Planet, Adventure10

Nice problem

Sorry this is a little bit rough I will try to make it more clear later.

This post has been edited 7 times. Last edited by shankarmath, Mar 26, 2019, 9:31 PM

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

#16 h May 16, 2019, 7:43 PM • 3 Y

Y by Purple_Planet, Adventure10, Mango247

We'll show that $f(1),f(2),\ldots,f(3^n)$ leave distinct remainders mod $3^n$ for all $n$ . We proceed by induction on $n$ . The base case is $n=1$ , and we see that $f(1)=1$ , $f(2)=3$ , and $f(3)=11$ , which are all distinct mod $3$ .

Now suppose $f(1),\ldots,f(3^n)$ are all distinct mod $3^n$ . We'll show that $f(1),\ldots,f(3^{n+1})$ are all distinct mod $3^{n+1}$ . Note that since $f(x)$ is always odd, we have by CRT that
$\{f(1),\ldots,f(3^n)\} \equiv \{1,3,5,\ldots,2\cdot 3^n-1\}\pmod{2\cdot 3^n}.$ Thus,
$f(3^n+1)\equiv f(1)+2^1+2^3+\cdots+2^{2\cdot 3^n-1}\pmod{3^{n+1}}$ by Euler's theorem. We compute
$D:=2^1+2^3+\cdots+2^{2\cdot 3^n-1}=2\frac{4^{3^n}-1}{3}.$ By LTE, we have $\nu_3(D)=n$ , so $D\equiv \pm 3^n\pmod{3^{n+1}}$ . But this means that $f(2),\ldots,f(3^n+1)$ are all distinct mod $3^n$ since $f(1)\equiv f(3^n+1)\pmod{3^n}$ , so by the same argument, we get that $f(3^n+2)\equiv f(2)+D\pmod{3^{n+1}}$ . Continuing in the same way, we get that $f(3^n+k)\equiv f(k)+D\pmod{3^{n+1}}$ . Thus,
$\{f(1),\ldots,f(3^{n+1})\}\equiv\{f(1),f(1)+3^n,f(1)+2\cdot 3^n\}\cup\cdots\cup\{f(3^n),f(3^n)+3^n,f(3^n)+2\cdot 3^n\}\pmod{3^{n+1}}.$ It's clear then that this covers all residue classes mod $3^{n+1}$ , since every induced residue class mod $3^n$ is one of the $3^n$ three element sets, and within each one, we cover all residues mod $3^{n+1}$ in that induced residue class mod $3^n$ , so the induction is complete. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Pluto04

797 posts

Pluto04

#17 h May 17, 2019, 4:47 PM • 2 Y

Y by Purple_Planet, Adventure10

My solution is somewhat similar to that of ISHO95.
First,looking carefully at the functional equation reveals a telescopic cancellation.
$f(n)-f(n-1)=2^{f(n-1)}$ .......... and so on till:
$f(2)-f(1)= 2^{f(1)}$ .
Adding all these equations, we get :
$f(n)=\sum_{i=1}^{n-1}2^{f(i)}+1.$ Clearly f(n) is odd for all n.
Suppose,f(m) and f(t) leave the same remainders when divided by $3^{2013}$ leave the same remainder.
Then,
$f(m)-f(t)= \sum_{i=f(t)}^{f(m-1)}2^{f(i)}$ must be divisible by $3^{2013}$ and also since f(n) is always odd for any n :
$\Rightarrow f(m)-f(t)= \sum_{i=f(t)}^{f(m-1)}2^{f(i)}\equiv 2(m-t)(mod 3^{2013})$ But this is not True since 3 does not divide 2 and m-t<2013 and this is a contradiction.So, we have proved the required result and we are done.

This post has been edited 3 times. Last edited by Pluto04, May 17, 2019, 7:07 PM
Reason: typo error

Z K Y

The post below has been deleted. Click to close.

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

NoctNight

108 posts

NoctNight

#42 h May 13, 2023, 8:12 AM

Y by

We induct to prove the statement: For integers $k\geq 0$ and $n\geq 1$ , we have that
$\{f(n),f(n+1),\ldots, f(3^k-1+n)\}=\{1,3,5,\ldots, 2\cdot 3^k-1\}$ modulo $2\cdot 3^k$ . The base case $k=0$ is trivial since $f(n)$ is always odd. Now assume it is true for $k=m$ . Since $\phi(2\cdot 3^{m+1})=\phi(3^{m+1})=2\cdot 3^m$ , we have that
$\begin{align*} f(a+3^m)-f(a)&\equiv f(a+3^m - 1)+2^{f(a+3^m - 1)}-f(a-1)-2^{f(a-1)}\pmod{2\cdot 3^{m+1}}\\ &\equiv f(a+3^m-1)-f(a-1)\\ &\vdots\\ &\equiv f(3^m+1)-1\\ &\equiv 2^{f(3^m)}+2^{f(3^m-1)}+\ldots+2^{f(2)}+2^{f(1)}+1-1\\ &\equiv \sum_{i=1}^{3^m} 2^{2i-1}\\ &\equiv 2\cdot \frac{4^{3^m}-1}{4-1}\\ &\equiv 2\cdot \frac{4^{3^m}-1}{3} \end{align*}$ By LTE,
$\nu_3\left(\frac{4^{3^m}-1}{3}\right)=\nu_3(4-1)+\nu_3(3^m)-1=m$ so we have that $f(a+3^m)-f(a)\equiv 2\cdot 3^m, 4\cdot 3^m$ modulo $2\cdot 3^{m+1}$ because $f(a+3^m)-f(a)$ is even and has $\nu_3$ equal to $m$ . Thus, $\left\{f(n+i), f(n+i+3^m), f(n+i+2\cdot 3^m\right\}=\{f(n+i),f(n+i)+2\cdot 3^{m+1}, f(n+i)+4\cdot 3^{m+1}\}$ . Therefore:
$\{f(n),\ldots, f(n+3^{m+1}\}=\{1,3,5,\ldots, 2\cdot 3^{m+1}-1\}$ modulo $2\cdot 3^{m+1}$ completing the inductive step and proof by setting $n=1$ .

Z K Y

The post below has been deleted. Click to close.

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

eibc

600 posts

eibc

#43 h Aug 13, 2023, 1:34 AM

Y by

Replace $2013$ with $k$ ; then we will in fact show that $f(x), f(x + 1) \ldots, f(x + 3^{k} - 1)$ leave distinct remainders when divided by $3^k$ for any positive integer $x$ by induction on $k$ . The base case of $k = 1$ is easy to verify. Now, assume that the statement holds for an arbitrary $k$ . We will prove it holds for $k + 1$ . Notice that
$\begin{aligned} f(x + 3^{k}) - f(x) &= f(n + 3^{k} - 1) + 2^{f(x + 3^{k} - 1)} - f(x) \\ &= f(x + 3^{k} - 2) + 2^{f(x + 3^{k} - 2)} + 2^{f(x + 3^{k} - 1)} - f(x) \\ &\vdots \\ &= f(x) + 2^{f(x)} + 2^{f(x + 1)} + \cdots + 2^{f(x + 3^{k} - 1}) - f(x) \\ &= 2^{f(x)} + 2^{f(x + 1)} + \cdots + 2^{f(x + 3^{k} - 1)}. \end{aligned}$ By the inductive hypothesis, we know that $f(x), f(x + 1), \ldots, f(x + 3^k - 1)$ are distinct modulo $3^k$ . Additionally, since all outputs of $f$ are odd, they must in fact be a permutation of $\{1, 3, 5, \ldots, 2 \cdot 3^k - 1\}$ modulo $2 \cdot 3^k$ . Therefore, since $2^{2 \cdot 3^k} \equiv 1 \pmod {3^{k + 1}}$ by Euler, our above sum is equivalent to
$\begin{aligned} 2^1 + 2^3 + \cdots + 2^{2 \cdot 3^k - 1} &\equiv \frac{2(4^{3^k} - 1)}{4 - 1} \pmod {3^{k + 1}}. \end{aligned}$ But from LTE, we have $\nu_3(4^{3^k} - 1) = \nu_2(4 - 1) + \nu_2(3^k) = k + 1$ , so $\nu_3(f(x + 3^k) - f(x)) = k$ . Thus, we have $f(x + 2 \cdot 3^k) - f(x + 3^k)) \equiv f(x + 3^k) - f(x) \equiv \alpha 3^k \pmod {3^{k + 1}}$ for some fixed $\alpha \in \{1, 2\}$ . Using the inductive hypothesis again, this finishes the induction.

This post has been edited 2 times. Last edited by eibc, Aug 13, 2023, 2:01 AM

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

#44 h Aug 20, 2023, 4:24 PM

Y by

This was a relatively easier problem 45 min solve :coolspeak:

We'll prove that $f(n),f(n+1),...,f(n+3^k-1)$ leave different residues mod $3^k$ by induction; the base case k=1 is obvious since mod 3 it's f(n),f(n)-1,...
Note that all f(n) are odd since the first term is odd and then it's odd+2^.=odd; also note that by recursion $f(n)=f(n-1)+2^{n-1}=f(n-2)+2^{n-1}+2^{n-2}=...=2^{n-1}+2^{n-2}+...+1$ . We'll prove it for k+1, assuming the induction for the numbers less than it are already proven; call the inductive hypothesis returning distinct residues and that the exponent is taken mod $3^k2$ by Euler's theorem (1). We have $f(x + 3^{k}) - f(x) \equiv 2^{f(x)} + 2^{f(x + 1)} + \dots + 2^{f(x + 3^{k} - 1)}\stackrel{(1)}{\equiv}2^1+2^3+...+2^{3^k2-1}\equiv\frac{2(4^{3^k} - 1)}{4 - 1}\stackrel{LTE:\nu_3(4^{3^k}-1)=k+1}{\equiv}3^kc\pmod {3^{k + 1}}$ for some constant c either 1 or 2; by the same reasoning $f(x+3^k2)-f(x+3^k)\equiv2^{f(x+3^k)}+2^{f(x+3^k+1)}+\dots\equiv2^1+2^3+...+2^{3^k2-1}\equiv3^kc\pmod {3^{k+1}}$ for the same c; in particular, no matter the choice, it's obvious they're all distinct since $2c,c\not\equiv0\pmod 3$ , and modulo $3^{k+1}$ adding $3^kc$ sufficiently separates the residues in each group (one spans from $[0,3^k-1]$ , another from $[3^k,3^k2-1]$ , and a third from $[3^k2,3^{k+1}-1]$ ). $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

peace09

5417 posts

peace09

#45 h Sep 8, 2023, 3:11 AM

Y by

Click to reveal hidden text

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

#46 h Oct 24, 2023, 5:36 PM

Y by

We will prove by induction that for any $3^k$ consecutive values of $f$ are different modulo $3^k$ . The base case $k=1$ is clearly true.

Assume the inductive statement holds to $n=m$ . Since powers of $2$ cycle every $2 \cdot 3^k$ in mod $3^{k+1}$ and all of the terms are odd, we have

$\begin{align*} f(n+3^k)-f(n) &= \sum_{i=n}^{n+3^k-1} 2^{f(i)} \pmod{3^{k+1}} \\ &\equiv \sum_{i=1}^{3^k} 2^{2i-1} \pmod{3^{k+1}} \\ &\equiv 2 \cdot \frac{4^{3^k}-1}{3} \pmod{3^{k+1}} \end{align*}$
LTE gives us $v_3 (4^{3^k}-1) = v_3(4-1)+v_3(3^k)=k+1$ , so

$v_3 \left(2 \cdot \frac{4^{3^k}-1}{3} \right) = k$
Thus, $f(n)$ , $f(n+3^k)$ , $f(n+2 \cdot 3^k)$ have different residues mod $3^{k+1}$ , completing the inductive step. $\square$

Z K Y

The post below has been deleted. Click to close.

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

Leo.Euler

577 posts

Leo.Euler

#47 h Nov 30, 2023, 6:42 PM

Y by

woah nice, 15 minute solve.

Claim: $\nu_3(f(a+3^i)-f(a)) = i$ .
Proof. Induct on $k$ , with the base case $i=0$ trivial. Then write $f(a+3^i)-f(a) = \sum_{n=a}^{a+3^i-1} f(n+1)-f(n) = \sum_{n=a}^{a+3^i-1} 2^{f(n)}.$ By inductive hypothesis, all of the $f(n)$ for $a \le n \le a+3^i - 1$ leave distinct residues modulo $3^i$ , and note in general that $f$ takes odd integer values. Thus modulo $3^{i+1}$ , we can use FLT to find that $f(a+3^i)-f(a) \equiv \sum_{k=1}^{3^k} 2^{2k-1} = 2 \cdot \frac{4^i-1}{3}.$ Now taking $\nu_3$ we have by LTE that $\nu_3(f(a+3^i)-f(a)) = i$ , as desired.
:yoda:

A consequence of the claim is that $f(a)$ , $f(a+3^i)$ , and $f(a+2 \cdot 3^i)$ have distinct residues modulo $3^{i+1}$ .

Now given $f(a+\Delta)-f(a)$ , write $\Delta$ in ternary so that $\Delta = \sum_{i} b_i \cdot 3^{a_i}$ for distinct $a_i$ and a sequence $b_i$ of numbers in $\{1, 2\}$ . Thus we see by the claim's consequence that $\nu_3(f(a+\Delta)-f(a)) = \nu_3(\Delta)$ by basic $\nu_3$ properties, which finishes.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

794 posts

shendrew7

#48 h Dec 19, 2023, 5:11 AM

Y by

We use induction to show that $f(1), f(2), \ldots$ has period $3^m$ in modulo $3^m$ . (Note that during a given period, we cannot have a residue repeat.) The base case $m=1$ is easy to verify. We then show the hypothesis holds for $n=k+1$ given that it holds for $n=k$ . The problem then rests on the following:

Claim: We have $v_3\left(f(n+2 \cdot 3^k)-f(n)\right) = v_3\left(f(n+3^k)-f(n)\right) = k$ for all positive integers $n$ .

We use our recursion to evaluate
$f(n+3^k)-f(n) = 2^{f(n)} + 2^{f(n+1)} + \ldots + 2^{f(n+3^k-1)}.$
Using modulo $3^{k+1}$ , Euler's Totient Theorem tells us to look at the exponents modulo $2 \cdot 3^k$ . Clearly every exponent is odd, and our inductive hypothesis tells us each leaves a distinct residue modulo $3^k$ , so this expression is equivalent to
$2^1 + 2^3 + \ldots + 2^{2 \cdot 3^k-1} \equiv \frac{2 \left(4^{3^k}-1\right)}{3} \pmod{3^{k+1}}.$
Now we see that $f(n+2 \cdot 3^k)-f(n)$ is equivalent twice this expression, so their $v_3$ 's should be equal. We finish using LTE, as
$v_3\left(\frac{2 \left(4^{3^k}-1\right)}{3}\right) = v_3(4-1) + v_3(3^k) - 1 = k. \quad {\color{blue} \Box}$
Thus we know $f(1), \ldots, f(3^{n+1})$ leave distinct residues modulo $3^{n+1}$ , completing our induction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Shreyasharma

678 posts

Shreyasharma

#49 h Dec 22, 2023, 4:28 AM

Y by

We claim that any $3^m$ values for $n$ gives $f(n)$ with $n \leq 3^m$ distinct remainders when divided by $3^m$ .

Note that $f$ is always odd. Now we induct. Say that the desired holds true for $n = 3^{m-1}$ and that the sequence $f(n)$ is periodic modulo $3^{m-1}$ , with period $3^{m-1}$ . We now show similar statements hold for $3^m$ . Clearly it suffices to show that $f(k)$ , $f(k + 3^{m-1})$ and $f(k + 2 \cdot 3^{m-1})$ leave distinct remainders modulo $3^m$ .

Now we can compute,
$\begin{align*} f(3^{m-1} + k) &= f(3^{m-1} + k - 1) + 2^{f(3^{m-1} + k - 1)}\\ &= f(3^{m-1} + k - 2) + 2^{f(3^{m-1} + k - 1)} + 2^{f(3^{m-1} + k - 2)}\\ &\vdots\\ &= f(k) + \sum_{i = 1}^{3^{m-1}} 2^{f(3^{m-1} + k - i)} \end{align*}$ Then it suffices to show that,
$\begin{align*} \sum_{i = 1}^{3^{m-1}} 2^{f(3^{m-1} + k - i)} \not\equiv 0 \pmod{3^m} \end{align*}$ Note that $\phi(3^m) = 2 \cdot 3^{m-1}$ . Then noting that any $3^{m-1}$ consecutive terms of $f$ leave distinct remainders modulo $3^{m-1}$ from our induction combined with the fact that $f$ is always odd we must have,
$\begin{align*} \{f(3^{m-1} + k - 1), f(3^{m-1}+k - 2), \dots, f(k) \} \equiv (1, 3, 5, \dots, 2 \cdot 3^{m-1} - 1) \pmod{2 \cdot 3^{m-1}} \end{align*}$ Thus we have,
$\begin{align*} \sum_{i = 1}^{3^{m-1}} 2^{f(3^{m-1} + k - i)} =\sum_{i=1}^{3^{m-1}} 2^{2i - 1} \pmod{3^m} \end{align*}$ Now from sum of geometric series we have,
$\begin{align*} \sum_{i=1}^{3^{m-1}} 2^{2i - 1} = 2 \cdot \left(\frac{4^{3^{m-1}} - 1}{3} \right) \end{align*}$ Now it suffices to show $\nu_3(4^{3^{m-1}} - 1) \leq m$ , as then we will have that the product is nonzero modulo $3^m$ . However LTE we find,
$\begin{align*} \nu_3(4^{3^{m-1}} - 1) = m \end{align*}$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

dolphinday

1323 posts

dolphinday

#50 h Jan 5, 2024, 11:48 AM

Y by

Our goal is to prove that $f(n)$ , $f(n + 3^k)$ , and $f(n + 2 \cdot 3^k)$ all have different residues $\pmod{3^{k+1}}$ , which we will accomplish by induction.
Our $k = 1$ case is obviously true.
$\newline$
Now, we need to prove that $f(n + 3^k) - f(n) \not\equiv 0 \pmod{3^{k+1}}$ .
Notice that
$f(n + 3^k) - f(n) = \sum_{i=0}^{i = 3^k - 1} 2^{f(n) + i}$ Since $\phi(3^{k+1}) = 2 \cdot 3^k$ , we will take the exponents of this expression mod $2 \cdot 3^k$ , which results in
$\sum_{i=0}^{3^k-1} 2^{2i+1}$ which is equivalent to
$2 \cdot \frac{4^{3^k} - 1}{3}$ By LTE, $v_3$ of this expression is equal to $k$ , which is less than $k + 1$ , so $f(n + 3^k)$ and $f(n)$ are distinct, modulo $3^{k+1}$ .

This post has been edited 1 time. Last edited by dolphinday, Feb 1, 2024, 1:47 PM

Z K Y

The post below has been deleted. Click to close.

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

blueprimes

334 posts

blueprimes

#51 h Apr 8, 2024, 3:15 PM

Y by

Really nice problem.

We will prove a stronger claim, that the remainders when $f(1), f(2), \dots, f(3^m)$ leave distinct remainders when divided by $3^m$ for all positive integers $m$ . The $m = 1$ case is easy to verify. Now assume the claim for $m$ , we will prove for $m + 1$ .

Lemma 1. The order of $2 \pmod{3^{m + 1}}$ is $2 \cdot 3^m$ .

Proof. Let the order be $t$ , clearly it is even. By Lifting the Exponent Lemma, we obtain
$m + 1 = \nu_3 \left((2^2)^{t / 2} - 1^{t/2} \right) = \nu_3(2^2 - 1) + \nu_3(t / 2),$ then the result follows.

Claim 1. The remainder when $f(k + 3^m) - f(k)$ is divided by $3^{m + 1}$ for positive integers $1 \le k \le 2 \cdot 3^m$ is some constant $d$ , and $d$ is either $3^m$ or $2 \cdot 3^m$ .

Proof. Clearly $f(n)$ is odd for all $n \in \mathbb{N}$ , then the residues of $f(1), f(2), \dots, f(3^m)$ in $\pmod{2 \cdot 3^m}$ are some permutation of $\{ 1, 3, 5, \dots, 2 \cdot 3^m - 1 \}$ by the Chinese Remainder Theorem. Then by Lemma 1, we have
$f(3^m + 1) \equiv f(1) + 2^{f(1)} + 2^{f(2)} + \dots + 2^{f(3^m)} \equiv f(1) + 2^1 + 2^3 + \dots + 2^{2 \cdot 3^m - 1} \equiv f(1) + 2 \left(\frac{2^{2 \cdot 3^m} - 1}{3} \right) \pmod{3^{m + 1}}.$
By Lifting the Exponent Lemma,
$\nu_3 \left((2^2)^{3^m} - 1^{3^m} \right) = \nu_3(2^2 - 1) + \nu_3(3^m) = m + 1,$ then clearly the remainder when $f(3^m + 1) - f(1)$ is divided by $3^{m + 1}$ is $3^m$ or $2 \cdot 3^m$ . Now repeatedly applying this process for the next set of remainders, we will constantly generate a unique remainder $\pmod{3^{m + 1}}$ . Note that the process works as the remainders when $f(k), f(k + 1), \dots, f(k + 3^m - 1)$ are divided by $\pmod{3^m}$ will always be made all distinct.

The latter claim finishes as for any residue $r$ of $3^m$ , we have $r, r + d, r + 2d$ leaving distinct residues in $3^{m + 1}$ . Our induction is complete. Now let $m = 2013$ , and we are done. $\blacksquare$

This post has been edited 1 time. Last edited by blueprimes, Apr 8, 2024, 3:16 PM

Z K Y

The post below has been deleted. Click to close.

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

Markas

105 posts

Markas

#52 h May 5, 2024, 1:56 PM

Y by

We will prove by induction that $f(1),f(2), \cdots , f(3^n)$ have distinct remainders $\pmod 3^n$ . Base case: n=1. Obviously $1,3,11 \pmod 3$ have distinct residues modulo 3. Induction hypothesis: Assume it holds for n=k.

Now we will prove it for k+1. We can see that $\phi (3^{k+1}) = 2.3^k$ . So ${ord}_2(3^{k+1}) \mid 2.3^k$ . If $f(x) \equiv f(y) \pmod {3^k}$ then $f(x) \equiv f(y) \pmod {2.3^k}$ , since f(n) is odd for all n $\Rightarrow$ $2^{f(x)} \equiv 2^{f(y)} \pmod {3^{k+1}}$ .

By the induction hypothesis $f(1), f(2), \cdots , f(3^k)$ is a complete residue system mod $3^k$ . Then $f(3^{k}+1) \equiv f(z) \pmod {3^k}$ $\Rightarrow$ $2^{f(3^k +1)} \equiv 2^{f(z)} \pmod {3^{k+1}}$ . So now we have $f(3^k +2) - f(3^k +1) \equiv f(z+1) - f(z) \pmod {3^{k+1}}$ $\Rightarrow$ $f(3^k + 2) \equiv f(z+1) \pmod {3^k}$ . So $f(3^k +3) - f(3^k+2) = f(z+2) - f(z+1)$ . Continuing this $f(3^k+s) - f(3^k+1) \equiv f(z+s-1) - f(z) \pmod {3^{k+1}}$ .

Now, using the fact that f is always odd, and the hypothesis we have, $f(3^k+1) = 1 + \sum_{i=1}^{3^k} 2^{f(i)} \equiv 2+2^3 +2^5 +\cdots +2^{2.3^k - 1} \equiv 2 \cdot \frac{2^{2.3^k} - 1}{3} +1 \pmod {3^{k+1}}$ . But $v_3 (2^{2 \cdot 3^k} - 1) = k+1$ $\Rightarrow$ $f(3^k + 1) \equiv 1 \pmod {3^k}$ , but $f(3^k+1) \not \equiv 1 \pmod {3^{k+1}}$ Hence $f$ is periodic modulo $3^k$ . But $f(3^k) \not \equiv f(1) \pmod {3^{k+1}}$ Clearly, this shows that $f(1), f(2), \dots f(2 \cdot 3^k)$ are all distinct mod $3^{k+1}$ . Also, $f(2 \cdot 3^k +1)- f(3^k +1) \equiv f(3^k +1)-f(1) \equiv m.3^k$ $\Rightarrow$ $f(2 \cdot 3^k+1) \equiv 2.m 3^k +1$ where $m \in \{1,2 \}$ .
But $2.m \not \equiv m \pmod 3$ . So $f(2.3^k+1)$ is distinct from all previous values and using the periodicity, we are ready.

Z K Y

The post below has been deleted. Click to close.

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

numbertheory97

42 posts

numbertheory97

#53 h Sep 20, 2024, 11:41 PM

Y by

Fix some $k$ , and consider the assertion that $f(n + 1), f(n + 2), \dots, f(n + 3^k)$ are distinct mod $3^k$ for all integers $n \geq 0$ . We prove this by induction on $k$ , with the base case $k = 1$ trivial (the sequence repeats $1, 0, 2, 1, 0, 2, \dots$ mod $3$ ). This clearly implies the $k = 2013$ case.

We prove the following lemma first, which allows us to lift from $3^k$ to $3^{k + 1}$ .

Claim: Let $\ell$ be a positive integer. Then $\text{ord}_{3^\ell}(2) = 2 \cdot 3^{\ell - 1}$ .

Proof. Let $r = \text{ord}_{3^\ell}(2)$ . Clearly $r$ is even (otherwise $2^r \equiv 2 \pmod 3$ ), so by LTE we have $\nu_3(2^r - 1) = \nu_3(4^{r/2} - 1) = \nu_3(r/2) + \nu_3(4 - 1) = \nu_3(r) + 1.$ Since $3^\ell \mid 2^r - 1$ , it follows that $3^{\ell - 1} \mid r$ . Thus $r$ is divisible by $2 \cdot 3^{\ell - 1}$ , and by minimality we have $r = 2 \cdot 3^{\ell - 1}$ as claimed. $\square$

Continuing with the problem, suppose the result holds for some $k$ , and let $n$ be a positive integer. We're given that $f(n + 1), f(n + 2), \dots, f(n + 3^k)$ are distinct mod $3^k$ , and since $f(m)$ is odd for all positive integers $m$ , $f(n + 1), f(n + 2), \dots, f(n + 3^k)$ form a permutation of $1, 3, 5, \dots, 2 \cdot 3^k - 1$ mod $2 \cdot 3^{k - 1}$ . Thus we have $f(n + 3^k + 1) = f(n + 3^k) + 2^{f(n + 3^k)} = \dots = f(n + 1) + \sum_{i = 1}^{3^k} 2^{f(n + i)}$ $\equiv f(n + 1) + \sum_{i = 1}^{3^k} 2^{2i - 1} = f(n + 1) + \frac23\left(4^{3^k} - 1\right).$ But since $\nu_3\left(\frac23\left(4^{3^k} - 1\right)\right) = \nu_3\left(4^{3^k} - 1\right) - 1 = k$ by LTE again, we obtain $\nu_3(f(n + 3^k + 1) - f(n + 1)) = k$ . By similar arguments, for each $i = 1, 2, \dots, 3^k - 1$ , the values $f(n + i), f(n + 2i), f(n + 3i)$ are in some order congruent to $f(n + i), f(n + i) + 3^k, f(n + i) + 2 \cdot 3^k$ mod $3^{k + 1}$ , which combined with the inductive hypothesis completes the induction. $\square$

Z K Y

The post below has been deleted. Click to close.

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

mathwiz_1207

95 posts

mathwiz_1207

#54 h Feb 18, 2025, 10:30 PM

Y by

We will instead prove that for any $k \geq 1$ , the sequence is periodic modulo $3^k$ , with period exactly $3^k$ . If $k = 1$ , this is obviously true. Now, assume it is true for $k$ , and notice that every term in the sequence is equivalent to $1 \pmod 2$ . Thus, the sequence is in fact also periodic modulo $2 \cdot 3^k$ , with period exactly $3^k$ . Denote these residues as
$a_1, a_2, \dots, a_{3^k}, a_1 , \dots \pmod {2 \cdot 3^k}$ Now, by Euler's theorem, we actually have that
$f(n) \equiv f(n - 1) + 2^{a_{n-1}} \pmod {3^{k + 1}}$ Therefore,
$f(n + 3^k) - f(n) \equiv 2^{a_1} + 2^{a_2} + \cdots + 2^{a_{3^k}} \pmod {3^{k + 1}}$ Since the order of $2$ is $2$ , modulo $3$ , by LTE we have
$v_3(2^{2m} - 1) = 1 + v_3(m) \geq 3^{k + 1} \implies 3^k \mid m$ Therefore, $2$ is in fact a primitive root modulo $3^{k + 1}$ , and since the $a_i's$ are odd,
$2^{a_1} + 2^{a_2} + \cdots + 2^{a_{3^k}}$ covers every residue that is $2 \pmod 3$ , so we in fact have
$f(n + 3^k) - f(n) \equiv 2 + 5 + \cdots + 3^{k + 1} - 1 \equiv \frac{3^{k+1} + 1}{2} \cdot 3^k \pmod {3^{k + 1}}$ Thus, the smallest $a$ such that $f(n + a \cdot 3^k) - f(n) \equiv 0 \pmod {3^{k + 1}}$ is $3$ , 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.

Maximilian113

550 posts

Maximilian113

#55 h Apr 1, 2025, 7:58 PM

Y by

We will show that for any $k \geq 1$ $f(n)$ has minimal period $3^k$ under modulo $3^k.$ We proceed with induction. The base case, $k=1,$ is trivial as $f(n)$ is odd so $2^{f(n)} \equiv -1 \pmod 3,$ and the sequence will always shift down by one.

Now, suppose that the proposition holds for some $k=r \geq 1.$ We show it for $k=r+1.$ By the inductive hypothesis, for nonnegative integers $\ell,$ $f(1+\ell 3^r), f(2+\ell 3^r), \cdots, f(3^r + \ell 3^r)$ is a complete residue system modulo $3^r.$ Apply this for $\ell=0, 1, 2$ so due to periodicity it suffices to show that $f(x), f(x+3^r), f(x+2 \cdot 3^r)$ are distinct modulo $3^{r+1}.$ But, since powers of $2$ repeat every $2 \cdot 3^r$ iterations mod $3^{r+1}$ by Euler's Theorem, it follows that by the inductive hypothesis, $f(x+3^r) = 2^{f(x+3^r-1)}+2^{f(x+3^r-2)} + \cdots + 2^{f(x)} + f(x) \equiv f(x) + \left( 2^1+2^3+\cdots + 2^{2 \cdot 3^r-1} \right) \pmod {3^{r+1}}$ as $f(x)$ is always odd so by CRT $\{f(x+3^r-1), f(x+3^r-2), \cdots, f(x)\}$ is some permutation of the odd residues under mod $2\cdot 3^r.$ But $v_3 \left( 2^1+2^3+\cdots+2^{2\cdot 3^r-1} \right) = v_3 \left( 2 \cdot \frac{4^{3^r}-1}{3} \right) = 3^r+1-1=3^r$ by LTE. Therefore $f(x),f(x+3^r), f(x+2 \cdot 3^r)$ are indeed distinct modulo $3^{r+1},$ so our induction is complete. Now the result follows. QED

This post has been edited 1 time. Last edited by Maximilian113, Apr 1, 2025, 7:59 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

597 posts

cursed_tangent1434

#56 h Monday at 9:54 AM

Y by

Extremely long and patchy writeup. Threefold-induction does the trick. We show the more general claim that $f(1),f(2),\dots , f(3^n)$ leave distinct remainders when divided by $3^n$ . To do this we employ induction. The result is obvious when $n=1$ since $f(1)=1$ , $f(2)=3$ and $f(3)=11$ . Now say the result holds for some positive integer $n\ge 1$ and we shall show it for $n+1$ . First of all, note that $f(i)$ is odd for all positive integers $i$ by induction. Each claim proved below is considered to be the inductive step in a proof via induction, the base case $n=1$ being clear. We first show the following key claim.

Claim : For all positive integers $r$ , $f(r) \equiv f(3^n+r) \pmod{3^n}$ .

Proof : We approach this via induction on $r$ (within the master induction on $n$ ), dual inductive the claim (and equivalently $3^n \mid f(r)+f(r+1)+\dots +f(3^n+r-1)$ ) and the statement that $3^n \mid 2^{f(r)}+2^{f(r+1)}+\dots + 2^{f(3^n+r-1)}$ for all $r \in \mathbb{N}$ . The base cases are clear by the inductive hypothesis (of our master induction). Now, say the claim holds for some $r \ge 1$ we wish to show it holds for $r+1$ .

Note,
$\begin{align*} f(r+1)+\dots + f(3^n+r) & = f(r+1)+f(r+2)+\dots + f(3^n+r-1) + \\ &\left(f(r)+2^{f(r)}+2^{f(r+1)}+\dots +2^{f(3^n+r-1)}\right)\\ & \equiv f(r+1)+f(r+2)+\dots + f(3^n+r-1) + f(r) \pmod{3^n}\\ & \equiv 0 \pmod{3^n} \end{align*}$ As a corollary it follows that,
$f(r+1)+f(r+2)+\dots + f(3^n+r) \equiv f(r)+f(r+1)+\dots + f(3^n+r-1) \pmod{3^n}$ which implies $f(r) \equiv f(3^n+r) \pmod{3^n}$ as claimed. However, since $f(i)$ is odd for all $i \in \mathbb{N}$ by the Chinese Remainder Theorem it also follows that $f(r) \equiv f(3^n+r) \pmod{2\cdot 3^n}$ .

Completing the induction,
$\begin{align*} 2^{f(r+1)}+2^{f(r+2)}+\dots + 2^{f(3^n+r)} & \equiv 3\left(2^1+2^3 + \dots + 2^{2\cdot 3^n-1}\right)\\ & \equiv 6\left (1+2^2+\dots + 2^{2\cdot 3^n-2}\right)\\ &= 2(4^{3^n}-1)\\ &\equiv 0 \pmod {3^n} \end{align*}$ As $f(1),f(2),\dots , f(3^{n-1}$ are distinct $\pmod{2\cdot 3^{n-1}}$ and the inductive hypothesis (of the claim) for $n-1$ holds, and also by the Lifting the Exponent Lemma it follows that $\nu_3(4^{3^n}-1) = \nu_3(4-1)+\nu_3(3^n)=n+1 >n$ .

Thus, both claims of the induction have been verified completing the inductive step and proving the claim.

Before we proceed there are some minor observations we need to make.

Claim : For all non-negative integers $m$ ,
$\frac{4^{3^m}-1}{3} \equiv 3^{m} \pmod{3^{m+1}}$
Proof : Once again, we show the result using induction on $m$ . The base cases $m=0,1,2$ are quite easy to check. Now say the claim holds for $m \ge 2$ so we wish to show it for $m+1$ . By the Inductive hypothesis we can write,
$\frac{4^{3^m}-1}{3} = (3l+1)3^m$ for some positive integer $l$ . Now note,
$\begin{align*} \frac{4^{3^{m+1}}-1}{3} &= \frac{4^{3^m}-1}{3} \left(4^{2\cdot 3^m}+ 4^{3^m} + 1\right) \\ &= (3l+1)3^m \left(4^{2\cdot 3^m}+ 4^{3^m} + 1\right) \\ &= (3l+1)3^m\left((3^{m+1}l+3^m+1)^2 + (3^{m+1}l+3^m+1) + 1\right)\\ & \equiv 3^m(3l+1)(3\cdot 3^{m+1}l+3\cdot 3^m+3) \pmod{3^{m+2}}\\ & = 3^{m+1}(3l+1)(3^{m+1}l+3^m+1)\\ & \equiv 3^{m+1}(3^{m+1}l+3^m+1) \pmod{3^{m+2}}\\ & \equiv 3^{m+1} \pmod{3^{m+2}} \end{align*}$ which completes the induction and we are done.

Now comes the key result which allows us to complete the master induction.

Claim : For all positive integers $r$ in the range $1 \le r \le 3^n$ we have $f(3^n+r) \equiv 2\cdot 3^n+f(r) \pmod{3^{n+1}}$ .

Proof : With all our preceding claims in hand this is but a minor computation,
$\begin{align*} f(3^n+r) & = f(r)+2^{f(r)}+2^{f(r+1)}+ \dots + 2^{f(3^n+r-1)} \\ & \equiv f(r)+2^1 + 2^3 + \dots + 2^{2\cdot 3^n-1}\pmod{3^{n+1}}\\ & = f(r) + 2\left(1+2^2+\dots 2^{2\cdot 3^n-2}\right)\\ & = f(r) + \frac{2(4^{3^n}-1)}{3}\\ &\equiv f(r) + 2\cdot 3^n \pmod{3^{n+1}} \end{align*}$ since $f(r),f(r+1),\dots , f(3^n+r-1)$ are distinct $\pmod{2\cdot 3^{n}}$ by our first claim, and Euler's Generalization of Fermat's Little Theorem.

But this immediately completes the master induction since $f(1),f(2),\dots , f(3^n)$ are distinct $\pmod{3^n}$ and by the above claim, $f(r),f(3^n+r),f(2\cdot 3^n+r)$ are distinct $\pmod{3^{n+1}}$ for all $1 \le r \le 3^n$ which implies that $f(1),f(2),\dots , f(3^{n+1})$ are distinct $\pmod{3^{n+1}}$ as desired.

Z K Y