Coprime pairs

First, prime factorize $n$ as $n = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}.$ Then, using the formula for Euler's totient function $\phi(n),$ we have $n\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right) \cdots \left(1-\dfrac{1}{p_k}\right) = \dfrac{n}{3}.$ Dividing through by $n$ and manipulating the fractions, we have $\dfrac{(p_1-1)(p_2-1)\cdots(p_k-1)}{p_1p_2\cdots p_k} = \dfrac{1}{3}.$

Now we cross-multiply and get $3(p_1-1)(p_2-1)\cdots (p_k-1) = p_1p_2\cdots p_k.$ Note that the right side of this equation must be a multiple of $3,$ and because all the terms in the product are primes, one of the terms must be $3.$ Without loss of generality, let $p_1 = 3.$ Then we have $3(2)(p_2-1)\cdots(p_k-1) = 3p_2\cdots p_k$ $2(p_2-1)(p_3-1)\cdots(p_k-1) = p_2p_3\cdots p_k$

By a similar argument, one of the remaining primes on the right-hand side must be $2,$ so let $p_2 = 2.$ This becomes $2(1)(p_3-1)\cdots(p_k-1) = 2p_3\cdots p_k$ $(p_3-1)\cdots(p_k-1) = p_3\cdots p_k$ Now notice that all the terms on the left-hand side are smaller than the corresponding terms on the right-hand side, so if $n$ has more than $2$ prime factors, equality cannot hold. Hence, the prime factors of $n$ are only $2$ and $3.$

Thus, we need to find all integral values of $a$ and $b$ such that $a, b> 0$ and $n = 2^a3^b < 1000.$ Performing casework on $b$ :

• If $b = 1,$ then $a = 1, 2, \ldots, 8$ ;
• If $b = 2,$ then $a = 1, 2, \ldots, 6$ ;
• If $b = 3,$ then $a = 1, 2, \ldots, 5$ ;
• If $b = 4,$ then $a = 1, 2, 3$ ;
• If $b = 5,$ then $a = 1, 2.$

Therefore, there are $8 + 6 + 5 + 3 + 2 = \boxed{24}$ possible values of $n.$

It is clear that $3 \mid n$ . We wish to find all $n \in \mathbb{N}$ so that $\phi(n) = \frac{n}{3}$ . Writing $n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$ , we write $\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\ldots (1-\frac{1}{p_k})$ and adding the fact that $3 \mid n$ , WLOG $p_1 = 3$ . So we find that $\frac{n}{3} = \frac{2}{3}n (1 - \frac{1}{p_2})(1 - \frac{1}{p_3}) \ldots (1 - \frac{1}{p_k})$ or $(1 - \frac{1}{p_2})(1 - \frac{1}{p_3}) \ldots (1 - \frac{1}{p_k}) = \frac{1}{2}$

It must be the case that the only prime divisor of $n$ other than $3$ is $2$ , for if $n$ has any other prime divisor but $2$ , the denominator in $(1 - \frac{1}{p_2})(1 - \frac{1}{p_3}) \ldots (1 - \frac{1}{p_k})$ would be an odd number, whereas the nominator would be an even number, so it can't be simplified to $\frac{1}{2}$ . If $n$ has any other prime divisor other than $2$ , $(1 - \frac{1}{p_2})(1 - \frac{1}{p_3}) \ldots (1 - \frac{1}{p_k}) < \frac{1}{2}$ So $n = 2^s 3^t$ for $s, t$ positive integer. We see that there are $24$ integers of this form less than $1000$ .

To satisfy the condition, a number n, must be a product of 2^a and 3^b, where a and b are positive integers.

That n has to be a product of 3^b is obvious, since otherwise n/3 is not an integer.

If n is not a product of 2^a, that means that 2 is coprime to n, and since 3k+1 is also coprime to n=3m, if m>k for every k>=0, there are at least 3/n +1 integers coprime to n

If n is a product of 2^a, 3^b and another prime p, than n is coprime to n, and and since 3k+1 is also coprime to n=3m, if m>k for every k>=0, there are at least 3/n +1 integers coprime to n

Now we have to count the cases of a and b where n < 1000

For b=1, 1<=a<=8,

For b=2, 1<=a<=6,

For b=3, 1<=a<=5,

For b=4, 1<=a<=3,

For b=5, 1<=a<=2,

For b=6, there is no integer a to satisfy n < 1000.

There are 24 pairs of a and b, QED

The number of positive integers that are coprime to n, where the prime factorization of $n$ is $p_1^{k_1}*p_2^{k_2}*p_3^{k_3}...$ is $n*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*\frac{p_3-1}{p_3}...$ This means that $n*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*\frac{p_3-1}{p_3}...=\frac{n}{3}$ Let n only have 2 prime factors, 2 and 3. Therefore, $n*\frac{1}{2}*\frac{2}{3}$ should equal $\frac{n}{3}$ . It does, so we can check if there are any other prime numbers that satisfy this. There aren't any: Therefore, 2 and 3 are the only plausible prime factors: Now we will have to look for the combinations of 2 and 3 that are less than 1000. $2^8*3^1$ yields one solution

$2^7*3^1$ yields one solution

$2^6*3, 2^6*3^2$ yields 2 solutions

$2^5*3, 2^5*3^2, 2^5*3^3$ yields 3 solutions

$2^4*3, 2^4*3^2, 2^4*3^3$ yields 3 solutions

$2^3*3, 2^3*3^2, 2^3*3^3, 2^3*3^4$ yields 4 solutions

$2^2*3, 2^2*3^2, 2^2*3^3, 2^2*3^4, 2^2*3^5$ yields 5 solutions

$2*3, 2*3^2, 2*3^3, 2*3^4, 2*3^5$ yields 5 solutions

Now we have to sum them up: $1+1+2+3+3+4+5+5=\boxed{24}$

$\phi(n)= n\prod_{p|n} \left( 1- \frac{1}{p}\right)$ where $p$ is prime. $\phi(n) = \frac{n}{3}$ implies $\prod_{p|n} \left( 1- \frac{1}{p}\right) = \frac{1}{3}$ The left side has to provide the factor of 3 in its denominator, and as only prime numbers are allowed it must include $\left(1 - \frac{1}{3}\right) = \frac{2}{3}$ . Solving we may find the other prime $p = 2$ .

Then it must be true that $2|n$ and $3|n$ , in other words $n = 2^x3^y$ where $x,y \in \mathbb{Z}^{pos}$ . There are $24$ numbers of such form less than $1000$ .

This is simply equivalent to saying $\phi(n)=\dfrac{n}{3}$ , where if $p$ , $q$ , $r$ ... are the distinct prime factors of $n$ , then $\phi(n)=n\dfrac{p-1}{p}\cdot\dfrac{q-1}{q}\cdot\dfrac{r-1}{r}...=n\dfrac{(p-1)(q-1)(r-1)\cdots}{pqr\cdots}$ Since the denominator is 3, one of the prime factors must be 3. Now, we have $\dfrac{1}{3}=\dfrac{2}{3}\cdot\dfrac{(q-1)(r-1)\cdots}{qr\cdots}$ Therefore, $\dfrac{1}{2}=\dfrac{(q-1)(r-1)\cdots}{qr\cdots}$ By similar reasoning, one prime factor must be 2. Now, $1=\dfrac{(r-1)\cdots}{r\cdots}$ Clearly, the left is less than 1, so the only prime factors of $n$ must be 2 and 3. Now, we count. If the exponent on 3 is 1, there are 8 possibilities. As the exponent on 3 increases, we have 6,5,3,2 possibilities. The answer is $8+6+5+3+2=\boxed{24}$ .

ssuming that 1 is co-prime with every number, then the answer is 24 numbers:

6 12 18 24 36 48 54 72 96 108 144 162 192 216 288 324 384 432 486 576 648 768 864 972 total = 24

The number of positive integers less than $n$ which are coprime to $n$ , is
$\phi$ ( $n$ ) = $n$ .(1 - $\frac{1}{p_{1}}$ ).(1 - $\frac{1}{p_{2}}$ )...............(1 - $\frac{1}{p_{k}}$ ); where $p_{i}$ are the prime factors of $n$ , and $1 \leq i \leq k$
In this case, when $n$ = $0$ , then we are done; if not, then
$n$ .(1 - $\frac{1}{p_{1}}$ ).(1 - $\frac{1}{p_{2}}$ )...............(1 - $\frac{1}{p_{k}}$ ) = $\frac{n}{3}$
⇒( $\frac{p_{1} - 1}{p_{1}}$ ).( $\frac{p_{2} - 1}{p_{2}}$ ).( $\frac{p_{3} - 1}{p_{3}}$ )............( $\frac{p_{k} - 1}{p_{k}}$ ) = $\frac{1}{3}$ ..................(1) [ Note that, $n$ $\neq$ $0$ ]
Without loss of generality, let $p_{1} \leq p_{2} \leq p_{3} \leq.........\leq p_{k}$
We can easily see that, in the equation (1), the numerator of the R.H.S. is $1$ , so, all the numbers at the numerator of L.H.S. must be canceled out when dividing by the denumerator of the L.H.S.
Note that, all the denumerators of each fractions in the L.H.S. of equation (1), are prime numbers,
So, ( $p_{1}$ - 1) can not divide any denumerator and, $(p_{1} - 1) \leq p_{1} \leq p_{2} \leq.......\leq p_{k}$
So, among $p_{i}$ where $1 \leq i \leq k$ no prime can divide ( $p_{1}$ - 1) if we want to cancel ( $p_{1}$ - 1), the only possible case is
( $p_{1}$ - 1) = 1
⇒ $p_{1}$ = 2
But the denumerator of the R.H.S. of equation (1) is $3$ , so we have to cancel $2$ , which is only possible when, $p_{2}$ = 3
Now observe that, if there exist any other prime $p_{3}$ , then, the R.H.S. of equation (1) can not be $\frac{1}{3}$ .
So, all the numbers $n$ will be in the form $2^{\alpha_{1}}$ . $3^{\alpha_{2}}$
In this way, if we study all the cases, we shall find;
If $\alpha_{1}$ = 1, then there are 5 choices of $\alpha_{2}$
If $\alpha_{1}$ = 2, then there are 5 choices of $\alpha_{2}$
If $\alpha_{1}$ = 3, then there are 4 choices of $\alpha_{2}$
If $\alpha_{1}$ = 4, then there are 3 choices of $\alpha_{2}$
If $\alpha_{1}$ = 5, then there are 3 choices of $\alpha_{2}$
If $\alpha_{1}$ = 6, then there are 2 choices of $\alpha_{2}$
If $\alpha_{1}$ = 7, then there are 1 choices of $\alpha_{2}$
If $\alpha_{1}$ = 8, then there are 1 choices of $\alpha_{2}$
[ NOTE THAT, none of $\alpha_{1}$ and $\alpha_{2}$ can be $0$ and the highest value of $\alpha_{1}$ and $\alpha_{2}$ is respectively 8 and 5]
So, the total numer of $n$ is ( $5$ + $5$ + $4$ + $3$ + $3$ + $2$ + $1$ + $1$ ) = $24$ [ANSWER]

According to Euler's totient function, if $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ with $p_1,p_2,...,p_k$ are distinct prime numbers and $\phi(n)$ denotes the number of positive integers less than $n$ which are coprime to $n$ , then $\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$
By substituting $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ , we get $\phi(n)=p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_k^{\alpha_k-1}(p_1-1)(p_2-1)\dots (p_k-1)$
Since $\phi(n)=\frac{n}{3}$ , then $p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_k^{\alpha_k-1}(p_1-1)(p_2-1)\dots (p_k-1)=\frac{p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}}{3}$
Divide both sides with $p_1^{\alpha_1-1}p_2^{\alpha_2-1}\dots p_k^{\alpha_k-1}$ we get
$(p_1-1)(p_2-1)...(p_k-1)=\frac{p_1p_2...p_k}{3}$
$3(p_1-1)(p_2-1)...(p_k-1)=p_1p_2...p_k$
Since $3$ divides left hand side, then one of $p_1,p_2,...,p_k$ must be 3
Without loss of generalization, let $p_1=3$
$3(3-1)(p_2-1)...(p_k-1)=3p_2p_3...p_k$
$2(p_2-1)(p_3-1)...(p_k-1)=p_2p_3...p_k$
Since $2$ divides left hand side, then one of $p_2,...,p_k$ must be 2
Without loss of generalization, let $p_2=2$
$2(2-1)(p_3-1)...(p_k-1)=2p_3...p_k$
$(p_3-1)(p_4-1)...(p_k-1)=p_3...p_k$
If $k>2$ , the left hand side will be even, but the right hand side will be odd (the only even prime number is $2$ and $p_2=2$ )
That's a contradiction
Therefore $k=2$ which implies that $n$ only has $2$ prime factors(which are $2$ and $3$ )
Since the prime factors of $n$ are $2$ and $3$ , we can write $n=3^{\alpha_1}2^{\alpha_2}$
$n<1000$ implies that $3^{\alpha_1}<1000$ implies that $\alpha_1\leq6$
We divide this into 6 cases
Case 1: $\alpha_1=6$
$3^6\times 2^{\alpha_2}<1000 \rightarrow 2^{\alpha_2}<2$ which means there are no values of $\alpha_2$
Case 2: $\alpha_1=5$
$3^5\times 2^{\alpha_2}<1000 \rightarrow 2^{\alpha_2}\leq4$ which means the possible values of $\alpha_2$ are $1$ and $2$
Case 3: $\alpha_1=4$
$3^4\times 2^{\alpha_2}<1000 \rightarrow 2^{\alpha_2}\leq12$ which means the possible values of $\alpha_2$ are $1,2$ and $3$
Case 4: $\alpha_1=3$
$3^3\times 2^{\alpha_2}<1000 \rightarrow 2^{\alpha_2}\leq37$ which means the possible values of $\alpha_2$ are $1,2,3,4$ and $5$
Case 5: $\alpha_1=2$
$3^2\times 2^{\alpha_2}<1000 \rightarrow 2^{\alpha_2}\leq111$ which means the possible values of $\alpha_2$ are $1,2,3,4,5$ and $6$
Case 6: $\alpha_1=1$
$3^1\times 2^{\alpha_2}<1000 \rightarrow 2^{\alpha_2}\leq333$ which means the possible values of $\alpha_2$ are $1,2,3,4,5,6,7$ and $8$
From all the cases, we get there are $0+2+3+5+6+8=24$ values of $n$ satisfy the given property

Since I am not familiar with the totient function, I approached this a different way than many.

For a number with prime factorization N = p_1^n_1 p_2^n_2p_3^n_3 ... p_k^n_k (that is, a number N with k unique primes in its prime factorization), the numbers that are coprime to N are precisely those which contain no factors $p_1$ through $p_k$ . We can enumerate this through the group of "Integers modulo $\Pi p_k$ ".

To clarify my meaning: You can determine whether a number is coprime to 12 $(2*2*3)$ by determining if it is coprime to 6 $(2*3)$ . You can also determine whether a number is coprime to 540 $(2*2*3*3*3*5)$ by looking instead at whether it is coprime to 30 $(2*3*5)$ . Thus I investigated this problem by reasoning about the groups modulo the product of all unique primes in the prime factorization of the larger number.

Consider the integers modulo 6. Since 6 is 2*3, you can determine the coprimality of all integers of the form 2^n 3^m by their coprimality to 6. All numbers that are congruent to 1(mod6) and 5(mod6) are coprime to 6, so they are coprime to 2^n 3^m. All other numbers are congruent to 0, 2, 3, and 4 (mod6). This means that all numbers of the form 2^n 3^m satisfy the desired condition, as precisely 1/3 of numbers are congruent to 1 or 5(mod6).

Justifying the nonexistence of other solutions feels a little hazier to me, so I'd love for some comments on my approach:

Consider a modular group with an order O such that O = p*3 (p a prime). That is, the group of integers modulo 3p. (This would check be any case of the form 3^n p ^m for some prime p. We note we must include 3^n because 3 must divide our integer N.)

Now, the integers in Z(mod3p) that are NOT coprime to 3p are either multiples of 3 or multiples of p. There are p multiples of 3, and 3 multiples of p in a group of order 3p, and only 0 overlaps when p and 3 are coprime. This means there is (3 + p - 1) or (p + 2) noncoprime integers in the group, and 3p -(p+2) coprime integers. Simplifying, in a group of order 3p, 2p-2 of the integers are coprime to 3p. If we wish that (2p-2) = 1/3 (3p), this implies that 2p-2=p and thus p=2.

So if a modular group is of order 3p and needs 1/3 of its divisors coprime to itself, p must be 2.

I am not sure whether i can extend this process to groups of the order 3pq where both p and q are prime, but I feel as if I would need to extend this process inductively to capture the idea that for any other prime factors in the group order, the number of coprime integers is too large to satisfy the requirement that exactly 1/3 be coprime.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def gcd(a, b):
    if a < b:
        spam = a
    else:
        spam = b
    while spam > 0:
        if a%spam == 0 and b%spam == 0:
            return spam
        spam -= 1
    return 1 

spam = 0
for i in xrange(2, 1000):
    count = 0
    for j in xrange(1, i):
        if gcd(i,j) == 1:
            count += 1
    if count == i/3:
        spam += 1

print spam        

Answer: 24

Assuming that 1 is co-prime with every number, then the answer is 24 numbers:

6 12 18 24 36 48 54 72 96 108 144 162 192 216 288 324 384 432 486 576 648 768 864 972 total = 24

Here's the list with the coprimes listed for up to n = 144:

6: 1 5

12: 1 5 7 11

18: 1 5 7 11 13 17

24: 1 5 7 11 13 17 19 23

36: 1 5 7 11 13 17 19 23 25 29 31 35

48: 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47

54: 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53

72: 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71

96: 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95

108: 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 101 103 107

144: 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 101 103 107 109 113 115 119 121 125 127 131 133 137 139 143

n divided by 3, so I will check the set 3, 6, 9, ..., 990, 993, 996, 999. After few observations, I keep the set 6, 12, 18, 24, 30, ..., 990, 996 ( n divided by 6) ( 1 ). Numbers 30 and 42 are no solutions, so I suppose that "good" numbers will have the form (2^x) * (3^y). There are 24 numbers with this form in our set ( 1 ). This was an intuitive solution; I will study the theory for an accurate, scientific proof. Thank you very much for this challenge :)

$\varphi(n)=n \left(\frac{p_1-1}{p_1} \right) \left(\frac{p_2-1}{p_2} \right)... \left(\frac{p_n-1}{p_n} \right)=\frac{n}{3}$

Evidently $p_1=3$ , as there is a $3$ in the denominator on the RHS. Also, $p_=2$ to cancel with the $2=p_1-1$ in the numerator on the RHS. There cannot be any other primes in the prime factorisation of $n$ , as this would leave more primes that do not cancel in the denominator and numerator of $\varphi(n)$ . Thus $n=3^a2^b$ with $a,b>0, n<1000$ . Simple enumeration yields $24$ cases.

Denote Euler's totient function as $\phi(n)$ , then we need $3\phi(n) = n$ , i.e. $$3\prod {p \mid n} p^{e - 1}(p - 1) = \prod {p \mid n} p^e$$ which is $$3\prod {p \mid n }(p - 1) = \prod {p \mid n} p$$ Denote right side $\mathcal{R}$ and left side $\mathcal{L}$ . Then $3 \mid \mathcal{L}$ implies $3 \mid \mathcal{R}$ . Now we know $2 \mid \mathcal{L}$ and so $2 \mid \mathcal{R}$ . So $n$ must have prime factors $2,3$ . We also know that $n$ can't have any other prime factors, because we would have $4 \mid \mathcal{L}$ but $4 \nmid \mathcal{R}$ , which is a contradiction. On the other hand it is easy to check that any $n = 2^a \cdot 3^b$ , where $a,b \geq 1$ , satisfies the problem. We have $$\phi(2^a \cdot 3^b) = \phi(2^a) \cdot \phi(3^b) = 2^{a - 1} \cdot (2 - 1) \cdot 3^{b - 1}(3 - 1) = \frac{2^a \cdot 3^b}{3}$$ Now it's just case work, we need $n < 1000$ , so:

1) If $b = 1$ , then $a \leq 8$ .

2) If $b = 2$ , then $a \leq 6$ .

3) If $b = 3$ , then $a \leq 5$ .

4) If $b = 4$ , then $a \leq 3$ .

5) If $b = 5$ , then $a \leq 2$ .

6) If $b \geq 6$ , then $a \in \emptyset$ .

Hence the number of sought positive integers is $$8 + 6 + 5 + 3 + 2 = \boxed{24}$$

We want the Euler totient function $\phi(n)$ to have the value $n / 3$ : $\phi(n) = n\Pi_k (1 - \frac{1}{p_k} ) = \frac{n}{3 } \implies \Pi_k (1 - \frac{1}{p_k}) = 1/3.$ By inspection, only case we can get 1/3 is by the product $(1 - \frac{1}{2}) (1 - \frac{1}{3}) = \frac{1}{2} \times \frac{2}{3} = \frac{1}{3}.$

With the given criterion, numbers must have the prime factorization of the form $n = 2^{k_1}3^{k_2},$ with both $k_1, k_2 \ne 0$ . It is easily seen that for $k_2=1$ , $1 \le k_1 \le 8$ ; for $k_2=2$ , $1 \le k_1 \le 6$ ; and so on, For $k_{2\rm{max}} = 5$ , $k_1 = 1,2$ .

Adding them gives 8+6+5+3+2 = 24.

The number of positive integers less than $n$ which are coprime to $n$ is given by Euler's totient function $\varphi(n)$ . We can find this using Euler's product formula, which states that $\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$ where the product is over the distinct prime numbers dividing $n$ . So we want to find all $n$ such that $\prod_{p\mid n} \left(1-\frac{1}{p}\right) = \frac{1}{3}$ . Now, assuming that $p_1< p_2 < ... < p_k$ are the primes dividing $n$ , the equation becomes $\frac{(p_1-1)(p_2-1)...(p_k-1)}{p_1p_2...p_k} = \frac{1}{3}$ , which can be rearranged to give $3(p_1-1)(p_2-1)...(p_k-1) = p_1p_2...p_k$ . Since $p_k$ is prime and $p_k$ is the larger than each of $(p_1-1), (p_2-1), ... , (p_k-1)$ , then $p_k$ does not divide any of $(p_1-1), (p_2-1), ... , (p_k-1)$ , so $p_k$ must divide $3$ . Then $p_k = 3$ since $p_k$ is prime. $2$ is the only prime smaller than $3$ , so we have $p_1 = 3$ or $p_1 = 2, p_2 = 3$ . We can substitute this back into the equation to find that only the second case works. Thus, we want all positive integers which have $2$ and $3$ as their prime factors and have no other prime factors.

This corresponds to all positive integers which are of the form $2^x3^y$ , where $x,y$ are (strictly) positive integers. We want $2^x3^y < 1000$ , so $3^y < \frac{1000}{2^x} \leq \frac{1000}{2^1} \leq 500$ . Thus $y \leq 5$ . We count each case separately.

$y=1: 2^x < \frac{1000}{3} (\approx 333.3) \Rightarrow x \leq 8 \\ y=2: 2^x < \frac{1000}{9} (\approx 111.1) \Rightarrow x \leq 6 \\ y=3: 2^x < \frac{1000}{27} (\approx 37.0) \Rightarrow x \leq 5 \\ y=4: 2^x < \frac{1000}{81} (\approx 12.3) \Rightarrow x \leq 3 \\ y=5: 2^x < \frac{1000}{243} (\approx 4.1) \Rightarrow x \leq 2$

Therefore, our answer is $8 + 6 + 5 + 3 + 2 = \boxed{24}$ .

1)every number has got unique prime factorization. given numbers less than n and coprimes to it are n/3. so n is a multiple of 3. let's say n=2^a1 * 3^a2 * 5^a3.... where a2>=1; then numbers less than n and coprimes to it are given by euler totient function pi(n)=2^a1 * 3^a2 * 5^a3...(1-1/2) (1-1/3) (1-1/5) .... pi(n)=2^(a1)3^(a2-1) 5^(a3-1) (some other remaining numbers here concentrate on primes and their powers) now, n/3=2^a1 3^(a2-1)*5(a3)..... given pi(n)=n/3. so powers of primes should be equal ie we can equal only powers of 2 and 3 and we cannot include 5 or any other prime number so number is of the form 2^a1 * 3^a2 where a2 >=1 and a1>=1

$\phi (n) = n\prod_{p|n}\frac{p-1}{p} = \frac{n}{3} \to \frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\frac{p_3-1}{p_3} \dots = \frac{1}{3}$ , if $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots$ . Since the denominator is $3$ , which is a prime, we know that $p_1 = 3$ (without loss of generality). This gives the product to be $\frac{3-1}{3}\frac{p_2-1}{p_2}\frac{p_3-1}{p_3} \dots = \frac{2}{3}\frac{p_2-1}{p_2}\frac{p_3-1}{p_3} \dots = \frac{1}{3}$ . The $2$ in the numerator must cancel, so $p_2 = 2$ : $\frac{2}{3} \frac{2-1}{2} \frac{p_3-1}{p_3} \dots = \frac{1}{3} \frac{p_3-1}{p_3} \dots = \frac{1}{3} \to \frac{p_3-1}{p_3} \frac{p_4-1}{p_4} \dots = 1$ .

We thus know that $n=2^a3^bc$ , so we can say that, since $c=p_3^{a_3}p_4^{a_4}\dots$ and $\frac{p_3-1}{p_3} \frac{p_4-1}{p_4} \dots = 1$ , $\phi (c) = c$ . This cannot happen since there are only $c$ positive integers $1 \le p \le c$ and $c | c$ , i.e., $\phi (c) \le c-1$ except in the case of $c=1$ . Thus, $c=1$ .

So now we only need to find the number of $1\le n \le 1000 : n = 2^a3^b$ for some $a,b \ge 1$ . To do this, we can numerically evaluate the sum $\sum_{b=1}^{\lfloor \log_3(1000)-1 \rfloor} \lfloor \log_2 \lfloor \frac{1000}{3^b} \rfloor \rfloor = \boxed{24}$

A little manipulation of Euler's totient function tells us that since $\frac{\phi(n)}{n} = \frac{1}{3}$ ,so 3 must be a factor of n, for 3 to be in denominator. Again this causes 2 to be in the numerator,which can be meted out if 2 is also a factor. Finally $n = 6 * 2^a * 3^b$ for non-negative integers a & b. Count it manually for a=1,2,.. & so on. You will get 24 values for n.

From the formula of the Euler's totient function, $\varphi(n) = n\prod_{p\mid n} \big(1-\frac{1}{p}\big)$ , we have $\prod_{p\mid n} \big(1-\frac{1}{p}\big) = \frac{1}{3}.$ This means $3$ must be a prime factor of $n$ and one of the factor in the product becomes $1-\frac{1}{3} = \frac{2}{3}$ . This implies that $2$ is a factor of $n$ . Now two factors of the product are $1-\frac{1}{2}$ and $1-\frac{1}{3}$ and their product is $\big(1-\frac{1}{2}\big)\big(1-\frac{1}{3}\big) = 1$ . This implies that all prime factors of $n$ are $2$ and $3$ . Let $n = 2^{i} 3^{j}$ where $i$ and $j$ are positive integers. Then by the formula of the Euler's totient function, we see that $\varphi(n) = \frac{n}{3}.$ Hence a positive integer $n$ satisfies $\varphi(n) = \frac{n}{3}$ if and only if $n = 2^{i} 3^{j}$ for some positive integers $i$ and $j$ .

To answer the question, we count the number of positive integers of the form $n=2^i 3^j$ in $[1,999]$ which turns out to be $24$ .

By recalling Euler's Phi function, we find how many numbers less than n are coprime to it.

$\phi (n) = p_1^{r_1-1}p_2^{r_2-1}...p_k^{r_k-1}(p_1-1)(p_2-1)...(p_k-1)$ . Where $p_1^{r_1}p_2^{r_2}...p_k^{r_k}$ is the prime factorization of n.

Thus, the problem states:

$p_1^{r_1-1}p_2^{r_2-1}...p_k^{r_k-1}(p_1-1)(p_2-1)...(p_k-1) = ( \frac{1}{3})(p_1^{r_1}p_2^{r_2}...p_k^{r_k})$

$\implies (p_1-1)(p_2-1)...(p_k-1) = \frac{1}{3}(p_1p_2...p_k)$ , with RHS being the unique prime factors of n.

For the answer to be an integer, 3 must be a prime factor of n. Then, by LHS, 2 must also be a factor. And, $p_1=2, p_2=3$ .

Thus, $2(p_3-1)(p_4-1)...(p_k-1) = 2(p_3p_4...p_k)$

$\implies (p_3-1)(p_4-1)...(p_k-1) = p_3p_4...p_k$ .

But, $p_i > p_i-1, \forall i \ge 3$ . Then,

$(p_3-1)(p_4-1)...(p_k-1) \lt p_3p_4...p_k$ . Equality is never attained.

The answer is made up of all the numbers of the form $2^{i}3^{j} \lt 1000$ with $i, j \ge 1$ .

The numbers that fit the restriction are:

$6, 12, 24, 48, 96, 192, 384, 768, 18, 36, 72, 144,$

$288, 576, 54, 108, 216, 432, 864, 162, 324, 648, 486, 972$ .

The answer is $24$ .

By Euler totient's totient function we get that: $n \prod_{p|n} (1 - \frac{1}{p}) = \frac{n}{3} \Rightarrow \prod_{p|n} (1 - \frac{1}{p}) = \frac{1}{3}$ For this to happen the only prime in the denominator after cancellation must be 3, which can only occur if $2|n$ . No other $p_{i}$ can divide $n$ because for that to happen it has to be cancelled by a $p_{j} - 1 \Rightarrow p_{j} = p_{i} + 1$ . This only occurs for $2$ and $3$ .

Checking case by case for numbers multiples of only $2$ and $3$ that are less than $1000$ we see that there are 24 solutions.

Given $n$ , the number of positive integers less than $n$ that are coprime to $n$ is denoted $\varphi(n)$ . It is well known that

$\varphi(n)$ = n\Prod_{p|n}(1-1/p)).

Here the product is taken over all the prime divisors of $n$ .

To make that factor equal a third, we need to have both 2 and 3 as prime factors and nothing else. Let's prove this carefully: first, 3 must obviously be a prime divisor of $n$ since otherwise $n/3$ would not even be an integer. Now, Let $p$ be the largest prime divisor of $n$ . Then the product in the formula above will contain the factor $\frac{p-1}{p}$ . That $p$ in the denominator cannot be canceled by anything in the enumerator since $q-1<p$ for any other prime divisor $q$ of $n$ . Since we need that product to be 1/3, the largest prime must be 3 itself.

Finally, 2 must also be a prime divisor since otherwise our product comes out 2/3 instead of 1/3.

This the number $n$ must have the form $2^a3^b$ where $a,b > 0$ . To count these numbers up to 1000 we can simply enumerate the various possibilities for $b$ (they are 1...5 since $2\times 3^6$ is too large) and for each one find the largest possible power of 2.

We find two possibilities for $3^5$ , three for $(3^4$ , etc. for a total of 24.