(no subject)
Apr. 9th, 2015 06:42 pmБолею, решил почитать старую книгу Пойя "Математика и правдоподобные рассуждения":
10. Проверяя предположение Гольдбаха для 2n = 60, мы последовательно испытывали простые числа p до n = 30. Однако мы могли бы также испытывать простые числа p между n = 30 и 2n = 60. Какой приём скорее всего окажется более выгодным для бóльших n?
(недоказанная до сих пор гипотеза Гольдбаха утверждает, что любое четное число, начиная с 4, можно представить в виде суммы двух простых)
( ответ )
Интересно, старик Пойя в 50-е годы совсем не думал о трудоемкости проверки на простоту?
Простой тест (правда, с самой примитивной проверкой простоты) дал обратный результат:
( Python )
10. Проверяя предположение Гольдбаха для 2n = 60, мы последовательно испытывали простые числа p до n = 30. Однако мы могли бы также испытывать простые числа p между n = 30 и 2n = 60. Какой приём скорее всего окажется более выгодным для бóльших n?
(недоказанная до сих пор гипотеза Гольдбаха утверждает, что любое четное число, начиная с 4, можно представить в виде суммы двух простых)
( ответ )
Интересно, старик Пойя в 50-е годы совсем не думал о трудоемкости проверки на простоту?
Простой тест (правда, с самой примитивной проверкой простоты) дал обратный результат:
( Python )
small 42.90952508
big 96.12519816