Ký hiệu $s(k)$ là tổng các chữ số của một số tự nhiên $k$ và $$S_n = \sum_{k < n} s(k).$$ Ta cần tính $S_n + s(n)$.
Ta có thể tính $S_n$ bằng đệ quy với công thức $$\begin{cases} S_0 = 0 \\ S_n = 10S_m + 45m + r \cdot s(m) + \frac{r(r-1)}{2}\end{cases}$$ với $m = \left\lfloor\frac{n}{10}\right\rfloor$ và $r = n-10m$.
Thật vậy, theo định nghĩa trên thì $m$ và $r$ lần lượt là phần chục và chữ số hàng đơn vị của $n$. Mỗi số tự nhiên $k < n$ có dạng $k = 10m' + r'$ với $m' < m$ và $r' \in \{0,1,\ldots,9\}$ hoặc $k = 10m + r'$ với $r' \in \{0,1,\ldots,r-1\}$. Do đó $$\begin{align*} S_n & = \sum_{m' < m} \sum_{r' = 0}^9 s(10m' + r') + \sum_{r'=0}^{r-1}s(10m+r) \\ & = \sum_{m' < m} \sum_{r' = 0}^9 (s(m') + r') + \sum_{r'=0}^{r-1} (s(m)+r') \\ & = \sum_{m' < m} (10s(m') + 45) + r \cdot s(m) + \frac{r(r-1)}{2} \\ & = 10 S_m + 45m + r \cdot s(m) + \frac{r(r-1)}{2}.\end{align*}$$
Để xác định độ phức tạp về thời gian $T(n)$ khi tính theo công thức truy hồi trên, nhận xét rằng $$T(n) = T\left(\frac{n}{10}\right) + O(\log n),$$ nên theo
định lý Master thì $T(n) = O(\log^2 n)$, tức là bằng hàm đa thức bậc hai theo cỡ của input. Từ công thức truy hồi trên có thể tính ra $S_n + s(n)$ theo các chữ số của $n$, nhưng mình chưa đủ kiên nhẫn để thử.
Bài viết đã được chỉnh sửa nội dung bởi nmlinh16: 15-07-2023 - 08:53
$$\text{H}^r_{\text{ét}}(\mathcal{O}_K, M) \times \text{Ext}^{3-r}_{\mathcal{O}_K}(M,\mathbb{G}_m) \to \text{H}^3_{\text{ét}}(\mathcal{O}_K,\mathbb{G}_m) \cong \mathbb{Q}/\mathbb{Z}.$$
"Wir müssen wissen, wir werden wissen." - David Hilbert