我的目标是找到由4、5、6组成的所有数字，从4到666554的总和。
SUM = 4+5+6+44+45+46+54+55+56+64+65+66+.....................+666554.
一种简单的方法是运行一个循环，只加上由4、5和6组成的数字。
long long sum = 0;
for(int i=4;i <=666554;i++){
/*check if number contains only 4,5 and 6.
if condition is true then add the number to the sum*/
}
但似乎效率不高。检查数字是否由4、5和6组成需要时间。有没有提高效率的方法？我已经尝试了很多，但没有找到新的方法。请帮忙。
对于一位数字，请注意：
4 + 5 + 6 == 5 * 3
对于两位数：
(44 + 45 + 46) + (54 + 55 + 56) + (64 + 65 + 66)
== 45 * 3 + 55 * 3 + 65 * 3
== 55 * 9
等等其他的数字。
一般来说，对于n位数，由4、5、6组成的数字共有3n个，它们的平均值恰好为5...5（n位数）。使用代码计算它们的总和为('5'*n).to_i * 3**n（Ruby）或int('5'*n) * 3**n（Python）。
您可以计算6位数字，然后从666555到666666的总和中减去它们。
P.S：对于像666554这样的小数字，使用模式匹配已足够快了。（示例）
('5' * n).to_i * 3 ** n （Ruby）或者 int('5' * n) * 3 ** n （Python）可以实现相同的功能。 - Yu Hao(10**n-1)*5//9 * 3**n，而不需要使用字符串操作。 - Colonel Panic实现一个基于3进制的计数器（数字值的数量），例如0，1，2，10，11，12，20，21，22，100.... 然后将3进制数字转换为十进制数字，并使用数字4、5、6（0->4，1->5，2->6）加到累加器中。重复此过程直到达到限制。
def compute_sum(digits, max_val):
def _next_val(cur_val):
for pos in range(len(cur_val)):
cur_val[pos]+=1
if cur_val[pos]<len(digits):
return
cur_val[pos]=0
cur_val.append(0)
def _get_val(cur_val):
digit_val=1
num_val=0
for x in cur_val:
num_val+=digits[x]*digit_val
digit_val*=10
return num_val
cur_val=[]
sum=0
while(True):
_next_val(cur_val)
num_val=_get_val(cur_val)
if num_val>max_val:
break
sum+=num_val
return sum
def main():
digits=[4,5,6]
max_val=666554
print(digits, max_val)
print(compute_sum(digits, max_val))
数学是好的，但并不是所有问题都可以轻松“压缩”，所以学会如何在没有数学的情况下处理它们也是值得的。
在这个问题中，求和很简单，困难在于有效地枚举需要相加的数字，乍一看。
“过滤”方法是一种可能性：逐步生成所有可能的数字，并过滤掉不匹配的数字；然而，它也相当低效（通常情况下）：
因此，我建议采用“生成”方法：只生成符合条件的数字（并且全部符合条件）。
我想指出，生成由4、5和6组成的所有数字就像计算（三进制）一样：
让我们用Python来实现，作为生成器：
def generator():
def convert(array):
i = 0
for e in array:
i *= 10
i += e
return i
def increment(array):
result = []
carry = True
for e in array[::-1]:
if carry:
e += 1
carry = False
if e > 6:
e = 4
carry = True
result = [e,] + result
if carry:
result = [4,] + result
return result
array = [4]
while True:
num = convert(array)
if num > 666554: break
yield num
array = increment(array)
使用sum(generator())可以打印结果：
$ time python example.py
409632209
python example.py 0.03s user 0.00s system 82% cpu 0.043 total
这里是同样的内容的C++版本。
从简单问题开始。——Polya
求由数字4、5和6组成的n位数的和。
正如Yu Hao上面解释的那样，这里有3**n个数字，它们的平均值是555555，因此总和为3**n * (10**n-1)*5/9。但如果你没有发现这一点，下面是另一种解决问题的方法。
这个问题具有递归结构，因此让我们尝试一个递归解决方案。设g(n)是所有恰好由n个数字456组成的数字的总和。然后我们有以下递推关系：
g(n) = (4+5+6)*10**(n-1)*3**(n-1) + 3*g(n-1)
g(2) = 44+45+46 + 54+55+56 + 64+65+66
= (40+50+60)*3 + 3*(4+5+6)
= (4+5+6)*10*3 + 3*g(n-1)
g(1) + g(2) + g(3) + g(4) + g(5) + g(6)。在Python中，可以使用动态规划实现：def sum456(n):
"""Find the sum of all numbers at most n digits which consist of 4,5,6 only"""
g = [0] * (n+1)
for i in range(1,n+1):
g[i] = 15*10**(i-1)*3**(i-1) + 3*g[i-1]
print(g) # show the array of partial solutions
return sum(g)
当n=6时
>>> sum456(6)
[0, 15, 495, 14985, 449955, 13499865, 404999595]
418964910
>>> sum456(6) - (666555 + 666556 + 666564 + 666565 + 666566 + 666644 + 666645 + 666646 + 666654 + 666655 + 666656 + + 666664 + 666665 + 666666)
409632209
9332701，为什么不直接使用 def sum456(): return 409632209 呢？ - SparK4 到 666666 的和为：
total = sum([15*(3**i)*int('1'*(i+1)) for i in range(6)])
>>> 418964910
666554和666666之间的几个数字的总和为：
rest = 666555+666556+666564+666565+666566+
666644+666645+666646+
666654+666655+666656+
666664+666665+666666
>>> 9332701
total - rest
>>> 409632209
public static long compute_sum(long[] digits, long max_val, long count[]) {
List<Long> cur_val = new ArrayList<>();
long sum = 0;
long mod = ((long)Math.pow(10,9))+7;
long num_val = 0;
while (true) {
_next_val(cur_val, digits);
num_val = _get_val(cur_val, digits, count);
sum =(sum%mod + (num_val)%mod)%mod;
if (num_val == max_val) {
break;
}
}
return sum;
}
public static void _next_val(List<Long> cur_val, long[] digits) {
for (int pos = 0; pos < cur_val.size(); pos++) {
cur_val.set(pos, cur_val.get(pos) + 1);
if (cur_val.get(pos) < digits.length)
return;
cur_val.set(pos, 0L);
}
cur_val.add(0L);
}
public static long _get_val(List<Long> cur_val, long[] digits, long count[]) {
long digit_val = 1;
long num_val = 0;
long[] digitAppearanceCount = new long[]{0,0,0};
for (Long x : cur_val) {
digitAppearanceCount[x.intValue()] = digitAppearanceCount[x.intValue()]+1;
if (digitAppearanceCount[x.intValue()]>count[x.intValue()]){
num_val=0;
break;
}
num_val = num_val+(digits[x.intValue()] * digit_val);
digit_val *= 10;
}
return num_val;
}
public static void main(String[] args) {
long [] digits=new long[]{4,5,6};
long count[] = new long[]{1,1,1};
long max_val= 654;
System.out.println(compute_sum(digits, max_val, count));
}
@gen-y-s的答案（https://dev59.com/E10Z5IYBdhLWcg3wlRMV#31286947）是错误的（它包括x=y=z=1时超出可用的4s、5s、6s的55、66、44）。它输出12189，但x=y=z=1时应该是3675。
@Yu Hao的逻辑（https://dev59.com/E10Z5IYBdhLWcg3wlRMV#31285816）与上述相同错误。它输出12189，但x=y=z=1时应该是3675。