二进制中数字之和函数及其均值估计＊

付火星, 朱伟义

(浙江师范大学数理与信息工程学院,浙江金华 321004)

十进制中数字之和数列的性质是文献[1]中提出的初等数论和集合论中 105个未解决的问题之一.许多学者对 n进制中数字之和函数的均值性质进行了研究,并得到了很多有意义的结论.本文将对二进制中数字之和函数的均值性质作进一步的讨论.

设自然数N在二进制表示下为as…a2a1a0,其中 ai=0或 1.定义函数 a(N)为N在二进制表示下的1,2,3,4,5,6,7,8)的精确计算公式.但是,要想得到更高次的均值精确计算公式,难度会越来越大.本文就这类问题进行了讨论,得到 Bm(Rn)的一个渐近性质,然后利用这个性质,给出了二进制中数字之和函数的 m次均值 Bm(N)的一个估计.

00是无意义的,为讨论方便,规定 00=1.根据以上定义,容易验证 Bm(Rn)有如下几个基本性质:1)B0(Rn)=Rn=2n;2)Bm(R0)=0(m≥1);3)Bm(R1)=1(m≥1).

为证明主要结果,先给出引理 1.

将式 (2)中的每个式子分别乘以 20,21,22,…,2n-2,并将其相加,得

考虑到 T1=1及 Bm(Rn)的基本性质 3),由式 (3)立即得到

根据引理 1以及 Bm(Rn)的基本性质 1)可以很容易地得到如下结论:

值得一提的是,这些结论与文献[2-6]的结果是一致的.当然,还可以利用引理 1以及 Bm(Rn)的基本性质 1)继续演算下去,从而得到 B6(Rn),B7(Rn),…等一系列计算公式.但是,当面对越来越大的 m值时,逐次往后递推的运算过程会越来越复杂,均值的精确计算公式也会非常冗长复杂.然而,从B0(Rn),B1(Rn),B2(Rn),B3(Rn),B4(Rn),B5(Rn)的计算公式中不难发现,当 t=0,1,2,3,4,5时Bt(Rn)与 nt2n-t是等价无穷大的,于是很自然地就会产生一个疑问:是否对于任意自然数 m,总成立Bm(Rn)～nm2n-m?定理 1给出了肯定的回答.

定理 1 对于任意给定的非负整数 m,有 Bm(Rn)～nm2n-m(n→∞).

证明 用归纳法证明.当 m=0时,由 Bm(Rn)的基本性质 1)知 B0(Rn)=Rn=2n,此时命题显然成立.现假设对任意小于 m(m≥1)的 t∈Z+,命题都成立,即 Bt(Rn-1)～(n-1)t2n-1-t.下面证明当 t=m时命题也成立.

由极限的定义知,对任意给定的ε>0,存在自然数 N,使得当 n>N时,

即

记式 (5)右端两项分别为 I1(n),I2(n).注意到 m≥1,故显然有 I1(n)→0.下面考虑 I2(n).由式 (4)不难得到

利用二项式定理,由式 (6)可得

即

这说明 Bt(Rn)～nt2n-t在 t=m时也成立.根据归纳法原理,定理 1得证.

定理 1给出了 Bm(Rn)的渐近性质,利用这个性质可以对二进制中数字之和函数的 m次均值Bm(N)给出一个估计,得定理 2.

定理 2 对于任意给定的非负整数 m,有 Bm(N)=O((log2N)mN)(N→+∞).

证明 设 N=2n1+2n2+…+2ns,其中 n1>n2>…>ns≥0,则 2n1≤N<2n1+1.下面考虑

令 N→+∞,并根据定理 1可得

由式 (7)和式 (8)得 Bm(N)=O((log2N)mN).定理 2证毕.

最后提出一个问题,既然在二进制下已经对其数字之和函数的 m次均值给出了一个估计,那么是否在任意 p进制下,也可以类似地对其数字之和函数作一定的均值估计?这是一个理论上值得探讨的问题.

[1]Smarandache F.Only Problems,Not Solutions[M].Chicago:Xiquan Publishing House,1993.

[2]李海龙,杨倩丽.关于 n进制及其有关计数函数[J].纯粹数学与应用数学,2002,18(1):13-15.

[3]杨倩丽,李海龙.关于 n进制中数字之和函数均值的计算[J].西北大学学报:自然科学版,2002,32(4):361-366.

[4]杨倩丽.一个数论函数的三次均值的计算[J].纺织高校基础科学学报,2002,15(1):47-48.

[5]杨倩丽.一个数论函数的四次均值的计算[J].陕西师范大学学报:自然科学版,2002,30(专刊):63-64.

[6]李海龙,刘志敏,成兴阁.一个数论函数的五次均值的计算[J].宝鸡文理学院学报:自然科学版,2002,22(4):256-257.

[7]杨海,付瑞琴,葛丹.一个数论函数的六次均值计算[J].延安大学学报:自然科学版,2003,22(4):4-5.

[8]常胜伟,申小琳.一个数论函数的七次均值计算[J].延安大学学报:自然科学版,2005,24(1):7-9.

[9]朱丽平.一个数论函数的八次均值计算[J].西南民族大学学报:自然科学版,2007,33(1):5-8.