10 новых сказок о потерянном времени

Найдите логическую ошибку в коде выше.

while( i < j )
        {
            while ( i < j && vec[i].first + vec[j].first > e5 ) j--;
            if ( vec[i].first + vec[j].first == e5 )
            {
                bla bla = bla;
            }
            i++;
        }

Я правильно понимаю, что во втором случае условие выглядит так:

while ( 1 && vec[i].first + vec[j].first > e5 ) j--;

А ещё, не замедляет ли решение printf, как было в одной из предыдущих статей на эту тему?

Скажите, а есть примеры практического применения данного уравнения?

У вас во вложенных циклах считаются gcd. Разве этот вспомогательный алгоритм не увеличивает сложность вычисления?

Неплохая работа, идея с дискретным корнем весьма интересна.

Еще у меня есть дикая идея проверить все n вплоть до миллиона. Ожидаемое время проверки, в принципе, реальное — около миллиона ядрочасов

Имхо, рано ещё, лучше потратить несколько часов (или десятков) на улучшение алгоритма и оптимизацию кода и сэкономить сотни тысяч часов обогрева комнаты на cpu (или gpu) ;)
В частности, рекомендую пользоваться gcc или clang — там есть встроенная поддержка __uint128_t.

Пишут, что известны три решения:

Euler's conjecture was disproven by L. J. Lander and T. R. Parkin in 1966 when, through a direct computer search on a CDC 6600, they found a counterexample for k = 5. A total of three primitive (that is, in which the summands do not all have a common factor) counterexamples are known:

27^5 + 84^5 + 110^5 + 133^5 = 144^5 (Lander & Parkin, 1966),
(−220)^5 + 5027^5 + 6237^5 + 14068^5 = 14132^5 (Scher & Seidl, 1996), and
55^5 + 3183^5 + 28969^5 + 85282^5 = 85359^5 (Frye, 2004).

Если «вывернуть на изнанку» циклы, можно получить сортированный вектор сразу на этапе инициализации.
В этом можно убедиться на примере однострочника на баше:

# с использованием сортировки
for a in $(seq 1 9); do for b in $(seq $(($a+1)) 10); do echo -n "$a^5+$b^5 = "; echo "$a^5+$b^5" | bc; done; done | sort -n -k3

# без использования сортировки
for a in $(seq 2 10); do for b in $(seq 1 $((a-1))); do echo -n "$a^5+$b^5 = "; echo "$a^5+$b^5" | bc; done; done

Я полагаю это может убавить заметное время выполнения.

А нельзя было попытаться хардкорно оптимизировать №8?

Может я глупость скажу но нет ли смысла попробовать погонять алгоритм для чисел отличных от простых? Я просто на бумажке накидал: 27^5+84^5+110^5+133^5=144^5 если разложить числа на простые множители то получим:
27 = 3^3
84 = 2^2 * 3 * 7
110 = 2 * 5 * 7
133 = 7 * 19
144 = 2^4 * 3^2
т.е. все числа не простые. Аналогично я проверил для решения 55^5 + 3183^5 + 28969^5 + 85282^5 = 85359^5. Все числа так же раскладываются на простые множители.
Из этого я делаю «громкое» заключение что числа должны быть не простыми!
А теперь немного здравого смысла: если верить этому источнику, то от 1 до 3000 мы имеем 430 простых чисел — 14%. Итого эффективность алгоритма может возрасти примерно на 14 %))

a^5+b^5 = (a+b)(a^4-a^3b+a^2b^2-ab^3+b^4)
Вдруг это поможет для нового метода :)

У нас есть два сервера для всяких расчетов. Один (Xeon E7-4850 — 4 CPUs, 40 cores, 128 Gb memory) сейчас свободен, поетому я решил поставить погонять эту программу.

С использованием OpenMP — 40 threads, 100% CPU:



#10:

n=20000 — 783 sec = чуть больше, чем 10 мин, т.е. примерно в 5 раз быстрее, чем в статье.

Я поставил для n=100000, завтра утром будет готово (у нас сейчас вечер)

У нас есть второй сервер (прям щас занят), в котором 48 «взрослых» cores и, кажется, 192 Гб.
Так, что если кому-то надо, то свистите, я могу на выходние поставить — кидайте код.

Артем, спасибо за текст. Вдохновляет. А гипотезу Била уже решили? Там хотя бы миллион можно получить)