Ermitteln der Anzahl an Lösungen von quatratischen Gleichungen (Sieb von Atkin)

[Lonsdaleit]

Hallo,

ich habe bereits das Sieb des Eratosthenes implementiert.
Nun möchte ich das Sieb des Atkin ausprobieren.

Leider scheitere ich an einer performanten Lösung was die Gleichungen betrifft:

• Falls der Eintrag eine Zahl mit Rest 1, 13, 17, 29, 37, 41, 49, oder 53 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 4x² + y² = n.
• Falls der Eintrag eine Zahl mit Rest 7, 19, 31, oder 43 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3x² + y² = n.
• Falls der Eintrag eine Zahl mit Rest 11, 23, 47, oder 59 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3x² − y² = n, wobei x > y.

Wichtig ist hier nur die Anzahl der Lösungen.
Ich habe bisher einfach "Brute-Force" alle ganzen Zahlen für x und y ausprobiert:

        private static int checkEquation(int n){
		 //n = 4x²+y²
		 int count = 0;
		 for (int x=0; x<Math.sqrt(n);x++){
			 for (int y=0;y<Math.sqrt(n);y++){
				if (n==4*x*x+y*y){
					count++;
				}
			}
		}
		return count;
	}

Leider dauert dies für große Zahlen sehr lang.
Kann ich den zu überprüfenden Zahlenraum weiter einschränken?
Bei der 3ten Gleichung reicht es ja, y nur bis y<x durchlaufen zu lassen.

Es handelt sich bei den überprüften Zahlen n ja um solche mit bestimmten Modulo60 Resten. Dies sollte den Zahlenraum einschränken lassen - nur weiß ich leider nicht wie.

Um einen guten Denkanstoß wäre ich sehr dankbar!!

Gruß,
Lonsdaleit

 

[Konni]

Für 4x2 + y2 = 1 oder 5 mod 12

Verwende folgende Kombinationen:

x = 0, 1 mod 2 mit y =1, 5 mod 6

und x = 1, 2 mod 3 mit y = 3 mod 6

Das sind ca. halb so viele Kombinationen, als wenn man alle x und y nehmen würde.



Für 3x2 + y2 = 7 mod 12

Verwende folgende Kombinationen:

x = 1, mod 2 mit y = 2, 4 mod 6

Das sind 1/6 Kombinationen von Allen.



Für 3x2 - y2 = 11 mod 12

Verwende folgende Kombinationen:

x = 1 mod 2 mit y =2, 4 mod 6

und x = 0 mod 2 mit y = 1, 5 mod 6

Das sind 1/3 Kombinationen von Allen.

Diese Kombinationen erzeugen nur Lösungen für die richtigen Restklassen von n mod 12. Die Prüfung ob n in der Restklasse liegt, kann also entfallen.

Restklassen für x und y für n mod 60 würden zusätzlich 5, 25, 35 und 55 mod 60 ausschließen. Diese haben aber in vielen Fällen gar keine Lösung. Bsp. Bei 3x2 + y2 und 3x2 - y2 kann der Teiler 5 nur auftreten, wenn x und y den gemeinsamen Teiler 5 haben. Der Aufwand lohnt sich also nicht.

Die Kombinationen lassen sich sehr einfach nachprüfen: Erstelle eine Tabelle mit x und y von null bis 11 als Zeilen- und Spaltenüberschriften. (am besten vorsortiert: 1, 5, 7, 11, 3, 9, 0, 6, 2, 4, 8, 10) Berechne in der Tabelle die Gleichung mod 12.

Das Gleiche kann man auch mit n mod 60 machen.