The 2N Relation

Consider the ternary representation of $n$ and $f(n)$ . Note that appending a $0,1,2$ to the back of the ternary representation of $n$ gives us the ternary representations of $3n, 3n+1, 3n+2$ respectively. From the recurrence, appending a $0,2,1$ to the back of the ternary representation of $f(n)$ gives us the ternary representations of $f(3n), f(3n+1), f(3n+2)$ respectively. Hence, when we append a $1$ to the ternary representation of $n$ , we append a $2$ to the ternary representation of $f(n)$ and vice versa. Therefore, in addition to the base cases, we can conclude that $f(n)$ represents the value when we take the ternary representation of $n$ and replace all the $1$ s with $2$ 's and $2$ 's with $1$ 's.

Let $S_0,S_1,S_2$ be the sums of powers of $3$ represented by the digits $0,1,2$ respectively in the ternary representation of $n$ , hence $n=0 \times S_0 + 1 \times S_1 + 2 \times S_2$ and $f(n) = 0 \times S_0 + 2 \times S_1 + 1 \times S_2$ . $f(N)=2N \Rightarrow 2S_1 + S_2 = 2S_1 + 4S_2$ so it must be that $S_2=0$ , which means that the ternary representation of $N$ contains only $0$ 's and $1$ 's.

Note that there is a bijection between the solutions of $f(N)=2N$ and the list of positive integers as the ternary representation of the former list looks exactly the same as the binary representation of the latter list. The ternary representation of $1000=729+243+27+1=3^6+3^5+3^3+3^0$ is $1101001$ which is also the binary representation of $2^6+2^5+2^3+2^0=105$ so $1000$ must be the $105$ th solution since $105$ is the $105$ th positive integer and there are thus $105$ solutions $\leq 1000$

Lemma: If x is expressed in base 3, then $f(x)$ is just $x$ in base 3 with 1's and 2's transposed. [Note: What he means is that $f(102102_3) = 201201_3$ . Replace each occurrence of 1 with a 2, and vice versa.]

Proof: By a quick induction, on each of the cases, we are done.

Thus $f(n)$ can only equal to $2n$ if all of its digits in base 3 are 0's or 1's. 1000 is 1101001 in base 3. If n has 7 digits in base 3 and begins with 11, then it must be 1101001, 1101000, 1100111, 1100110, 1100101, 1100100, 1100011, 1100010, 1100001, or 1100000 If n has 7 digits and begins with 10, then there are 32 possibilities. If n has 6 digits, there are 32 possibilities for n. If n has 5 digits, there are 16 possibilities for n. If n has 4 digits, there are 8 possibilities for n. If n has 3 digits, there are 4 possibilities for n. If n has 2 digits, there are 2 possibilities for n. If n has 1 digits, there is 1 possibility for n. Summing these up, we have 105 total n <= 1000 that satisfy f(n) = 2n.

For simplicity, we let $f(0) = 0$ . Note that the 5 equations in the question will still hold (except the condition of f being a function from the positive integers to the positive integers).

We first prove that $f(n) \leq 2n$ for all n, with equality if and only if n is in the form $3m$ or $3m + 1$ and $f(m) = 2m$ . Note that $f(0) = 0 = 2 \cdot 0$ , $f(1) = 2 = 2 \cdot 1$ and $f(2) = 1 < 2 \cdot 2$ . So, our claim is true for n = 0, 1 and 2. Now assume our claim is true for all $n < 3k$ , where k is a positive integer. Then $f(3k) = 3f(k) \leq 6k = 2 \cdot 3k$ , with equality if and only if $f(k) = 2k$ . Similarly, we have $f(3k+1) = 3f(k) + 2 \leq 6k + 2 = 2 \cdot (3k+1)$ , with equality if and only if $f(k) = 2k$ , as well as $f(3k+2) = 3f(k) + 1 \leq 6k + 1 < 2 \cdot (3k+2)$ . Thus, our claim is also true for all $n < 3(k+1)$ . By mathematical induction, our claim is true for all n.

So which integers satisfy this condition? The easiest way to do this is to express each integer in base 3. All integers with only 0s or 1s in their base-3 representation would satisfy this condition, while any integer with at least one "2" in its base-3 representation will not.

Since $1000_{10 }= 1101001_3$ , all integers with at most 6 digits in their base-3 representation and with all digits being 0 or 1 (except for 0) will satisfy the criteria in the question. There are $2^6 - 1 = 63$ of such integers. Any integer with 7 digits in their base-3 representation must satisfy one of the following (mutually exclusive) criteria so that they are not more than 1000 and have the property $f(N) = 2N$ :

(i) The base-3 representation starts with "10" and all other digits are either "0" or "1". There are $2^5 = 32$ integers in this category.

(ii) The base-3 representation starts with "1100" and all other digits are either "0" or "1". There are $2^3 = 8$ integers in this category.

(iii) The base-3 representation starts with "110100" and the last digit is either "0" or "1". There are $2^1 = 2$ integers in this category.

So, there are a total of $63 + 32 + 8 + 2 = 105$ such integers.

First, let us extend the definition of $f(n)$ by defining $f(0)$ . Given the original definition of the function, it would not hurt us if we let $f(0)=0$ since it satisfies all the given conditions.

Given this definition of $f(0)$ , we can say that:

$f(3n)=3f(n)+f(0)$

$f(3n+1)=3f(n)+f(1)$

$f(3n+2)=3f(n)+f(2)$

Second, let us rewrite the integer $N$ into its ternary (i.e. base- $3$ ) notation. Let this be $(x_6x_5x_4x_3x_2x_1x_0)_3$ . Note that $N$ can only have at most seven digits in its ternary representation because it is less than or equal to $1000=1101001_3$ .

Thus, $N=\displaystyle\sum_{n=0}^{6} 3^nx_n$ .

Given this,

$f(N)=f\left(\displaystyle\sum_{n=0}^{6} 3^nx_n\right)=3f\left(\displaystyle\sum_{n=1}^{6} 3^{n-1}x_n\right)+f(x_0)$

$=3f\left(\displaystyle\sum_{n=2}^{6} 3^{n-2}x_n\right)+3f(x_1)+f(x_0)$

$=3f\left(\displaystyle\sum_{n=3}^{6} 3^{n-3}x_n\right)+9f(x_2)+3f(x_1)+f(x_0)$

and so on...

Thus, $f(N)=\displaystyle\sum_{n=0}^6 3^nf(x_n)$ .

Given this, the problem is asking for us to count all $N$ 's such that:

$f(N)=\displaystyle\sum_{n=0}^6 3^nf(x_n)=2\displaystyle\sum_{n=0}^6 3^nx_n=2N$ .

The equation will be satisfied if $f(x_n)=2x_n \forall n$ , which will only happen if $x_n=\{0,1\}$ .

Thus, we have to find all integers $N \leq 1000$ whose ternary notation only contains $1$ 's and $0$ 's.

This is equal to $2^7-(1111111_2-1000_{10})=$ $128-(1111111_2-1101001_2)=$ $128-10110_2=$ $128-23=105$ .

Let a positive integers $n$ be 'good' if $n \leq 1000$ and $f(n) = 2n$ . Notice that if $n$ is good, then $f(3n) = 6n$ and $f(3n+1) = 6n + 2$ which means if $n$ is good, then $3n$ and $3n+1$ is good. Other case can also be check that they are not good.

Case 1: $n$ is not good, then $f(3n) \neq 6n$ , $f(3n+1) \neq 6n+2$ and $f(3n+2) \neq 6n+4$ .

Case 2: $n$ is good, then $f(3n+2) \neq 6n+4$ .

So, if $n$ is good, then only $3n$ and $3n+1$ is good. We start at our first good number (1) which 'produce' two good numbers (3, 4) which produce four good numbers (9, 10, 12, 13)...... Notice the it is exactly the power of two! So, we can draw a tree-like diagram with (1) be the first row, (3, 4) be the second row.... Consider the last number of each row, notice that $1 \rightarrow 4 \rightarrow 13 \rightarrow 40 \rightarrow 121 \rightarrow 364 \rightarrow 1092$ . Thus good numbers stop at 7 row. Notice that $37 \rightarrow 111 \rightarrow 333 \rightarrow (999, 1000)$ . There are 2 number on the right of 37(4th row), thus 5 numbers on the right of 111(5th row), 11 numbers on the right of 333(6th row) and 22 numbers on the right of 1000(7th row). Thus, our ans is $2^0 + 2^1 + 2^2 +2^3 +2^4 + 2^5 + (2^6-22) =$

$1+2+4+8+16+32+(64-22) =$

$105$ .

HERE f(1)=2,f(3n)=3f(n),f(3n+1)=3f(n)+2 ARE THE EQUATIONS CONTRIBUTING f(N)=2N, N=1 IS THE FIRST CASE,FROM THAT APPLYING THE ABOVE EQUATIONS WE GET N=3 ,N=4 TAKE THESE TWO VALUES AS LEVEL 2, LEVEL 3 GIVES 9,10,12,13 (4 VALUES). LEVEL 4 GIVES 27,28,30,31,36,37,39,40 (8 VALUES). LEVEL 5 GIVES 81,82,84,85,90.91,93,94,108,109,111,112,117,118,120,121 (16 VALUES) LEVEL 6 GIVES 243,244,246,247,252,253,255,256,270,271,273,274,279,280,282,283,324,325,327,328,333,334,336,337,351,352,356,357,360,361,363,364 (32 VALUES). 333 2+1=1000 , SO WE HAVE TO CONSIDER UP TO 333 FOR LEVEL 7, SO THE NUMBERS LESS THAN 1000 SATISFYING THE CONDITION f(N)=2N WILL BE =1+2+4+8+16+32+(21 2)=105

Correct and well written

Seeing as this problem has a lot of 3's in it, consider the problem in base 3: Let $x=\overline{a_1 a_2 a_3 ... a_k}$ base 3. I claim that $f(x)=2x$ iff $a_i \neq 2$ for all i (It is given, since x is positive, that not all the $a_i$ are 0). We proceed by induction on the number of digits, k. If k=1, then either $x=1$ or $2$ , which by the given values must satisfy $f(1)=2*1$ and $f(2) \neq 2*2$ . So our base case is done. Now, let this be true for k=some number, say t. Then consider $x=\overline{a_1 a_2 ... a_{t+1}}$ . For later simplicity, let $x'=\overline{a_1 ... a_t}$ . By the givens of the problem, if $a_{t+1}=0$ , we must have $f(x)=10f(x')$ (remember, 10 base 3 = 3 base 10. The numbers I will be writing, remember, will all be in base 3). In other words, $f(x)=f(x')$ with a 0 appended to the end. So if $f(x)=2x$ , then $f(x')=2x'$ by simply dividing by 10. By the induction hypothesis, this is only true if x' is composed of only 0's and 1's, so by appending a 0 to the end, we see that x is composed of only 0's and 1's, with a 0 at the end. We are halfway done: If x ends in 0 and satisfies my conditions, then we must have $f(x)=2x$ , and if x ends in 0 and doesn't satisfy my conditions, $f(x) \neq 2x$ . We can use similar logic to see that if $a_{t+1}=1$ , then $f(x)=10f(x')+2$ . By before, since x-1 must end in 0, $f(x-1)=2(x-1)=10f(x')$ , so $f(x)=10f(x')+2=2x-2+2=2x$ . Thus my proposition is true for the x ends in 1 case, too. Finally, if $a_{t+1}=2$ , then $f(x)=10f(x')+1$ . Since x-1 ends in 1, $f(x-1)=2(x-1)=10f(x')+2$ , so $f(x)=10f(x')+2-1=2x-2-1=2x-3$ . But $2x-3 \neq 2x$ for any x, so $f(x)=2x$ does not hold if x ends in 2. To summarize: if x' satisfies my conditions, the $f(x)=2x$ holds iff x ends in 0 or 1. This is equivalent to what I wanted to show. Going back into decimal, there are many ways to go from here to show that there are 105 satisfying values. All require simply finding what 1000 base 10 is in base 3. It is 1101001. Now, here is what I think is the coolest way from here to get to the solution: Simply note that every satisfying number in base 3 can also be expressed as some number in base 2. Therefore all satisfying numbers less than or equal to 1000 are the same as all numbers less than or equal to what the base 3 1000 is in base 2. Basically, we need the number of positive integers less than or equal to $1101001_2$ . But this is simply the number itself, so the answer is $1101001_2=105_10$ .

"... must also have f (n) =2n+1, but this is iimpossible." Why impossible? Similarly, no details are given regarding ternary representation or the number of integers.

First, consider what happens if we have an $n$ so that $f(n)=2n$ .

$f(n)=2n$

$f(3n)=3f(n)=3(2n)=2(3n)$

Therefore, if a number $n$ satisfies the condition, then so does $3n$ .

Also, if $f(n)=2n$ ,

$f(3n+1)=3f(n)+2=3(2n)+2=2(3n+1)$

Therefore, if if a number $n$ satisfies the condition, then so does $3n+1$ .

Applying this same logic to $f(3n+2)$ yields that $f(n)=2n$ implies that $f(3n+2)\neq 6n+4$ , though.

We thus need to find the list of numbers where for each term $n$ , $3n$ and $3n+1$ also appear in the list. Considering all of our numbers in base 3, we have a simple relation. For all numbers $n$ , we get $3n$ by adding a 0 to the end of the number, and we get $3n+1$ by adding a 1 to the end of the number. Since 1 is the first number on this list (since $f(1)=2$ ), all numbers on this list are every single binary string written in base 2, but read in base 3. Since $1000=1101001_3$ , we reread this in binary, which is $1101001_2=105$ . Therefore, there are 105 binary strings, which means that there are $\boxed{105}$ numbers $N$ such that $f(N)=2N$ .

For some n and a, let f(n)=2n-a, then f(3n)=6n-3a, f(3n+1)=6n-3a+2, and f(3n+2)=6n-3a+1. If f(3n)=6n, then a=0,f(n)=2n, likewise for f(3n+1), while no value of a allows F(3n+2) to be an integer, as a>=0 for all values of n, and thus f(3n+2)<=6n+1<2(3n+2). With this we can see that every value of f(n) such that f(n)=2n generates 2 more such values. f(1) generates 2 values, 3 and 4, which each generate two values, for a total of 7 from 1 to 13. Ignoring the 13, we find that from 1-12 we generate a total of 12 such solutions from 1 to 37, and adding in the 13 gives 13 solutions. Continuing in this manner, we get a total of 105.

Let i try and compute some values that the function first:

ƒ(1) = 2 ƒ(2) = 1 ƒ(3) = 3*2 = 6 ƒ(4) = 8 etc but unfortunately the numbers look very random and there doesn’t seem to be an algebraic, It seems like the function satisfies condition that if ƒ(x) = y then ƒ(y) = x, beside that The expressions 3n,3n+1,3n+2,are suggesting us to consider the problem in base 3,

Let us see what we obtain if we express all numbers in base 3 for the previous values:

ƒ(1) = 2 ƒ(2) = 1 ƒ(10₃ ) = 20₃ ƒ(11₃) = 22₃

etc

Upon conversion an obvious pattern arises. It seems like the function merely transforms all digit 1s into 2s and all digit 2s into 1s

so far we have N = 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112, 117, 118, 120, 121, 243,...,1000, with this property, we know that ƒ(n) = 2n ,and From the all number N we know there are 105 positive integers satisfy with that conditions

Pattern Recognation

f(1) = 2, f(2) = 1, f(3) = 3 f(1) = 6, f(4) = 3 f(1) + 2 = 8, f(5) = 3*f(1) + 1 = 7.

We have N = 1, 3, 4 such that f(N) = 2*N.

for N = 3^(k+1) for k >= 2 I have f(N) = f(3^(k+1)) = f(3 3^k) = 3 f(3^k) = 3 3 f(3^(k-1)) = 3^k * f(3) = 3^k * 3 2 = 3^(k+1) * 2 = 2 N.

for N = 3^(k+1) + 1 for k >= 1 I havef(N) = f(3^(k+1) + 1) = 3 f(3^k) + 2 = 3^k * f(3) + 2 = 3^k * 3 2 + 2 =2 (3^(k+1) + 1) = 2 N.

Next, for any N such that f(N) = 2 N, I have f(3 N) = 3 f(N) = 3 2 N = 2 (3*N).

Just make a pattern

f(1), f(3), f(4),f(9), f(10), f(15), f(16), f(21), f(22), f(27), f(28),and so on..

Just look at the trend.

Note that each line starts with a power of 3, and that each line has twice the number of values as the previous line. Now 3^6 = 729

In the first two numbers one satisfies. The first two will lead to next 6 (from f(3) to f(8)) out of which 2 cases (f(3), f(4)) satisfies. These 6 leads to next 18 out of which 2x2=4 satisfies ... next 54 - 8, next 162 - 16, next 486 - 32.

From the first 6 lines we have 1 + 2 + 4 + 8 + 16 + 32 = 63 values of N.

so the last line of values N such that f(N) = 2*N will start with 729 and end with 1093, but we need N <= 1000 so we will have factor that restriction into our tally.

On the 7th line we can only go up to 1000,

which is 'rooted' in 111 on the 5th line and 333 on the 6th line. 111 is the 11th number on the 5th line, so 333 will be the 22nd number on the 6th line, and so 999 will be the 42th number on the 7th line.

and the 63 + 42 = 105 number N such that N <= 1000 and f(N) = 2*N.

So there are 105 positive integers N <= 1000 such that f(N) = 2*N.

From the question, it suggests that we should work in base 3. We can check that $f( 1_3) =f(1)= 2_3$ , $f(2_3) = f(2) = 1_3$ , $f(10_3) = f(3) = 3 f(1) = 6 = 20_3$ , $f(11_3)=f(4) = 3f(1)+2 = 8 = 22_3$ , $f(12_3) = f(5) = 3f(1)+1 = 7 = 21_3$ , $f(20_3) = f(6) = 3f(2)= 3 = 10_3$ , $f(21_3) = f(7) = 3f(2)+2 = 5 = 12_3$ , $f(22_3)=f(8)=3f(2)+1 = 4 = 11_3$ . The pattern is that, to calculate $f(N)$ , we write $N$ in base 3 notation, and then swap each digit of 1 with 2 (and vice versa). This can easily be shown by Induction on the number of digits in base 3 notation.

As such, $f(N)=2N$ if and only if $N$ consists of 1's and 0's in base 3 notation. Since $1000 = 1101001_3$ , there are $2^6$ possible $N$ from 1 to 729, $2^5$ possible $N$ from 730 to 972, $2^3$ possible $N$ from 973 to 999, $2^0$ possible $N$ from 1000 to 1000. Hence, there are $2^6 + 2^5 + 2^3 + 1 = 105$ solutions.

Basic implementation by C++: n=1000; for (int i=1;i<=n;++i) { if (i<=2) f[i]=3-i; else { if (i%3==0) f[i]=3 f[i/3]; else f[i]=3 f[i/3]+3-i%3; } if (f[i]==2*i) cout << i << endl; }

The complexity is O(n) where n=1000.

So, f(3)=6 ,f(4)=8, I have N =1,3,4 such that f(N)=2N I find out more then I find the pattern f(1), f(3) ,f(4), f(9), f(10), f(15), f(16),............. and so on.... 1,3,4,9,10,15,16,,.......................................................................................................................................................................999 and count the integers and got 105 answer