Determine whether \(G(2026)\) is odd or even, where \(G(n)\) is defined by
\[ G(n)=\sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor, \]
and \(\lfloor x\rfloor\) denotes the floor function (the greatest integer \(\le x\)).
Key Idea
The expression \(\left\lfloor \frac{n}{k}\right\rfloor\) counts how many multiples of \(k\) are at most \(n\):
\[ \left\lfloor\frac{n}{k}\right\rfloor = \#\{\,j\in\mathbb{N} : kj \le n\,\}. \]
So the whole sum
\[ G(n)=\sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor \]
counts the number of integer pairs \((k,j)\) such that \(kj\le n\).
Rewriting the Sum Using Divisors
Let’s count the same pairs \((k,j)\) in a different way.
For every product \(m = kj\) with \(m \le n\), how many pairs \((k,j)\) satisfy \(kj=m\)? Exactly as many as the number of positive divisors of \(m\). Denote this divisor-counting function by \(d(m)\).
That means:
\[ G(n)=\sum_{m=1}^{n} d(m). \]
So the parity (odd/even nature) of \(G(n)\) depends on the parity of the sum of divisor counts up to \(n\).
A Crucial Parity Fact: When Is \(d(m)\) Odd?
Divisors usually come in pairs: if \(a\mid m\), then \(\frac{m}{a}\mid m\) as well.
- If \(a \ne \frac{m}{a}\), they form a pair contributing 2 divisors.
- The only way a divisor can pair with itself is when \(a = \frac{m}{a}\), i.e. \(a^2 = m\).
So only perfect squares have an unpaired “middle divisor” \(\sqrt{m}\), and therefore:
\(d(m)\) is odd if and only if \(m\) is a perfect square.
Thus, modulo 2:
\[ d(m) \equiv \begin{cases} 1 & \text{if } m \text{ is a square},\\ 0 & \text{otherwise}. \end{cases} \]
Reducing \(G(n)\) Modulo 2
Now look at \(G(n)\) modulo 2:
\[ G(n)=\sum_{m=1}^{n} d(m) \equiv \sum_{m=1}^{n} (d(m)\bmod 2) \pmod 2. \]
But only squares contribute a 1. Therefore:
\[ G(n)\equiv \#\{\,m\le n : m \text{ is a perfect square}\,\}\pmod 2. \]
How many squares are \(\le n\)? They are \(1^2, 2^2, \dots, \lfloor\sqrt{n}\rfloor^2\), so there are exactly \(\lfloor\sqrt{n}\rfloor\) of them:
\[ G(n)\equiv \lfloor\sqrt{n}\rfloor \pmod 2. \]
This is the whole trick:
the parity of \(G(n)\) is the same as the parity of \(\lfloor \sqrt{n}\rfloor\).
Applying It to \(n = 2026\)
Compute \(\lfloor\sqrt{2026}\rfloor\).
We know:
- \(45^2 = 2025\)
- \(46^2 = 2116\)
So:
\[ 45^2 \le 2026 < 46^2 \quad\Rightarrow\quad \left\lfloor\sqrt{2026}\right\rfloor = 45. \]
And since \(45\) is odd, we conclude:
\[ G(2026)\equiv 45 \equiv 1 \pmod 2. \]
Final Answer
\[ \boxed{G(2026)\text{ is odd}.} \]
General Rule
For every \(n\ge 1\),
\[ \boxed{G(n)\text{ is odd } \Longleftrightarrow \lfloor\sqrt{n}\rfloor \text{ is odd}.} \]
So you can decide the parity of this entire floor-sum just by checking how many perfect squares fit below \(n\).