Let $L(n)$ denote the number of positive divisors of a number $n$. Prove that $\sum_{n=1}^N L(n)=\lfloor{\sqrt N}\rfloor\pmod 2$.

Question

Let $L(n)$ denote the number of positive divisors of a number $n$. Prove that $\sum_{n=1}^N L(n)=\lfloor{\sqrt N}\rfloor\pmod 2$.

I wanted to prove that by induction. For $n=1$ True. Assume True for some N. Now we have $N+1$. I observed that $L(n)=n-\phi(n)+1$ where phi is Euler's function. And what now... If $N+1$ is a square, then $\lfloor\sqrt N\rfloor\ne\lfloor\sqrt{N+1}\rfloor\pmod 2$, whereas they are the same modulo 2 if $N+1$ is not a square. When we add $N+1$th element to the sum, we add $N+1-\phi(N+1)+1$ which modulo 2 is $N-\phi(N+1)$. So, the function $k(n)=n-\phi(n+1)$ should be odd if $n+1$ is square, and even if it is not square. But, I opened table of Euler's phi function and that function seems to be odd when n is odd and even when n is even - I looked all naturals < 500. So, where am I wrong?

I would be also happy to see non-induction solution, because it is probably better way. I just cant imagine from where did that sqrt(N) came from when I think about that sum.

Thanks in advance for help. I will probably answer for comments tomorrow.

Answer 1

Your $L(n)$ can be odd only when $n$ itself is a perfect square. So, mod 2, you are just counting the squares up to the upper bound, which you called $N$.

First, $L(1) = 1.$ If $n> 1,$ it has a prime factorization, say $$ n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r} $$ with exponents $a_j \geq 1$ and $r$ primes with $r \geq 1.$ Then $$ L(n) = (a_1+1) (a_2 + 1) \cdots (a_r + 1). $$ If any of the $a_j$ is odd, then $a_j + 1$ is even, so $L(n)$ is even. That is the most frequent outcome. It is possible to have $L(n)$ odd only when all the $(a_j + 1)$ are odd, meaning all the $a_j$ are even, meaning $n$ is a perfect square.

Answer 2

Your evaluation of $L$ using the Euler phi function is wrong, it works only for primes and 1 and 4.

Thu Dec 26 13:34:20 PST 2019

1 =  1     divisor count: 1         n - phi + 1:  1  EQUAL 
2 = 2    divisor count: 2         n - phi + 1:  2  EQUAL 
3 = 3    divisor count: 2         n - phi + 1:  2  EQUAL 
4 = 2^2    divisor count: 3         n - phi + 1:  3  EQUAL 
5 = 5    divisor count: 2         n - phi + 1:  2  EQUAL 
6 = 2 * 3    divisor count: 4         n - phi + 1:  5
7 = 7    divisor count: 2         n - phi + 1:  2  EQUAL 
8 = 2^3    divisor count: 4         n - phi + 1:  5
9 = 3^2    divisor count: 3         n - phi + 1:  4
10 = 2 * 5    divisor count: 4         n - phi + 1:  7
11 = 11    divisor count: 2         n - phi + 1:  2  EQUAL 
12 = 2^2 * 3    divisor count: 6         n - phi + 1:  9
13 = 13    divisor count: 2         n - phi + 1:  2  EQUAL 
14 = 2 * 7    divisor count: 4         n - phi + 1:  9
15 = 3 * 5    divisor count: 4         n - phi + 1:  8
16 = 2^4    divisor count: 5         n - phi + 1:  9
17 = 17    divisor count: 2         n - phi + 1:  2  EQUAL 
18 = 2 * 3^2    divisor count: 6         n - phi + 1:  13
19 = 19    divisor count: 2         n - phi + 1:  2  EQUAL 
20 = 2^2 * 5    divisor count: 6         n - phi + 1:  13
21 = 3 * 7    divisor count: 4         n - phi + 1:  10
22 = 2 * 11    divisor count: 4         n - phi + 1:  13
23 = 23    divisor count: 2         n - phi + 1:  2  EQUAL 
24 = 2^3 * 3    divisor count: 8         n - phi + 1:  17
25 = 5^2    divisor count: 3         n - phi + 1:  6
26 = 2 * 13    divisor count: 4         n - phi + 1:  15
27 = 3^3    divisor count: 4         n - phi + 1:  10
28 = 2^2 * 7    divisor count: 6         n - phi + 1:  17
29 = 29    divisor count: 2         n - phi + 1:  2  EQUAL 
30 = 2 * 3 * 5    divisor count: 8         n - phi + 1:  23
31 = 31    divisor count: 2         n - phi + 1:  2  EQUAL 
32 = 2^5    divisor count: 6         n - phi + 1:  17
33 = 3 * 11    divisor count: 4         n - phi + 1:  14
34 = 2 * 17    divisor count: 4         n - phi + 1:  19
35 = 5 * 7    divisor count: 4         n - phi + 1:  12
36 = 2^2 * 3^2    divisor count: 9         n - phi + 1:  25
37 = 37    divisor count: 2         n - phi + 1:  2  EQUAL 
38 = 2 * 19    divisor count: 4         n - phi + 1:  21
39 = 3 * 13    divisor count: 4         n - phi + 1:  16
40 = 2^3 * 5    divisor count: 8         n - phi + 1:  25
41 = 41    divisor count: 2         n - phi + 1:  2  EQUAL 
42 = 2 * 3 * 7    divisor count: 8         n - phi + 1:  31
43 = 43    divisor count: 2         n - phi + 1:  2  EQUAL 
44 = 2^2 * 11    divisor count: 6         n - phi + 1:  25
45 = 3^2 * 5    divisor count: 6         n - phi + 1:  22
46 = 2 * 23    divisor count: 4         n - phi + 1:  25
47 = 47    divisor count: 2         n - phi + 1:  2  EQUAL 
48 = 2^4 * 3    divisor count: 10         n - phi + 1:  33
49 = 7^2    divisor count: 3         n - phi + 1:  8
50 = 2 * 5^2    divisor count: 6         n - phi + 1:  31
51 = 3 * 17    divisor count: 4         n - phi + 1:  20
52 = 2^2 * 13    divisor count: 6         n - phi + 1:  29
53 = 53    divisor count: 2         n - phi + 1:  2  EQUAL 
54 = 2 * 3^3    divisor count: 8         n - phi + 1:  37
55 = 5 * 11    divisor count: 4         n - phi + 1:  16
56 = 2^3 * 7    divisor count: 8         n - phi + 1:  33
57 = 3 * 19    divisor count: 4         n - phi + 1:  22
58 = 2 * 29    divisor count: 4         n - phi + 1:  31
59 = 59    divisor count: 2         n - phi + 1:  2  EQUAL 
60 = 2^2 * 3 * 5    divisor count: 12         n - phi + 1:  45
61 = 61    divisor count: 2         n - phi + 1:  2  EQUAL 
62 = 2 * 31    divisor count: 4         n - phi + 1:  33
63 = 3^2 * 7    divisor count: 6         n - phi + 1:  28
64 = 2^6    divisor count: 7         n - phi + 1:  33
65 = 5 * 13    divisor count: 4         n - phi + 1:  18
66 = 2 * 3 * 11    divisor count: 8         n - phi + 1:  47
67 = 67    divisor count: 2         n - phi + 1:  2  EQUAL 
68 = 2^2 * 17    divisor count: 6         n - phi + 1:  37
69 = 3 * 23    divisor count: 4         n - phi + 1:  26
70 = 2 * 5 * 7    divisor count: 8         n - phi + 1:  47
71 = 71    divisor count: 2         n - phi + 1:  2  EQUAL 
72 = 2^3 * 3^2    divisor count: 12         n - phi + 1:  49
73 = 73    divisor count: 2         n - phi + 1:  2  EQUAL 
74 = 2 * 37    divisor count: 4         n - phi + 1:  39
75 = 3 * 5^2    divisor count: 6         n - phi + 1:  36
76 = 2^2 * 19    divisor count: 6         n - phi + 1:  41
77 = 7 * 11    divisor count: 4         n - phi + 1:  18
78 = 2 * 3 * 13    divisor count: 8         n - phi + 1:  55
79 = 79    divisor count: 2         n - phi + 1:  2  EQUAL 
80 = 2^4 * 5    divisor count: 10         n - phi + 1:  49
81 = 3^4    divisor count: 5         n - phi + 1:  28
82 = 2 * 41    divisor count: 4         n - phi + 1:  43
83 = 83    divisor count: 2         n - phi + 1:  2  EQUAL 
84 = 2^2 * 3 * 7    divisor count: 12         n - phi + 1:  61
85 = 5 * 17    divisor count: 4         n - phi + 1:  22
86 = 2 * 43    divisor count: 4         n - phi + 1:  45
87 = 3 * 29    divisor count: 4         n - phi + 1:  32
88 = 2^3 * 11    divisor count: 8         n - phi + 1:  49
89 = 89    divisor count: 2         n - phi + 1:  2  EQUAL 
90 = 2 * 3^2 * 5    divisor count: 12         n - phi + 1:  67
91 = 7 * 13    divisor count: 4         n - phi + 1:  20
92 = 2^2 * 23    divisor count: 6         n - phi + 1:  49
93 = 3 * 31    divisor count: 4         n - phi + 1:  34
94 = 2 * 47    divisor count: 4         n - phi + 1:  49
95 = 5 * 19    divisor count: 4         n - phi + 1:  24
96 = 2^5 * 3    divisor count: 12         n - phi + 1:  65
97 = 97    divisor count: 2         n - phi + 1:  2  EQUAL 
98 = 2 * 7^2    divisor count: 6         n - phi + 1:  57
99 = 3^2 * 11    divisor count: 6         n - phi + 1:  40
100 = 2^2 * 5^2    divisor count: 9         n - phi + 1:  61


Thu Dec 26 13:34:20 PST 2019