题目159：因子的数根之和

欧拉计划

Digital root sums of factorisations

A composite number can be factored many different ways. For instance, not including multiplication by one, 24 can be factored in 7 distinct ways:

  24 = 2x2x2x3
  24 = 2x3x4
  24 = 2x2x6
  24 = 4x6
  24 = 3x8
  24 = 2x12
  24 = 24

Recall that the digital root of a number, in base 10, is found by adding together the digits of that number, and repeating that process until a number is arrived at that is less than 10. Thus the digital root of 467 is 8.

We shall call a Digital Root Sum (DRS) the sum of the digital roots of the individual factors of our number.
The chart below demonstrates all of the DRS values for 24.

The maximum Digital Root Sum of 24 is 11.
The function mdrs(n) gives the maximum Digital Root Sum of n. So mdrs(24)=11.
Find ∑mdrs(n) for 1 < n < 1,000,000.

题目：

一个合数能有很多种因子分解方式。比如说，在不包括 1 的乘积，24 可以有七种不同的分解方式如下：

    24 = 2x2x2x3
    24 = 2x3x4
    24 = 2x2x6
    24 = 4x6
    24 = 3x8
    24 = 2x12
    24 = 24

回想下，一个 10 进制数字的数根，是把它各个位的数字相加，并重复这个过程，直到这个数字小于 10。


我们把DRS叫做数字独立因子的数根之和。下表展示了 24 的所有 DRS 值。

24 的 DRS 值中，最大的是 11。

定义 mdrs(n) 为 n 的最大 DRS 值，因此，mdrs(24) = 11


对于 1 < n < 1,000,000，求∑mdrs(n)。

gunjang

def getDigitalRoot(n):
    if n < 10: return n
    r = 0
    while n >= 10:
        r += n%10
        n //= 10
    r += n
    return getDigitalRoot(r)

#maximum Digital Root Sum
mdrs1M = [getDigitalRoot(x) for x in range(0,10**6+1)] #2-4s
mdrs1M[10] = 7 # 10=2*5,2+5=7  =>now [1..10] is correct
x = 10
while True:  #求[x+1, 2*x]:
    m = min(10**6, 2*x)
    # print(x+1,"-",2*x," i=[2 -", int(m**0.5),"]")
    for i in range(2, int(m**0.5)+1):
        # if x <=20: print("i=",i,"j=",max(i,(x+1)//i), (m//i))
        for j in range(max(i,(x+1)//i), (m//i)+1):
            mdrs1M[i*j] = max(mdrs1M[i*j], mdrs1M[i] + mdrs1M[j])
    x *= 2
    if m == 1000000:
        break
print("1000=",mdrs1M[1000])
print("24=",mdrs1M[24])
# 1 < n <1000,000
print(sum(mdrs1M[2:1000000])) #14489159

永恒的蓝色梦想

gunjang 发表于 2020-7-15 20:32

欢迎答题！
你没有加代码格式，我帮你加了一下

guosl

对于一个整数n，其数字根有一个计算公式：drs(n) =  (n-1) % 9+1
对于一个整数n的最大数字根可以通过递归式：mdrs(n) = max(mdrs(a)+mdrs(b)) 对所有 a*b=n)
故本题可以应用类似筛法的方法，通过不停修改mdrs(n)的值来得到。

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1000000;

int mdrs[N];

int main(void)
{
  for (int i = 2; i < N; ++i)
    mdrs[i] =(i - 1) % 9 + 1; //初值
  for (int i = 2; i < N; ++i) //通过类似筛法的方法不停修改mdrs
    for (int j = 2, k; (k = i*j) < N; ++j)
      mdrs[k] = max(mdrs[k], mdrs[i] + mdrs[j]);//获得更大的值
  int nSum = 0;
  for (int i = 2; i < N; ++i)
    nSum += mdrs[i];
  printf("%d\n", nSum);
  return 0;
}