13 + k*(2p)²

Fytch

knivil schrieb:

Es ist wahrscheinlich nur noetig, eine sinnvolle obere Abschaetzung fuer n zu finden und dann alle n durchzuprobieren.

so hab ich das gelöst für n ≤ 256, hat immer unterschiedliche werte gegeben je nach n (vermutlich weil gewisse vielfache erst in dem bereich gefunden werden (und gewisse erst noch später)). nicht viel nach 256 ist mir dann der speicher für mein sieb ausgegangen. ( std::vector<bool> kann eigentlich std::numeric_limits<std::size_t>::max() * std::numeric_limits<unsigned char>::digits einträge speichern, klappt aber mit dem indizieren nicht, muss wohl die tage einen eigenen dynamischen bitvector schreiben.)

edit:
f(n + 1) - f(n) erhöht sich immer um 2. das kann man in einer sekunde sieben bis 10^7 * 256. alle primzahlen bis 10^7 sind auch augenblicklich gesiebt. dann hab ich die vielfache der quadrate der primzahlen im ersten sieb gesucht und bedingt addiert.

knivil

Hmm, klingt gut, ein Sieb fuer n^2 - 3n -1.

Columbo

Das durchprobieren aller n's halte ich mit geeignetem Schema fuer unproblematisch.

Tatsächlich? Das überrascht mich.

f(n + 1) - f(n) erhöht sich immer um 2.

Hä? Die erste Ableitung ist doch von n abhängig?

Man kann aber tatsächlich in jedem Schritt n - 3 draufaddieren...

#include <iostream>
#include "NumberTheoryAlgorithms.hxx"

unsigned R( unsigned const p )
{
	unsigned n = p;
	unsigned const p_square = p*p;
	unsigned f_n = p_square - 3*p - 1;

	while( n != p + 1000000 )
	{
		if( f_n % p_square == 0 )
			return n;

		f_n += 2*n - 2; // Hier wird der neue Funktionswert berechnet.
		++n;
	}

	return 0;
}

int main()
{
	unsigned sum = 0;
	for( auto p : createPrimeTable(10000u) )
		sum += R(p);

	std::cout << sum;
}

Braucht auf meinem corei7 knapp 0.7 Sekunden... das ist viel zu lange.
Also ist die Idee nun, eine Lookup-Tabelle für die Funktion zu machen?

knivil

Arcoth schrieb:

Das durchprobieren aller n's halte ich mit geeignetem Schema fuer unproblematisch.

Tatsächlich? Das überrascht mich.

Alle n's ist wahrscheinlich missverstaendlich. Bei Primzahltest mit Rad werden auch nicht alle n getestet. Das meine ich mit geeignetem Iterationsschema.

Und wenn man dann mod p^2 erreicht hat, dann startet man in der Modulo-Uhr mit einem Shift. Wie sieht also dieser Shift aus und wie verschiebt er die NST des Polynoms.

Fytch

vorab:
f(4) = 3
f(5) = 9
f(6) = 17
f(7) = 27

Arcoth schrieb:

Man kann aber tatsächlich in jedem Schritt n - 3 draufaddieren...

so wie ich das verstehe liegst du falsch. ich verstehe dich so, dass:
f(n) = f(n - 1) + n - 3
f(4) = 3
f(5) ≠ f(4) + n - 3 = 3 + 5 - 3 = 5

ich hab erhalten:
f(n) = f(n - 1) + 2(n - 2)
f(4) = 3
f(5) = f(4) + 2(n - 2) = 3 + 2(5 - 2) = 9

Arcoth schrieb:

Also ist die Idee nun, eine Lookup-Tabelle für die Funktion zu machen?

bei einer look-up-table müsstest du binär suchen. bei einem sieb kannst du direkt indizieren. ausserdem kann ich mir vorstellen, dass das sieb platzeffizienter ist (da bin ich mir aber nicht sicher).

die idee geht weiter, dass man schaut, ob die vielfachen der quadrate der primzahlen im sieb der funktion vorkommen (das ist ja die bedingung für f(n) mod p^2 = 0). das hab ich so auch implementiert aber selbst bei x = 256 in x*p^2 hab ich nicht die richtige lösung erhalten. das hab ich aber schon geschrieben.

die idee die knivil im letzten post angedeutet hat ist bestimmt richtiger und besser als mein iterativer ansatz. mir fällt leider keine methode ein mit der man bestimmen kann mit ob das polynom mod p^2 überhaupt 0 ergeben kann. ansonsten könnte man die kombination der polynomlösungen und der primzahlen, bei denen das nicht möglich ist, aussondern und den rest iterativ lösen. das iterieren ist mit einem sieb für alle möglichkeiten in 1 bis 2 sekunden möglich, das stellt nicht das problem dar.

edit: rechtschreibungsfehler...

Columbo

Guck mal in meinen Code.

f(5) = f(4) + 2*4-2
f(5) = 3 + 6 = 9

f(6) = f(5) + 2*5-2
f(6) = 9 + 8 = 17

f(7) = 17 + 2*6-2 = 27

Fytch

Arcoth schrieb:

Guck mal in meinen Code.

achso, ja klar. dann liegt der fehler bei mir, ich habe es falsch verstanden.

Columbo

Wäre es nicht einfacher, das so anzugehen, als wäre es eine quadratische Kongruenz-Gleichung?

Damit ergibt sich
n^2 - 3n - 1 \equiv 0 \pmod{p^2}
Wenn man pq anwendet
n = \frac{3 ± \sqrt{13}}{2}
Dann muss noch die Wurzel von 13 Modulo $p^2$ gefunden werden...

Columbo

Vielleicht interessieren jemanden diese Werte; für p=11 wurden folgende n ausprobiert, Ergebnis der Divisionsreste:

Die Werte sind vollkommen symmetrisch, mit dem "Spiegel" bei n=62.

Für p=13:

Symmetrie bei n=86. Wirkt zusammenhanglos.... lässt sich aber bei allen bisher ausprobierten Primzahlen finden...

otze

divisionrest von was?

Columbo

otze schrieb:

divisionrest von was?

Es geht um $f(n) \quad mod \quad p^2$ , wobei $f(n) = n^2 - 3n - 1$ und p eine Primzahl ist.