一个数的地板和天花板

数论是一门学科,也是我的人生。有人把酒论英雄,我用数字描天下。
打印 被阅读次数

一个实数的取整有两种方式,一是向下取整,fl(x),称为floor of x (地板函数),即是x的整数部分,x = fl(x) + dp(x), 0 ≤ dp(x) < 1(x的小数部分);另一个是向上取整,cl(x),称为ceiling of x (天花板),即是x = cl(x) – cp(x), 0 ≤ cp(x) < 1。当x为整数时,fl(x) = cl(x);但x不是整数时,cl(x) = fl(x) + 1。dp(x)和cp(x)都是周期为1的函数;fl(x)和cl(x)都是非初等函数,不在任何国家的数学大纲内,却是数学竞赛出题者的最爱。

fl(x)的主要应用在于 “滤波”, 即在一种量的连续分布中,去掉某些成分后,剩余部分的数学表示。对于离散的有理数m/n,fl(m/n) 是正整数m除以正整数n的商,余数m%n (按C语言的记号) 自然就是 m – nfl(m/n) 。对任意实数x, 1/2 – dp(x)是可以用Fourier级数表示的,如果x非整数,它就等于sigma{sin(2πnx)/nπ, n从1加到无穷} 。

例如,有人把完全平方数从正整数列中去掉,得到2, 3, 5, 6, 7, 8, 10, …;它的第n项就是n + fl(sqrt(n)),若n ≤ fl^2(sqrt(n)) + fl(sqrt(n));否则为n + 1 + fl(sqrt(n))。也可以把任意k次幂去掉,剩下的数用地板函数表出。也有人把正整数n重复n次排成一行:1, 2, 2, 3, 3, 3, 4, 4, 4, 4, …, 它的第n项就是fl(sqrt(2n) + 0.5), 也可以表示为fl[(1 + sqrt(8n – 7))/2]。在2011年的Euclid竞赛中的第九题,就是对此数列性质的讨论。

还有人把前n个自然数排成一圈(圆形),从1开始,按照顺时针方向,去一个留一个,最后被去掉的那个数记为L(n) (2022年Cayley Contest最后一题)。显然,L(1) = 1, 当n > 1时,第一轮过后剩下的是全部的偶数2, 4, …, 2fl(n/2) ;因此L(n) = 2L(fl(n/2)) ;自然有L(2k) = L(2k + 1)。这个递推式的解很简单,就是L(2^m + h) = 2^m,对所有非负整数h < 2^M。

在1996年的AIME,2005年的Euclid竞赛中,出题者把1到n的自然数排成一行,从1开始,从左到右,留一个去一个;然后再回过头来,从右到左,留一个去一个;如此反复,直到最后一个数。其编号记为R(n)。显然,R(1) = 1;R(2k – 1) = R(2k)。对于n = 2k,第一轮过后,剩下的是k个奇数:1, 3, …, 2k – 1;如果从右到左将它们重新编号,就可发现一个规律:[R(2k) + 1]/2 + R(k) = k + 1,即R(2k) = 2k + 1 – 2R(k)。写成一般式子,有R(n) = 2cl(n/2) + 1 – 2R(cl(n/2))。在AIME的那道题中,n = 1024是2的幂,很容易解出。对于一般的n,可以把它写为二进制数,得出递推公式。

另一个应用是计数:满足不等式g(n) ≤ x的正整数n的个数为fl(g^(-1)(x))。例如,在n!中,它能够被一个质数p除尽的最高次数为fl(n/p) + fl(n/p^2) + fl(n/p^3) + … 直到0.因此n! 末尾的 0的个数为fl(n/5) + fl(n/25) + fl(n/125) + fl(n/625) + …。计算此和式的办法是将n用p进位制表示,结果就是逐次去掉一个低位数字,依次把各位数字从低位到高位相加。

再一个应用是整除性的判定:正整数m被n整除就是dp(m/n) = (m%n)/n = 0。根据Wilson定理,一个数p为质数的充分必要条件是,dp{[(n – 1)! + 1]/n} = 0;但阶乘太大,难于计算。如果用平方根判别法,p为质数的条件是fl(p/q) 不等于0,对有质数q≤ sqrt(p)。给定前n个质数,可以用地板函数表示出下一个质数。

涉及到fl(x)的计算或证明,实际上都是解不等式。有兴趣的话,不妨试试这几给问题:

(1)给定正整数n. 问集合{fl(k^2/n): k = 1, 2, …, n}中,有多少个不同的整数值?

(2)解方程 fl(3/x) + fl(4/x) = 5;

(3)解方程xfl(x) = 7;

(4)给定正整数n,定义一个数列t(k) = 2n(k^2%n) + k,对k = 1, 2, …, n;请找出所有正整数n,使得有四个不同的正整数i, j, k, m ≤ n, 满足t(i) + t(j) = t(k) + t(m)。

最后一题是Euclid竞赛2017年的问题。在这个竞赛中,许多问题都没有一个初等函数表达式。但是,如果能够使用地板/天花板的话,则只剩计数问题难以表出了。时至今日(3月7日),离此项竞赛还有一个月的时间,若能弄清表达式的话,一定满分可达!

登录后才可评论.