Блог

Гипотеза Поля — это математическая гипотеза, которая предполагает, что сумма первого (-1) ^(Omega (n)), где Omega (n) — число простых делителей числа n с кратностью, всегда отрицательна или равна нулю.

Встречный пример — 906316571, был найден пятьдесят лет назад. Интересно, как они могли это найти, потому что это занимает огромное количество времени, я пытался оптимизировать свой алгоритм Python, но это все еще занимает много времени, можете ли вы помочь мне оптимизировать его?

Вот мой код (я использовал запоминание)

  >>> class Memoize:
def __init__(self, f):
    self.f = f
    self.memo = {}
def __call__(self, *args):
    if not args in self.memo:
        self.memo[args] = self.f(*args)
    return self.memo[args]

 >>> def sieve(m):
n=m 1;
s=[];
for i in range(2,n):
    s.append(i);
k=0;
while k<len(s):
    for i in range(2,int(n/s[k]) 1):
        x=i*s[k];
        if s.count(x)==1:
            s.remove(x);
    k=k 1;
return s;
>>> s=sieve(100000);
>>> def omega(n):
k=0;
if n==1:
    return 0;
else :
    while k<len(s) and n%s[k]!=0 :
        k=k 1;
    if k<len(s):
        return omega(int(n/s[k])) 1;
    else :
        return 1;
>>> omega=Memoize(omega)
>>> def polya(n):
h=omega(n);
if n==1:
    return 0;
else :
    if omega(n)%2==0:
        return polya(n-1) 1;
    else :
        return polya(n-1)-1;
>>> polya=Memoize(polya);
>>> while polya(k)<=0 :
k=k 1;
  

Как chepner я уже говорил вам, первоначальное доказательство 1958 года не было выполнено с помощью грубой силы. Он также не выявил наименьшего числа, нарушающего правило, оно было найдено только в 1980 году. Я вообще не изучал этот случай, но доказательство 1980 года, возможно, было сделано с помощью компьютера. Это скорее вопрос объема доступной оперативной памяти, а не вопрос скорости обработки как таковой.

Однако на современных компьютерах не должно быть слишком сложно подойти к проблеме с помощью грубой силы. Python здесь не лучшая альтернатива, но все же числа можно найти за разумное время.

 import numpy as np
import time

max_number = 1000000000

# array for results
arr = np.zeros(max_number, dtype='int8')

# starting time
t0 = time.time()

# some tracking for the time spent
time_spent = []

# go through all possible numbers up to the larges possible factor
for p in range(2, int(np.sqrt(max_number))):
    # if the number of factors for the number > 0, it is not a prime, jump to the next
    if arr[p] > 0:
        continue
    # if we have a prime, we will have to go through all its powers < max_number
    n = p
    while n < max_number:
         # increment the counter at n, 2n, 3n, ...
        arr[n::n]  = 1
        # take the next power
        n = n * p
    # track the time spent

print "Time spent calculating the table of number of factors: {0} s".format(time.time()-t0)

# now we have the big primes left, but their powers are not needed any more
# they need to be taken into account up to max_number / 2
j = 0
for p in range(p   1, (max_number   1) / 2):
    if arr[p] > 0:
        continue
    arr[p::p]  = 1
    if j % 10000 == 0:
        print "{0} at {1} s".format(p, time.time()-t0)
    j  = 1

print "Primes up to {0} done at {1} s".format(p, time.time()-t0)
# now we have only big primes with no multiples left, they will be all 1
arr[arr == 0] = 1

print "Factor table done at {0} s".format(time.time() - t0)

# calculate the odd/even balance, note that 0 is not included and 1 has 0 factors
cumulative = np.cumsum(1 - 2 * (arr[1:] amp; 1), dtype='int32')
print "Total time {0} s".format(time.time()-t0)
  

Это не самая быстрая или наиболее оптимизированная функция, математика, стоящая за этим, должна быть совершенно очевидной. На моей машине (i7), работающей на одном ядре, требуется примерно 2800 секунд, чтобы вычислить полную таблицу числа простых множителей с точностью до 1 x 10 ^ 9. (Но будьте осторожны, не пытайтесь использовать это без 64-разрядного python и по крайней мере 8 ГБ оперативной памяти. Таблица совокупных сумм занимает 4 ГБ.)

Чтобы доказать, что вышеупомянутая функция работает, по крайней мере, довольно хорошо, вот график интересной области:

Из-за некоторых проблем с первыми числами результаты, приведенные в приведенном выше коде, немного неточны. Чтобы получить официальную итоговую лямбду Лиувилля, используйте cumulative[n-1] 2 . Для числа, упомянутого в вопросе (906 316 571), результат cumulative[906316570] 2 равен 829, что является максимальным значением в регионе.