For positive integer $x>1$, define set $S_x$ as $$S_x=\{p^\alpha|p \textup{ is one of the prime divisor of }x,\alpha \in \mathbb{N},p^\alpha|x,\alpha \equiv v_p(x)(\textup{mod} 2)\},$$where $v_p(n)$ is the power of prime divisor $p$ in positive integer $n.$ Let $f(x)$ be the sum of all the elements of $S_x$ when $x>1,$ and $f(1)=1.$ Let $m$ be a given positive integer, and the sequence $a_1,a_2,\cdots,a_n,\cdots$ satisfy that for any positive integer $n>m,$ $a_{n+1}=\max\{ f(a_n),f(a_{n-1}+1),\cdots,f(a_{n-m}+m)\}.$ Prove that (1)there exists constant $A,B(0<A<1),$ such that when positive integer $x$ has at least two different prime divisors, $f(x)<Ax+B$ holds; (2)there exists positive integer $N,l$, such that for any positive integer $n\geq N ,a_{n+l}=a_n$ holds.
Problem
Source: 2019 CSMO Grade 11 P8
Tags: number theory
31.07.2019 19:03
不想翻译成我的蹩脚英文, 就用中文吧, 需要看的朋友们大多是中国的老师和学生. 我是嘉兴一中的萌新老师, 工作一年未满的那种, 你是不是也在吉安? 我现在很期待我学生的成绩. 明天你会在公众号上看到我的解答和叙述背景. (1)是容易题, 从数量级上看, $A<1$显然, $B$是只依赖于那些比较小的素数的一个值, 我们直接做(2), 为便于大家get到其中关键, 我们一边分析, 一边用白话文(我也不擅长规范叙述)进行证明: 我们用 $\mathbb{P}$表示所有素数构成的集合, 根据第(1)问, 若充分大的$x$不为素数方幂, 那么$f(x)<Ax+B<x$, 我们再迭代过程中只要处理充分大的素数方幂$p^k$, 并且我们注意到: $$\frac{\sum_{i=0}^{k} p^{2i}}{p^{2k}}<\frac{1}{1-\frac{1}{p^2}}=1+\frac{1}{p^2-1};$$$$\frac{\sum_{i=0}^{k} p^{2i+1}}{p^{2k+1}}<\frac{1}{1-\frac{1}{p^2}}=1+\frac{1}{p^2-1}$$在迭代过程中, 有$f(p^k)<(1+\dfrac{1}{p^2-1})p^k$. 注意到: 每一次通过了一个充分大的素数方幂的迭代, $a_n$至多是之前的$1+\dfrac{1}{p^2-1}$倍($m$是有限值, 素数方幂趋向无穷大, 若成为之前的$1+\dfrac{1}{p^2-1}+h$倍, $h>0$, 根据素数方幂充分大可得矛盾), 再注意到: $$\prod_{p \in \mathbb{P}}(1+\dfrac{1}{p^2-1})=\prod_{p \in \mathbb{P}} \sum_{k=0}^{+\infty} \frac{1}{p^{2k}}=\sum_{n=1}^{+\infty} \frac{1}{n^2}=\frac{\pi^2}{6}<2,$$(如果$p$用$n\ln n$近似替换, 其中, $p$ 是第$n$ 个素数, 除非积分, 不然不好处理, 更何况用到素数定理得可能性很小, 另外, 其实, 我们可以直接裂项来处理$\prod\limits_{p \in \mathbb{P}}(1+\dfrac{1}{p^2-1})<\prod\limits_{n>1}\dfrac{n^2}{n^2-1}<2$, 之前的表述只是为了提一下罗老师在讲评过程中说到的和Riemann $\zeta$函数有关的地方在哪). 若迭代次数充分大之后, (可以不计加上的常数)发生$$\max\{a_1, a_2, \cdots, a_n\} <a_{n+1},$$则必须通过一个素数方幂才能提供, 若$\{a_n\}$ 迭代过程中经过了两个$p$ 的方幂, 分别为$p^a$ 和$p^b$, 较大者至少是较小者的$p (\geq 2)$ 倍, 不失一般性, 设这两个$p$ 的方幂之间不存在相同的素数方幂(若有, 那便直接用这两项替换, 直到没有为止), 那么通过迭代亦不能超过2 倍, 矛盾. 这说明, 对于给定的素数, 其方幂在迭代过程中至多出现一次, 于是无论经过多少次迭代, 都不会超过$2$ 倍, 所以$\{a_n\}$必然有界. 再考虑有限维向量$(a_i, a_{i+2}, \cdots, a_{i+m})$必有重复, 可得周期性.
02.08.2019 15:45
Well, the problem (2) for the Grade Ten students is to prove that $a_n$ is bounded, which can imply this problem (2). My method is to consider that in the situation $a_{n-i}+i$ is a power of a prime number $p^s$, $f(p^s) = p^s \cdot \frac{1}{1-p^{-s}}$, which jumps. Denote $M_n = \max\{a_1 , a_2 , \ldots , a_n \}$. We may denote $\{n_i \}$ as a series of subscript that $M_{n_i}>M_{n_i -1}$, and $a_{n_i}=f(p_{i}^{s_i})$. If there exist an $i$ and a $j$ such that $i<j$, $p_i = p_j = p$, and $p_{i+1},\ldots,p_{j-1}\neq p$. We have $$\frac{a_{n_j}}{a_{n_i}}=\frac{1-p^{-2\cdot[s_j /2]}}{1-p^{-2\cdot[s_i /2]}}>p^{s_j -s_i }\geq p\geq 2$$but $$\frac{a_{n_j}}{a_{n_i}}=\frac{M_{n_j}}{M_{n_i}}=\prod_{k=i+1}^{j}\frac{M_{n_k}}{M_{n_{k+1}}}<\prod_{k=i+1}^{j}(1-p_{k}^{-2})^{-1}<\prod_{p\text{ prime}}(1-p^{-2})^{-1}<\prod_{n\geq 2}(1-n^{-2})^{-1}=\prod_{n\geq 2}\frac{n}{n-1}\cdot\frac{n}{n+1}=2$$which makes a contradiction. So all $p_i$ are different to each others. And also, we have $$\lim_{k\rightarrow\infty}\frac{M_{n_{i+k}}}{M_{n_i}}<\lim_{k\rightarrow\infty}\prod_{k=1}(1-p_{k}^{-2})^{-1}\leq\prod_{p\text{ prime}}(1-p^{-2})^{-1}<2$$So all "jumps" are bounded, which means that $\{a_i \}$ is a bounded series. For this problem (2), the series $\{f(a_{n}) , f(a_{n-1}+1) , \ldots , f(a_{n-m}+m) \}$ has only finitely many values. So there exists $N,N'$ such that $\{f(a_{N}) , f(a_{N-1}+1) , \ldots , f(a_{N-m}+m) \}=\{f(a_{N'}) , f(a_{N'-1}+1) , \ldots , f(a_{N'-m}+m) \}$. So this series is periodic.