A continuation

Calculus Level 5

Above is the graph of y = n = 1 x gcd ( x , n ) \displaystyle y=\sum _{n=1}^x\gcd \left(x,n\right) .

As you can see, there is quite a number of points scattered along the line y = 2 x 1 y=2x-1 .

Within 0 x k 0 \le x \le k , let the number of points that lie on the line y = 2 x 1 y=2x-1 be D k D_{k}

Find lim k k D e k k \lim _{ k\rightarrow \infty }{ \sqrt [ k ]{ k{ D }_{ { e }^{ k } } } }


The answer is 2.71828.

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.

1 solution

Vijay Bhaskar
Jun 22, 2015

y = n = 1 x gcd ( x , n ) = gcd ( x , x ) + n = 1 x 1 gcd ( x , n ) = x + n = 1 x 1 gcd ( x , n ) y=\sum _{ n=1 }^{ x }{ \gcd{(x,n)} } = \gcd{(x,x)} + \sum _{ n=1 }^{ x -1}{ \gcd{(x,n)} } =x + \sum _{ n=1 }^{ x - 1 }{ \gcd{(x,n)} }

Note that y = 2 x 1 y = 2x-1 if x x is prime

Also note that if x x is composite, n = 1 x 1 gcd ( x , n ) \sum _{ n=1 }^{ x - 1 }{ \gcd{(x,n)} } is strictly greater than x 1 x -1 because there exists at least one 1 < n < x 1 < n < x such that g c d ( x , n ) > 1 gcd(x,n) > 1

Hence, the only points lying on y = 2 x 1 y = 2x -1 are points where x x is prime.

Hence, D e k = ( Number of primes e k ) D_{e^k} = (\text{Number of primes} \le e^k)

By Prime Number Theorem, its limiting value when k k and hence e k e^{k} tends to infinity is e k ln ( e k ) = e k k \frac{e^{k}}{\ln{(e^{k})}} = \frac{e^{k}}{k}

Hence, ( k D e k ) 1 / k = ( e k ) 1 / k = e (kD_{e^k})^{1/k} = (e^{k})^{1/k} = \boxed{e}

Moderator note:

Great approach!

I have edited your solution for LaTeX \LaTeX , mind if you check your solution for any errors that I may have made?

Julian Poon - 5 years, 11 months ago

Log in to reply

Thanks a lot for the edit!

Vijay Bhaskar - 5 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...