ϕ ( n ) / n \phi(n)/n

For a positive integer n n , let ϕ ( n ) \phi(n) denotes the Euler's totient function .

And let S k = n ϕ ( n ) n S_{k}=\displaystyle \sum_{n} \dfrac{\phi (n)}{n} , where n n runs through all positive divisors of 4 2 k 42^k . Find the largest positive integer k < 1000 k<1000 such that S k S_{k} is an integer.


The answer is 996.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

for a given k k , n = 2 α 3 β 7 γ n=2^{\alpha}3^{\beta}7^{\gamma} , for integer 0 α , β , γ k 0\leq \alpha,\beta,\gamma \leq k .

Then we can consider cases

1- 1 α , β , γ k 1\leq \alpha,\beta,\gamma \leq k

ϕ ( 2 α 3 β 7 γ ) 2 α 3 β 7 γ = 2 7 \frac{\phi(2^{\alpha}3^{\beta}7^{\gamma})}{2^{\alpha}3^{\beta}7^{\gamma}}=\frac{2}{7}

there is gonna be k 3 k^3 such numbers n = 2 α 3 β 7 γ n=2^{\alpha}3^{\beta}7^{\gamma}

2- exactly one of α , β , γ \alpha,\beta,\gamma is zero. If α = 0 \alpha=0

ϕ ( 3 β 7 γ ) 3 β 7 γ = 4 7 \frac{\phi(3^{\beta}7^{\gamma})}{3^{\beta}7^{\gamma}}=\frac{4}{7}

there is gonna be k 2 k^2 such numbers n = 2 α 3 β 7 γ n=2^{\alpha}3^{\beta}7^{\gamma}

similarly, if β = 0 \beta=0 or If γ = 0 \gamma=0 , the fraction would be 3 7 \frac{3}{7} and 1 3 \frac{1}{3} , respectively. Each would contain k 2 k^2 numbers n n .

3- exactly two of α , β , γ \alpha,\beta,\gamma are zero. If α 0 \alpha\neq 0

ϕ ( 2 α ) 2 α = 1 2 \frac{\phi(2^{\alpha})}{2^{\alpha}}=\frac{1}{2}

there is gonna be k k such numbers n = 2 α 3 β 7 γ n=2^{\alpha}3^{\beta}7^{\gamma}

similarly, ff β 0 \beta\neq 0 or If γ 0 \gamma\neq 0 , the fraction would be 2 3 \frac{2}{3} and 6 7 \frac{6}{7} , respectively. Again, each would contain k k numbers n n .

4- all three of α , β , γ \alpha,\beta,\gamma are zero.

ϕ ( 1 ) 1 = 1 \frac{\phi(1)}{1}=1

there would be a single number n = 1 n=1 in this case.

So, we form the summation again

2 7 k 3 + 28 21 k 2 + 85 42 k + 1 = 12 k 3 + 56 k 2 + 85 k 42 + 1 \frac{2}{7}k^3+\frac{28}{21}k^2+\frac{85}{42}k+1=\frac{12k^3+56k^2+85k}{42}+1

so we need to find the largest k < 1000 k<1000 ,for which 12 k 3 + 56 k 2 + 85 k 42 \frac{12k^3+56k^2+85k}{42} is an integer. From this point, I ran a program to find the largest k k , although an analytical approach seems to be easily achievable (rather cumbersome though). the largest would be k = 996 k=996

how did you say that k=996 at the last step?

Venkatesh A - 2 years, 5 months ago
Patrick Corn
Nov 27, 2018

The function g ( n ) = d n φ ( n ) n g(n) = \sum\limits_{d|n} \frac{\varphi(n)}{n} is multiplicative , so g ( 4 2 k ) = g ( 2 k ) g ( 3 k ) g ( 7 k ) . g(42^k) = g(2^k)g(3^k)g(7^k).

For any prime p p and nonnegative integer k , k, direct computation shows that g ( p k ) = 1 + k ( 1 1 / p ) . g(p^k) = 1 + k(1-1/p). So g ( 4 2 k ) = ( 1 + k 2 ) ( 1 + 2 k 3 ) ( 1 + 6 k 7 ) = ( k + 2 ) ( 2 k + 3 ) ( 6 k + 7 ) 42 . g(42^k) = \left( 1 + \frac{k}2 \right) \left( 1 + \frac{2k}3 \right) \left( 1 + \frac{6k}7 \right) = \frac{(k+2)(2k+3)(6k+7)}{42}. This is an integer if and only if the numerator is divisible by 2 , 3 , 2,3, and 7 , 7, which happens if and only if k 0 ( m o d 2 ) k 0 , 1 ( m o d 3 ) k 0 , 2 , 5 ( m o d 7 ) \begin{aligned} k &\equiv 0 \pmod 2 \\ k &\equiv 0,1 \pmod 3 \\ k &\equiv 0,2,5 \pmod 7 \end{aligned} By the Chinese remainder theorem , this is equivalent to k 0 , 12 , 16 , 28 , 30 , 40 ( m o d 42 ) k \equiv 0, 12, 16, 28, 30, 40 \pmod{42} and since 1000 34 ( m o d 42 ) , 1000 \equiv 34 \pmod{42}, the largest integer less than 1000 1000 that fits the requirements is 996 . \fbox{996}.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...