Goldbachsche Vermutung für die ersten 20 000 Zahlen

[Sarah1111]

Hallo zusammen

ich möchte die Goldbachsche Vermutung für die ersten 20 000 geraden natürlichen Zahlen testen (Die Goldbachsche Vermutung besagt, dass sich jede gerade natürliche Zahl n ∈N mit n > 2 als Summe von zwei Primzahlen schreiben lässt ).
Bisher habe ich das Untenstehende. Leider weiß ich aber nicht, welchen Befehl ich bei dem "elif"-teil angeben muss, damit k nicht nur die nächste Zahl ist, sondern die nächste Primzahl aus der prime_range(2, 20001, 2). Kann mir da jemand helfen?

Code: Alles auswählen

Bereich = [range(2,20001,2)]    # zu überprüfende Zahlenrange
GoldbachZahlen = []             #leere Liste, in denen später die Zahlen angegeben werden, die die Goldbachsche Vermutung bestätigen

for k in prime_range(2,20001,2):
    
    if ((n-k).is_prime() and n in Bereich):
        GoldbachZahlen.append(k+(n-k))
        
    elif k+=1 in...                                  #k soll zur nächsten Zahl in prim_range(...) ???

    
set(GoldbachZahlen)                               #lasse mir die Liste der Goldbachzahlen in einer Menge angeben

print(set(GoldbachZahlen))

[__blackjack__]

@Sarah1111: Bitte bitte arbeite endlich mal ein Grundlagentutorial durch. Das hier ist doch schon wieder alles geraten. Du musst die Grundlagen wie ``for``-Schleifen verstehen, bevor Du anfangen kannst damit Probleme zu lösen. Das Du denkst ``k +=1`` in der Schleife würde Sinn machen, sagt aber ziemlich deutlich, dass Du ``for``-Schleifen nicht verstanden hast. Lass doch mal den Schleifeninhalt weg und ersetze ihn einfach nur durch die Ausgabe von `k`. Denn offenbar hakt es Da schon beim Verständnis was diese Schleife macht und welche Werte `k` annimmt.

`n` ist nirgends definiert. Ganze Zahlen in Python haben keine `is_prime()`-Methode. ``n in Bereich`` bedeutet ganz sicher nicht das was Du denkst was das bedeutet.

Je länger Du Dich dagegen wehrst Deine Aufgabe erst einmal zu vergessen und die Grundlagen durch zu arbeiten, um so länger wird sich das hinziehen. Ohne die Grundlagen geht es nicht.

[__blackjack__]

Nachtrag: Ich habe gerade gelernt das SageMath-Dateien nicht auf *.py sondern auf *.sage enden, und das sich das teilweise anders verhält als Python. Zum Beispiel werden literale ganze Zahlen offensichtlich automatisch in `Integer`-Objekte verpackt, womit es dann doch eine `is_prime()`-Methode gibt. ``7 .is_prime()`` ergibt tatsächlich `True`. Allerdings ergibt auch ``n >= 0`` einen ``TypeError`` wenn ``n = int`` ist, obwohl SageMath tatsächlich noch auf Python 2.7 setzt. Du zeigst hier also Code im Forum der ganz am Anfang auf die Nase fällt, ohne das zu erwähnen und hast Fragen zu späteren Teilen im Quelltext.

Auch die SageMath-Dokumentation hat etwas zu Grundlagen und Programmieren (Kontroll- und Datenstrukturen). Sogar auf Deutsch. Das wäre wohl das erste was man mal durcharbeiten sollte – die Grundlagentutorials zu der Software die man verwendet. Programmieren durch raten funktioniert nicht, falls das nicht schon mal gesagt wurde.

[__blackjack__]

@Sarah1111: Vielleicht noch ein allgemeiner Hinweis zum Programmieren: Statt alles in einem Stück lösen zu wollen, teilt man ein Problem normalerweise in kleinere Teilprobleme auf. Und diese Teilprobleme dann wieder in Teilprobleme. Solange bis man Teilprobleme hat, die sich jeweils mit einer Funktion mit ein paar Zeilen Code leicht lösen lassen. Und so eine Funktion für eine Teillösung schreibt und testet man dann. Wenn die funktioniert wie sie soll, macht man mit der nächsten Funktion weiter. Dann kann man Teillösungen mit Funktionen zu grösseren Teillösungen zusammenfügen. Solange bis man das Gesamtproblem gelöst hat.

Eine Aufteilung die sich oft anbietet ist wenn man etwas für viele Elemente machen muss, eine Funktion zu schreiben die ein Teilproblem für *ein* Element löst. Wenn man die hat, kann man eine Funktion schreiben, die diese Funktion für jedes Element aufruft und die Teillösungen zu einer Lösung für alle Elemente zusammenfasst.

Hier wäre das beispielsweise eine Funktion die für *eine* Zahl prüft ob sie als Summe von zwei Primzahlen darstellbar ist und entsprechend `True` oder `False` zurück gibt. Wenn man diese Funktion hat, kann man sie für alle Zahlen aufrufen die man prüfen möchte und testen ob sie für alle `True` liefert. Dabei können die Funktionen `all()` und `map()` beziehungsweise `itertools.imap()` sehr nützlich sein. Die finale Prüfung wäre mit einer `is_sum_of_two_primes()` folgender Einzeiler: ``all(imap(is_sum_of_two_primes, even_numbers))``, mit einer entsprechenden Definition von `even_numbers`.

[__blackjack__]

Folgendes BASIC-Programm sagt, her Goldbach hat recht mit seiner Vermutung – für ganze, gerade Zahlen bis 20.000:

Code: Alles auswählen

Function IsPrime (n As Integer) As Boolean
  If n < 2 Then Return False
  If n = 2 Then Return True
  If n And 1 = 0 Then Return False
  For i As Integer = 3 To Sqr(n) Step 2
    If n Mod i = 0 Then Return False
  Next
  Return True
End Function

Function IsSumOfTwoPrimes (n As Integer) As Boolean
  For i As Integer = 2 To n \ 2
    If IsPrime(i) Then If IsPrime(n - i) Then Return True
  Next
  Return False
End Function

Function AllEvensAreTheSumOfTwoPrimes (a As Integer, b As Integer) As Boolean
  Assert(a Mod 2 = 0) : Assert(a > 2) : Assert(a <= b)
  For n As Integer = a To b Step 2
    If Not IsSumOfTwoPrimes(n) Then Return False
  Next
  Return True
End Function

If AllEvensAreTheSumOfTwoPrimes(4, 20000) Then
  Print "Juhuu!"
Else
  Print "Ooooh!"
End If

Ist mit FreeBASIC getestet. Ist zwar alles andere als effizient, aber für den relativ kleinen Zahlbereich trotzdem auf moderner Hardware schnell berechnet.

[__blackjack__]

Aus Neugier hatte ich das gestern noch mal für alte Hardware nach QBasic portiert und auf meinem DOS-Rechner laufen lassen – lief für die 20.000 Zahlen knapp unter einer halben Minute.

Code: Alles auswählen

DECLARE FUNCTION IsPrime% (n AS INTEGER)
DECLARE FUNCTION IsSumOfTwoPrimes% (n AS INTEGER)
DECLARE FUNCTION AllEvensAreTheSumOfTwoPrimes% (a AS INTEGER, b AS INTEGER)

DIM start AS SINGLE

start = TIMER
IF AllEvensAreTheSumOfTwoPrimes(4, 20000) THEN
  PRINT "Juhuu!"
ELSE
  PRINT "Ooooh!"
END IF
PRINT "Laufzeit:"; TIMER - start; "Sekunden."

FUNCTION AllEvensAreTheSumOfTwoPrimes% (a AS INTEGER, b AS INTEGER)
  DIM n AS INTEGER, result AS INTEGER
 
  result = -1
  FOR n = a TO b STEP 2
    IF NOT IsSumOfTwoPrimes(n) THEN
      result = 0
      EXIT FOR
    END IF
  NEXT
  AllEvensAreTheSumOfTwoPrimes = result
END FUNCTION

FUNCTION IsPrime% (n AS INTEGER)
  DIM i AS INTEGER, result AS INTEGER

  IF n < 2 THEN
    result = 0
  ELSEIF n = 2 THEN
    result = -1
  ELSEIF n AND 1 = 0 THEN
    result = 0
  ELSE
    result = -1
    FOR i = 3 TO SQR(n) STEP 2
      IF n MOD i = 0 THEN
        result = 0
        EXIT FOR
      END IF
    NEXT
  END IF

  IsPrime = result
END FUNCTION

FUNCTION IsSumOfTwoPrimes% (n AS INTEGER)
  DIM i AS INTEGER, result AS INTEGER

  result = 0
  FOR i = 2 TO n \ 2
    IF IsPrime(i) THEN
      IF IsPrime(n - i) THEN
        result = -1
        EXIT FOR
      END IF
    END IF
  NEXT
  IsSumOfTwoPrimes = result
END FUNCTION

Also flugs ein Sieb nach Eratosthenes dazu programmiert, und es läuft in knapp unter vier Sekunden.

Code: Alles auswählen

DECLARE SUB InitIsPrime ()
DECLARE FUNCTION IsSumOfTwoPrimes% (n AS INTEGER)
DECLARE FUNCTION AllEvensAreTheSumOfTwoPrimes% (a AS INTEGER, b AS INTEGER)

CONST UpperLimit = 20000
DIM start AS SINGLE
DIM SHARED IsPrime(UpperLimit) AS INTEGER

start = TIMER
InitIsPrime
IF AllEvensAreTheSumOfTwoPrimes(4, UpperLimit) THEN
  PRINT "Juhuu!"
ELSE
  PRINT "Ooooh!"
END IF
PRINT "Laufzeit:"; TIMER - start; "Sekunden."

FUNCTION AllEvensAreTheSumOfTwoPrimes% (a AS INTEGER, b AS INTEGER)
  DIM n AS INTEGER, result AS INTEGER
 
  result = -1
  FOR n = a TO b STEP 2
    IF NOT IsSumOfTwoPrimes(n) THEN
      result = 0
      EXIT FOR
    END IF
  NEXT
  AllEvensAreTheSumOfTwoPrimes = result
END FUNCTION

SUB InitIsPrime
  DIM i AS INTEGER, j AS INTEGER

  IsPrime(2) = -1
  FOR i = 3 TO UBOUND(IsPrime) STEP 2
    IsPrime(i) = -1
  NEXT
  FOR i = 3 TO SQR(UBOUND(IsPrime)) STEP 2
    IF IsPrime(i) THEN
      FOR j = i * i TO UBOUND(IsPrime) STEP i
        IsPrime(j) = 0
      NEXT
    END IF
  NEXT
END SUB

FUNCTION IsSumOfTwoPrimes% (n AS INTEGER)
  DIM i AS INTEGER, result AS INTEGER

  result = 0
  FOR i = 2 TO n \ 2
    IF IsPrime(i) THEN
      IF IsPrime(n - i) THEN
        result = -1
        EXIT FOR
      END IF
    END IF
  NEXT
  IsSumOfTwoPrimes = result
END FUNCTION

Interessant an BASIC ist hier die Entscheidung für Funktionsaufrufe und Arrayzugriffe die gleiche Art von Klammern zu verwenden, so das man beim Wechsel von einer `IsPrime`-Funktion zu einem `IsPrime`-Array mit vorberechneten Ergebnissen an den Aufrufen, bzw. dann Zugriffen, nichts ändern muss.

[__blackjack__]

So könnte eine Lösung mit SageMath als PDF exportiert aussehen: forum_goldbach.pdf.