主题
Search

位数计数

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

数字 N_d^((b))(n) 在以 b 为底的数字 n 的表示中的位数称为 b-ary 位数计数，用于 d。 位数计数在 Wolfram 语言 中实现为DigitCount[n, b, d].

DigitCount1s

数字 n 的二进制表示中 1 的数量 N_1(n)=N_1^((2))(n)，如上所示，由下式给出

N_1(n)=n-gde(n!,2)
(1)
=n-sum_(k=1)^(|_log_2n_|)|_n/(2^k)_|,
(2)

其中 gde(n!,2) 是 2 相对于 n! 的最大除数指数。 这是 素数 p 除以阶乘 的幂 的一般结果的特殊应用（Vardi 1991，Graham等人。1994）。 将 a(n) 记为 N_1(n)，1 的数量也由递推关系给出

a(2n)=a(n)
(3)
a(2n+1)=a(n)+1,
(4)

其中 a(0)=0，并且由

N_1(n)=2n-log_2(d),
(5)

其中 d 是

1/(n!)[(d^n)/(dx^n)(1-x)^(-1/2)]_(x=0).
(6)

的分母 n=1、2、...，前几个值为 1、1、2、1、2、2、3、1、2、2、3、...（OEIS A000120；Smith 1966，Graham 1970，McIlroy 1974）。

对于二进制数，1 的计数 N_1(n) 等于数字和 s_2(n)。 数量 N_1(n) (mod 2) 称为非负整数 n 的奇偶性。

N_0(n) 和 N_1(n) 满足以下优美的恒等式

sum_(n=1)^(infty)(N_1(n)+N_0(n))/(2n(2n+1))=gamma
(7)
sum_(n=1)^(infty)(N_1(n)-N_0(n))/(2n(2n+1))=ln(4/pi),
(8)

其中 gamma 是欧拉-马歇罗尼常数，ln(4/pi)=0.241564... (OEIS A094640) 是其“交替模拟”（Sondow 2005）。

令 e(n) 和 o(n) 分别为 n 的偶数位和奇数位的数量。 则

sum_(n=1)^(infty)(o(2^n))/(2^n)=1/9
(9)
sum_(n=1)^(infty)(e(2^n))/(2^n)=-1/9+sum_(n=1)^(infty)(|_nlog_(10)2_|+1)/(2^n)
(10)
=1.0316063864...,
(11)

其中后者 (OEIS A096614) 是超越数（Borwein等人。2004，第 14-15 页）。

另请参阅

二进制, 位数, 位数乘积, 位数和, 奇偶性, Stolarsky-Harborth 常数

相关 Wolfram 网站

http://functions.wolfram.com/NumberTheoryFunctions/DigitCount/

使用 Wolfram|Alpha 探索

参考文献

Borwein, J.; Bailey, D.; 和 Girgensohn, R. 数学实验：计算发现之路。 Wellesley, MA: A K Peters, 2004.Graham, R. L. "关于本原图和最优顶点分配。" Ann. New York Acad. Sci. 175, 170-186, 1970.Graham, R. L.; Knuth, D. E.; 和 Patashnik, O. "阶乘因子。" §4.4 in 具体数学：计算机科学基础，第 2 版。 Reading, MA: Addison-Wesley, pp. 111-115, 1994.McIlroy, M. D. "二进制整数中 1 的数量：界限和极值性质。" SIAM J. Comput. 3, 255-261, 1974.Sloane, N. J. A. 序列 A000120/M0105, A094640, A096614 in "整数序列在线百科全书"。Smith, N. "问题 B-82。" Fib. Quart. 4, 374-365, 1966.Sondow, J. "欧拉常数及其“交替”模拟 ln(4/pi) 的新型 Vacca 型有理级数。" 2005 年 8 月 1 日。 http://arxiv.org/abs/math.NT/0508042.Trott, M. Mathematica 编程指南。 New York: Springer-Verlag, p. 33, 2004. http://www.mathematicaguidebooks.org/.Vardi, I. Mathematica 计算娱乐。 Reading, MA: Addison-Wesley, p. 67, 1991.Wolfram, S. 一种新科学。 Champaign, IL: Wolfram Media, p. 902, 2002.

在 Wolfram|Alpha 上引用

位数计数

请引用为

Weisstein, Eric W. "位数计数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/DigitCount.html

主题分类