ϕ ( n ) + 2 n − 1 = \phi(n) + 2^n-1 = Monster

Number Theory Level 4

Evaluate the following sum: ∑ n = 1 ∞ ϕ ( n ) 2 n − 1 \sum_{n=1}^\infty \frac{\phi(n)}{2^n-1}

Notation: ϕ ( ⋅ ) \phi(\cdot) denotes the Euler's totient function .


The answer is 2.

ChengYiin Ong by ChengYiin Ong , 17, Malaysia

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

Chew-Seong Cheong
Jul 11, 2020

∑ n = 1 ∞ ϕ ( n ) 2 n − 1 = ∑ n = 1 ∞ ϕ ( n ) ( 1 2 ) n 1 − ( 1 2 ) n By Lambert series = 1 2 ( 1 − 1 2 ) 2 = 2 \begin{aligned} \sum_{n=1}^\infty \frac {\phi (n)}{2^n-1} & = \sum_{n=1}^\infty \frac {\phi (n) \left(\frac 12\right)^n}{1- \left(\frac 12\right)^n} & \small \blue{\text{By Lambert series}} \\ & = \frac {\frac 12}{\left(1-\frac 12\right)^2} \\ & = \boxed 2 \end{aligned}

Reference: Lambert series ∑ n = 1 ∞ ϕ ( n ) q n 1 − q n = q ( 1 − q ) 2 \displaystyle \sum_{n=1}^\infty \frac {\phi(n)q^n}{1-q^n} = \frac q{(1-q)^2} which converges when ∣ q ∣ < 1 |q| < 1 .

0 Helpful 0 Interesting 4 Brilliant 0 Confused

@ChengYlln Ong , you have to mentioned what ϕ ( ⋅ ) \phi(\cdot) is. I have done that for you.

Chew-Seong Cheong - 11 months ago

Thx! Forgot about that...

ChengYiin Ong - 11 months ago

Log in to reply

Where do you get a problem like that?

Chew-Seong Cheong - 11 months ago

Log in to reply

I saw that problem from the art of problem solving forum which this problem was from a math contest

ChengYiin Ong - 11 months ago

Thank youo very mucho! Conciso and to the pointo.

Alexander Shannon - 11 months ago

The key step is understanding why the lambert series actually converges wrt the Totient function...that wikipedia article is pretty badly written imo. The real reason the sum converges to 2 is because the exponential part totally overpowers the increase in the totient function.

Here's some python code that demonstrates it: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
def gcd(a,b): #assumes a < b
    if (a == 0): 
        return b 
    return gcd(b % a, a)

def totient(n):
    result = 1
    for i in range(2, n): 
        if (gcd(i, n) == 1): 
            result+=1
    return result 

def lambert(n):
    result = 0
    for i in range(1, n):
        result += totient(i)/(2**i-1)
        # print(f"   {result}")
    return result

def totientsum(n):
    result = 0
    for i in range(1,n):
        # print(f"{result}+{totient(i)} => {result+totient(i)}")
        result += totient(i)
    return result

def expdenom(b,i):
    return 1/(b**i-1)

def expsum(b, n):
    result = 0
    for i in range(1,n):
        result += 1/(b**i-1)
    return result

for x in range(2,100):
    print("-")
    print(f"{x}:")
    print(f"tot => {totient(x)}")
    print(f"exp => {expdenom(2,x)}")
    print(f"tts => {totientsum(x)}")
    print(f"eps => {expsum(2,x)}")
    print(f"fin => {lambert(x)}")

Imran Qureshi - 11 months ago

@Chew-Seong Cheong sir , I'm fascinated by your knowledge and really interested in knowing how do you get to know these amazing things in Number Theory.

Tattwa shiwani - 5 months ago
Patrick Corn
Jul 27, 2020

For a derivation from first principles: ∑ n = 1 ∞ ϕ ( n ) 2 n − 1 = ∑ n = 1 ∞ ϕ ( n ) ( 1 / 2 ) n 1 − ( 1 / 2 ) n = ∑ n = 1 ∞ ϕ ( n ) ∑ k = 1 ∞ ( 1 / 2 ) n k = ∑ n , k ≥ 1 ϕ ( n ) ( 1 / 2 ) n k = ∑ a = 1 ∞ ( ∑ n ∣ a ϕ ( n ) ) ( 1 / 2 ) a = ∑ a = 1 ∞ a ( 1 / 2 ) a , \begin{aligned} \sum_{n=1}^\infty \frac{\phi(n)}{2^n-1} &= \sum_{n=1}^\infty \frac{\phi(n) (1/2)^n}{1 - (1/2)^n} \\ &= \sum_{n=1}^\infty \phi(n) \sum_{k=1}^\infty (1/2)^{nk} \\ &= \sum_{n,k \ge 1} \phi(n) (1/2)^{nk} \\ &= \sum_{a=1}^\infty \left(\sum_{n|a} \phi(n) \right) (1/2)^a \\ &= \sum_{a=1}^\infty a(1/2)^a, \end{aligned} and this sum is well-known to be 1 / 2 ( 1 − 1 / 2 ) 2 = 2 . \frac{1/2}{(1-1/2)^2} = \fbox{2}.

1 Helpful 1 Interesting 2 Brilliant 1 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...