Удаление диакритических знаков/диакритических знаков от строки при сохранении других специальных символов (попробовал mb_chars.normalize и iconv),

Уравнения могут быть немного упрощены, чтобы облегчить вычисления.

Сначала вам нужно сохранить результаты вашего d (i), чтобы вам никогда не приходилось пересчитывать их. Найти d (i + 1) из d (i) легко, просто воспользуйтесь

Вторую пару циклов можно значительно упростить. Давайте рассмотрим S (5)

           i
       1     2     3     4     5
    1  d(1) d(2)  d(3)  d(4)   d(5)
    2  d(2) d(4)  d(6)  d(8)  d(10)
  j 3  d(3) d(6)  d(9)  d(12) d(15)
    4  d(4) d(8)  d(12) d(16) d(20)
    5  d(5) d(10) d(15) d(20) d(25)

Мы можем видеть, сколько значений пересчитывается. Во-первых, обратите внимание, как матрица симметрична относительно диагонали, давая экономию половины. Есть много других значений, пересчитанных.

Теперь, если мы посмотрим на отдельные члены в d (k). Сначала посмотрите на результаты для mod (k, i) для разных k и i

        i
     123456789
     ---------
 1 | 0
 2 | 00
 3 | 010
k4 | 0010
 5 | 01210
 6 | 000210
 7 | 0113210
 8 | 00203210
 9 | 010143210

Снова поможет кэширование значений. Деление является относительно дорогой операцией, поэтому определите функцию

f(m) = floor( 1 / ( 1 + m ) )

и используйте эту функцию с кэшированными результатами при вычислении d (k). Собственно давайте посчитаем значения f (m). Теперь f (0) = floor (1/1) = 1. f (1) = floor (1/2) = 0 и для любого m> 1 f (m) = 0.

Это значительно упрощает расчет. Нас в основном интересуют только случаи, когда mod (k, i) = 0. Это время, когда k кратно i.

Таким образом, d (k) является просто суммой факторов k.

Вместо того, чтобы пытаться найти факторы k, проще взглянуть на множители i.

for(i=1;i<N;++i) {
    // find multiples of i
    for(j=1;j<???;++j) {
       m = i * j;
       d(m) += i;
    }
 }

Теперь мы выяснили, что d (k) - сумма факторов k, мы можем упростить вычисления S (N).

В сущности, для данного фактора m мы хотим найти все случаи, когда m является фактором i * j.

Очевидно, 1 является фактором каждого числа, поэтому 1 встречается N N раз. 2 является фактором, если либо i, либо j четно. Произведение i j нечетное N / 2 * N / 2 раза, поэтому четное 3/4 N * N раз. (Я предполагал, что N четно)

Для 3, если мы рисуем умножение

*  1  2  3  4  5  6
1        3        6
2        6       12
3  3  6  9 12 15 18
4       12       24
5       15       30
6  6 12 18 24 30 36

и просто заполняем кратные 3. Мы видим, что есть (1 - 2/3 * 2/3) N * N кратно.

Аналогично, с 4 существует (1 - 3/4 * 3/4) N * N кратных.

Таким образом, все становится намного проще, если мы думаем о сложении количества кратных.