强全一数
|
7在2进制和6进制下的表示都由1组成，即$7_{10}=11_{6}=111_2$。
若一个正整数在至少两种进制下的表示都由一组成，就称其为强全一数。
可以验证，有八个小于50的强循环单位数：1,7,13,15,21,31,40,43，且所有小于1000的强全一数之和是15864。
求所有小于$10^{12}$的强全一数之和。
|
本题难度:
|
解答
|
显然对任意$n>2$都有$n=11_{n-1}$，因此只要一个数能在某一进制下表示为长度至少为3的全一数，那么它就是强全一数。
在b进制下这样的数至少是$b^2+b+1$，因此只需枚举基数b并生成该进制下不超过$10^{12}$的全一数再去重即可，最终结果是$336108797689259276$。
target=10**12
b=2
s=set()
while b*b+b+1 < target:
m=b*b+b+1
while m < target:
s.add(m)
m=m*b+1
b+=1
print sum(s)+1
|
| |
