二進制中數字之和函數及其均值估計＊

付火星, 朱偉義

(浙江師范大學數理與信息工程學院,浙江金華 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.