正整数二进制展开中1的个数：g(f(n))及fₖ(n)的计算问题

咱们先明确题目里的两个核心函数定义：

• 函数 $f:\mathbb{Z^{+}\to\mathbb{Z}+}$（其中$\mathbb{Z^+}$代表正整数），定义为 $f(n)=3^n+3n$
• 函数 $g:\mathbb{Z^{+}\to\mathbb{Z}+}$ 是用来统计正整数二进制展开中1的个数的函数（也就是常说的汉明重量）

一、求解g(f(n)) #

首先，咱们先代入几个小的正整数n，看看能不能找到规律：

• n=1：$f(1)=3+3=6$，二进制为110，所以$g(f(1))=2$
• n=2：$f(2)=9+6=15$，二进制为1111，所以$g(f(2))=4$
• n=3：$f(3)=27+9=36$，二进制为100100，所以$g(f(3))=2$
• n=4：$f(4)=81+12=93$，二进制为1011101，所以$g(f(4))=5$
• n=5：$f(5)=243+15=258$，二进制为100000010，所以$g(f(5))=2$
• n=6：$f(6)=729+18=747$，二进制为1011101011，所以$g(f(6))=6$

从这些例子能看出来，$g(f(n))$的数值并没有一个简单的统一规律——这本质上是因为$3^n$的二进制展开本身就没有简洁的闭合表达式，再加上$3n$之后，两者二进制相加会产生进位，而进位的情况完全取决于两个数二进制位的重叠状态，很难用一个通用式子直接表达。

如果要深入分析，我们可以用模2的幂来推导某些位的取值，但最终还是无法得到一个能直接计算任意n对应$g(f(n))$的简洁公式，只能针对具体的n值进行计算，或者分析特定n范围（比如奇数/偶数n）下的局部规律。

二、一般化情况：求解g(fₖ(n)) #

对于定义为 $f_{k}(n)=k^n+kn$ 的函数，$g(f_k(n))$的求解难度完全取决于k的取值，咱们分几种情况讨论：

• 当k是2的幂时：比如$k=2^{m$，那么$k}n=2^{{mn}$，二进制是`1`后面跟$mn$个0；$kn=2}m \times n$，二进制是n的二进制后面跟m个0。当$mn > \log_2(n)+m$时（也就是n足够大时），两个数的二进制位没有重叠，相加后不会产生进位，此时$g(f_k(n))=g(n)+1$；当n较小时，两个数的二进制位可能重叠，需要具体分析进位情况。
• 当k是奇数时：比如k=3、5这类，$k^n$的二进制展开没有规律可言，加上$kn$后的进位情况更加复杂，和原问题类似，无法得到通用的闭合表达式，只能针对具体n或k计算数值。
• 当k是偶数但不是2的幂时：比如k=6=2×3，此时$f_k(n)=6ⁿ⁺⁶ⁿ⁼²n \times 3^n + 2\times3n=2\times(3^n \times 2^{{n-1}+3n)$，二进制里乘以2就是左移一位，1的个数不变，所以$g(f_k(n))=g(3}n \times 2^{n-1}+3n)$，这就转化成了类似奇数k的复杂情况，同样没有简洁公式。

总结 #

不管是原问题中的$g(f(n))$，还是一般化的$g(f_k(n))$，都不存在一个能直接计算任意n值的简洁通用公式。大部分情况下，我们只能针对具体的n或k进行数值计算，或者在特定条件（比如k是2的幂且n足够大）下找到局部规律。

内容的提问来源于stack exchange，提问作者Klangen