algorithm - 用大量和数计算一个总和

Question

有一个任务是计算一个总和，summands 是bin 中有偶数个 1 的数字，每个数字都是 4 的幂。问题是最后一个 summand 是 2 ⁶⁴，所以通常的计算需要很长时间。我认为动态编程在这里可以提供帮助，但我不知道如何在这里使用它。

这是一个例子：

请问，谁能帮我解决这个问题？

Answer 1

这是计算价值的方法。

您为上限的二进制表示中的每个位数迭代计算该值。对于每个位数，分别计算其二进制表示中具有偶数个 1 的数字和具有奇数个 1 的数字的 1 到 4 度的总和。有了这些值，您应该能够计算 n+1 的值，其中 n 是二进制表示中的位数。

以下是关于如何做到这一点的一些观察：如果您有第 k 次数字的总和与偶数个 1，然后将其乘以 2^k，您将得到这些数字的总和加倍。这些数字仍然会有偶数个。实际上，每个具有 n 位数字且具有偶数个 1 的数字要么是具有 n-1 位数字且具有偶数个 1 的倍数，要么是 x * 2 + 1 其中 x 是具有奇数个 1 并且具有 n - 1 位数。因此，在其二进制表示中具有偶数个 1 且具有 n 位的数字的第 k 度的总和是Se(n,k) = 2^k * Se(n-1, k) + Sum(a : number with odd number of ones and n-1 digits){(2*a + 1)^k}。这里我用 Se 来表示偶数个数的总和。现在有趣的部分是第二个总和。它可以使用二项式公式计算：

(2*a + 1)^k = 2^k*a*k + combination(1,k)*(2*a)^(k-1) + ... 1 所以重组后你有： Sum(a : number with odd number of ones and n digits){(2*a + 1)^k} = 2^k*So(n-1,k) + combination(1, k) * 2^(k-1)*So(n-1,k) + combination(2, k) * 2^(k-2)*So(n-1,k) + ...

现在，如果您假设您已经为 n-1 计算了 So（二进制表示中具有奇数个数字的总和），您也可以计算这个总和。

您必须为 So(n,k) 编写类似的公式：

So(n,k) = 2^k*(So(n-1, k)) + Sum(a : 偶数个和 n-1 位的数字){(2*a + 1)^k

请记住，您必须为 k = 1, ... 4 计算此值，以便您可以将它们用于下一次迭代。只有一个音符 - 对于 So(n, 1)，你有 So(n, 1) = So(n-1,1)*2 + Se(n-1,1)*2 + 1，类似 Se(n, 1 ) = Se(n-1, 1) * 2 + So(n-1, 1)。

Using these formulas you should be able to compute the value you need quite fast. You need to sum Se(1,4) + Se(2,4) + ... Se(64, 4). The algorithm will work for values quite higher then the given constraints. Please note that the value you are searching for will not fit in any "regular" integer type. You will need to use some kind of BigInteger implementation.

Hope this answers your question.

Answer 2

There's a formula to calculate the sum of the powers of 4 of all integers from 1 to n:

sum(k⁴) _{for 1<=k<=n} = (6*n⁵ + 15*n⁴ + 10*n³ - n) / 30

在您的问题中，您只需要总结 4 的幂，这些幂在其二进制表示中具有偶数个。而且这个公式不排除具有奇数个1的k。

但是，我的直觉告诉我，具有奇数个 1 的 4 个 k 的幂和应该与具有偶数个 1 的 4 个 k 的幂和大致相同。

事实证明，如果你计算一系列 k 的这两个总和，这些总和偶尔会完全相同，每 32 k 出现一次：

n=   0 OddSum=                   0 EvenSum=                   0 = =
n=   1 OddSum=                   1 EvenSum=                   0  
n=   2 OddSum=                  17 EvenSum=                   0  
n=   3 OddSum=                  17 EvenSum=                  81  
n=   4 OddSum=                 273 EvenSum=                  81  
n=   5 OddSum=                 273 EvenSum=                 706  
n=   6 OddSum=                 273 EvenSum=                2002  
n=   7 OddSum=                2674 EvenSum=                2002  
n=   8 OddSum=                6770 EvenSum=                2002  
n=   9 OddSum=                6770 EvenSum=                8563  
n=  10 OddSum=                6770 EvenSum=               18563  
n=  11 OddSum=               21411 EvenSum=               18563  
n=  12 OddSum=               21411 EvenSum=               39299  
n=  13 OddSum=               49972 EvenSum=               39299  
n=  14 OddSum=               88388 EvenSum=               39299  
n=  15 OddSum=               88388 EvenSum=               89924  
n=  16 OddSum=              153924 EvenSum=               89924  
n=  17 OddSum=              153924 EvenSum=              173445  
n=  18 OddSum=              153924 EvenSum=              278421  
n=  19 OddSum=              284245 EvenSum=              278421  
n=  20 OddSum=              284245 EvenSum=              438421  
n=  21 OddSum=              478726 EvenSum=              438421  
n=  22 OddSum=              712982 EvenSum=              438421  
n=  23 OddSum=              712982 EvenSum=              718262  
n=  24 OddSum=              712982 EvenSum=             1050038  
n=  25 OddSum=             1103607 EvenSum=             1050038  
n=  26 OddSum=             1560583 EvenSum=             1050038  
n=  27 OddSum=             1560583 EvenSum=             1581479  
n=  28 OddSum=             2175239 EvenSum=             1581479  
n=  29 OddSum=             2175239 EvenSum=             2288760  
n=  30 OddSum=             2175239 EvenSum=             3098760  
n=  31 OddSum=             3098760 EvenSum=             3098760 = =
n=  32 OddSum=             4147336 EvenSum=             3098760  
n=  33 OddSum=             4147336 EvenSum=             4284681  
n=  34 OddSum=             4147336 EvenSum=             5621017  
n=  35 OddSum=             5647961 EvenSum=             5621017  
n=  36 OddSum=             5647961 EvenSum=             7300633  
n=  37 OddSum=             7522122 EvenSum=             7300633  
n=  38 OddSum=             9607258 EvenSum=             7300633  
n=  39 OddSum=             9607258 EvenSum=             9614074  
n=  40 OddSum=             9607258 EvenSum=            12174074  
n=  41 OddSum=            12433019 EvenSum=            12174074  
n=  42 OddSum=            15544715 EvenSum=            12174074  
n=  43 OddSum=            15544715 EvenSum=            15592875  
n=  44 OddSum=            19292811 EvenSum=            15592875  
n=  45 OddSum=            19292811 EvenSum=            19693500  
n=  46 OddSum=            19292811 EvenSum=            24170956  
n=  47 OddSum=            24172492 EvenSum=            24170956  
n=  48 OddSum=            24172492 EvenSum=            29479372  
n=  49 OddSum=            29937293 EvenSum=            29479372  
n=  50 OddSum=            36187293 EvenSum=            29479372  
n=  51 OddSum=            36187293 EvenSum=            36244573  
n=  52 OddSum=            43498909 EvenSum=            36244573  
n=  53 OddSum=            43498909 EvenSum=            44135054  
n=  54 OddSum=            43498909 EvenSum=            52638110  
n=  55 OddSum=            52649534 EvenSum=            52638110  
n=  56 OddSum=            62484030 EvenSum=            52638110  
n=  57 OddSum=            62484030 EvenSum=            63194111  
n=  58 OddSum=            62484030 EvenSum=            74510607  
n=  59 OddSum=            74601391 EvenSum=            74510607  
n=  60 OddSum=            74601391 EvenSum=            87470607  
n=  61 OddSum=            88447232 EvenSum=            87470607  
n=  62 OddSum=           103223568 EvenSum=            87470607  
n=  63 OddSum=           103223568 EvenSum=           103223568 = =
n=  64 OddSum=           120000784 EvenSum=           103223568  
...
n=4062 OddSum=  110517674755433207 EvenSum=  110790187795938168  
n=4063 OddSum=  110790187795938168 EvenSum=  110790187795938168 = =
n=4064 OddSum=  111062969223019384 EvenSum=  110790187795938168  
n=4065 OddSum=  111062969223019384 EvenSum=  111063237807788793  
n=4066 OddSum=  111062969223019384 EvenSum=  111336556602699529  
n=4067 OddSum=  111336556999378505 EvenSum=  111336556602699529  
n=4068 OddSum=  111336556999378505 EvenSum=  111610413558992905  
n=4069 OddSum=  111610683334189626 EvenSum=  111610413558992905  
n=4070 OddSum=  111885079246199626 EvenSum=  111610413558992905  
n=4071 OddSum=  111885079246199626 EvenSum=  111885079246980586  
n=4072 OddSum=  111885079246199626 EvenSum=  112160014909822442  
n=4073 OddSum=  112160285082869867 EvenSum=  112160014909822442  
n=4074 OddSum=  112435761292440443 EvenSum=  112160014909822442  
n=4075 OddSum=  112435761292440443 EvenSum=  112435761691463067  
n=4076 OddSum=  112711778845418619 EvenSum=  112435761691463067  
n=4077 OddSum=  112711778845418619 EvenSum=  112712050215144108  
n=4078 OddSum=  112711778845418619 EvenSum=  112988609908991164  
n=4079 OddSum=  112988609908992700 EvenSum=  112988609908991164  
n=4080 OddSum=  112988609908992700 EvenSum=  113265712541951164  
n=4081 OddSum=  113265984311095421 EvenSum=  113265712541951164  
n=4082 OddSum=  113543630682195597 EvenSum=  113265712541951164  
n=4083 OddSum=  113543630682195597 EvenSum=  113543631082001485  
n=4084 OddSum=  113821821591246733 EvenSum=  113543631082001485  
n=4085 OddSum=  113821821591246733 EvenSum=  113822094560202110  
n=4086 OddSum=  113821821591246733 EvenSum=  114100830807798926  
n=4087 OddSum=  114100830808584494 EvenSum=  114100830807798926  
n=4088 OddSum=  114380113196106030 EvenSum=  114100830807798926  
n=4089 OddSum=  114380113196106030 EvenSum=  114380386566045167  
n=4090 OddSum=  114380113196106030 EvenSum=  114660215895655167  
n=4091 OddSum=  114660216297816991 EvenSum=  114660215895655167  
n=4092 OddSum=  114660216297816991 EvenSum=  114940592970302463  
n=4093 OddSum=  114940867546334192 EvenSum=  114940592970302463  
n=4094 OddSum=  115221793169753088 EvenSum=  114940592970302463  
n=4095 OddSum=  115221793169753088 EvenSum=  115221793169753088 = =
...

在没有正式证明的情况下，我建议答案是：

((6*n ⁵ + 15*n ⁴ + 10*n ³ - n) / 30) / 2

其中n=2 ⁶⁴ -1。