波利亚猜想的一个反例

Question

Polya's conjecture是一个数学猜想，假设第一个（-1）^（Ω（n））的和，其中ω（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;

Answer 1

正如{}告诉你的那样，最初1958年的证据并不是用暴力来完成的。它也没有透露最小的违反规则的数字，它是1980年才发现的。我根本没有研究过这个案子，但1980年的证据可能是用电脑做的。这更多的是可用RAM的数量问题，而不是处理速度的问题。在

然而，在现代计算机中，用蛮力来解决这个问题应该不难。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:] & 1), dtype='int32')
print "Total time {0} s".format(time.time()-t0)

这不是最快或最优化的函数，其背后的数学原理应该非常明显。在我的机器（i7）中，运行在一个核心上，大约需要2800秒来计算全表的素数因子，最大可达1×10^9。（但请注意，在没有64位python和至少8gb RAM的情况下不要尝试此操作。累计和表消耗4 GB。）

为了证明上述函数至少能很好地工作，下面是一个有趣区域的图：

由于第一个数字有一些问题，上面代码给出的结果有点偏差。要获得正式的Liouville lambda求和，请使用cumulative[n-1] + 2。对于问题（906316571）中提到的数字，结果是cumulative[906316570] + 2等于829，这是该区域中的最大值。在