Ein Gegenbeispiel für die Vermutung von Polya

Question

Polyas Vermutung ist eine mathematische Vermutung, die besagt, dass die Summe der ersten (-1)^(Omega(n)) wobei Omega(n) die Anzahl der Primfaktoren von n mit Vielfachheit ist, immer negativ oder null ist.

Ein Gegenbeispiel ist 906316571, das vor fünfzig Jahren gefunden wurde. Ich frage mich, wie sie es gefunden haben, weil es eine massive Menge Zeit benötigt, Ich habe versucht, meinen Python-Algorithmus zu optimieren, aber es dauert immer noch eine massive Zeit, können Sie mir helfen, ihn zu optimieren?

Hier ist mein Code (Ich habe Memoisierung verwendet)

 >>> 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>> s=sieve(100000);
>>> def omega(n):
k=0;
if n==1:
    return 0;
else :
    while k>> 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

Wie chepner Ihnen mitgeteilt hat, wurde der ursprüngliche Beweis aus dem Jahr 1958 nicht mit Brute Force durchgeführt. Es hat auch nicht die kleinste Zahl offenbart, um die Regel zu brechen; diese wurde erst 1980 gefunden. Ich habe den Fall überhaupt nicht studiert, aber der Beweis von 1980 wurde möglicherweise mit einem Computer durchgeführt. Es handelt sich mehr um die Menge an verfügbarem RAM als um die Verarbeitungsgeschwindigkeit an sich.

Mit modernen Computern sollte es jedoch nicht übermäßig schwierig sein, das Problem mit Brute Force anzugehen. Python ist hier nicht die beste Alternative, aber die Zahlen können dennoch in angemessener Zeit gefunden werden.

import numpy as np
import time

max_number = 1000000000

# Array für Ergebnisse
arr = np.zeros(max_number, dtype='int8')

# Startzeit
t0 = time.time()

# Verfolgung der verbrachten Zeit
time_spent = []

# Gehe alle möglichen Zahlen bis zum größten möglichen Faktor durch
for p in range(2, int(np.sqrt(max_number))):
    # Wenn die Anzahl der Faktoren für die Zahl > 0 beträgt, ist sie keine Primzahl, springe zur nächsten
    if arr[p] > 0:
        continue
    # Wenn wir eine Primzahl haben, müssen wir durch alle ihre Potenzen < max_number gehen
    n = p
    while n < max_number:
         # Zähler bei n, 2n, 3n, ... erhöhen
        arr[n::n] += 1
        # zur nächsten Potenz übergehen
        n = n * p
    # Verfolge die verbrachte Zeit

print "Zeit für die Berechnung der Tabelle der Anzahl der Faktoren: {0} s".format(time.time()-t0)

# Jetzt haben wir noch die großen Primzahlen übrig, aber ihre Potenzen werden nicht mehr benötigt
# sie müssen bis max_number / 2 berücksichtigt werden
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} bei {1} s".format(p, time.time()-t0)
    j += 1

print "Primzahlen bis {0} bei {1} s".format(p, time.time()-t0)
# Jetzt haben wir nur noch große Primzahlen ohne Mehrfache übrig, sie sind alle 1
arr[arr == 0] = 1

print "Faktortabelle bei {0} s erstellt".format(time.time() - t0)

# Berechne das Verhältnis von ungeraden/geraden Zahlen, beachte dass 0 nicht enthalten ist und 1 hat 0 Faktoren
kumulativ = np.cumsum(1 - 2 * (arr[1:] & 1), dtype='int32')
print "Gesamtzeit {0} s".format(time.time()-t0)

Dies ist nicht die schnellste oder optimierteste Funktion, die Mathematik dahinter sollte ziemlich offensichtlich sein. Auf meinem Computer (i7) führt es auf einem Kern etwa 2800 Sekunden dauern, um die volle Tabelle der Anzahl der Primfaktoren bis 1 x 10^9 zu berechnen. (Aber Vorsicht, versuchen Sie dies nicht ohne 64-Bit-Python und mindestens 8 GB RAM. Die kumulative Summentabelle benötigt 4 GB.)

Um zu beweisen, dass die obige Funktion zumindest recht gut funktioniert, hier ist ein Plot des interessanten Bereichs:

Aufgrund einiger Probleme mit den ersten Zahlen sind die Ergebnisse, die der obige Code liefert, leicht ungenau. Um die offizielle Summatoria Liouville Lambda zu erhalten, verwenden Sie kumulativ[n-1] + 2. Für die in der Frage genannte Zahl (906 316 571) beträgt das Ergebnis kumulativ[906316570] + 2 und entspricht 829, was der Maximalwert in der Region ist.