13 + k*(2p)²



  • Hi,

    kann ich (effizient) prüfen, welches k dazu führt, dass
    13+k(2p)213 + k(2p)^2
    Eine Quadratzahl ist?
    p ist hierbei bekannt und eine Primzahl.
    Wenn es mehrere gibt, einfach das kleinste. Die "doofe" Methode, einfach alle Werte ab 1 durch zu probieren und bei einem bestimmten Limit abzubrechen, kann einfach nicht die beste Methode sein.

    Wikipedia-Links wären schon eine große Hilfe.



  • k muss jedenfalls ungerade sein:
    13+k(2p)213 + k(2p)^2 ist immer ungerade
    und alle ungeraden Quadratzahlen lassen sich in der Form 8n+1 darstellen.



  • camper schrieb:

    k muss jedenfalls ungerade sein:
    13+k(2p)213 + k(2p)^2 ist immer ungerade

    Edit: Ah, ich verstehe.
    Es gilt
    (12+k(2p)2)mod8=0(12 + k(2p)^2) \quad mod \quad 8 = 0
    Und damit muss k ungerade sein, damit k(2p)2k(2p)^2 nicht durch acht teilbar ist (sondern nur durch vier).

    und alle ungeraden Quadratzahlen lassen sich in der Form 8n+1 darstellen.

    Danke, das wusste ich noch nicht.

    ~
    Edit^x: Diese nervigen Formatierungsfehler... ich sollte öfter die Posts nochmal anschauen bevor ich abschicke..~



  • Um den Kontext zu geben: Es geht um das neue Project-Euler Problem, ich habe es so umgeformt:
    n23n1=kp2n^2 - 3n - 1 = k * p^2
    n23n(1+kp2)=0n^2 - 3n - (1 + k * p^2) = 0
    pq-Formel:
    n=3+9+4(1+kp2)2n = \frac{3 + \sqrt{9 + 4*(1 + k * p^2)}}{2}
    n = \frac{3 + \sqrt{13 + 4\*k\*p^2)}}{2}
    n=3+13+k(2p)2)2n = \frac{3 + \sqrt{13 + k*(2p)^2)}}{2}
    Nun gilt es eigentlich nur noch, k zu finden. Und da die Wurzel ganzzahlig sein muss...
    Aber wenn selbst camper nicht einfällt, wie man das löst, dann ist das wohl der falsche Ansatz. Ich dachte, das im OP gestellte wäre ein allgemeines Problem mit einer allgemein bekannten Lösung...



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

    Nun gilt es eigentlich nur noch, k zu finden.

    Du willst gar nicht k, du willst n. Insbesondere willst du wissen, ob ein n existiert. Das durchprobieren aller n's halte ich mit geeignetem Schema fuer unproblematisch.

    Andererseits ist es Nummer 457, da braucht man vielleicht mehr ... bspw. Primfaktoren von n in Relation zu p.



  • 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.



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



  • 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?



  • 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.



  • 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...



  • 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



  • Arcoth schrieb:

    Guck mal in meinen Code.

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



  • 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 p2p^2 gefunden werden...



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

    12: 107
    13: 8
    14: 32
    15: 58
    16: 86
    17: 116
    18: 27
    19: 61
    20: 97
    21: 14
    22: 54
    23: 96
    24: 19
    25: 65
    26: 113
    27: 42
    28: 94
    29: 27
    30: 83
    31: 20
    32: 80
    33: 21
    34: 85
    35: 30
    36: 98
    37: 47
    38: 119
    39: 72
    40: 27
    41: 105
    42: 64
    43: 25
    44: 109
    45: 74
    46: 41
    47: 10
    48: 102
    49: 75
    50: 50
    51: 27
    52: 6
    53: 108
    54: 91
    55: 76
    56: 63
    57: 52
    58: 43
    59: 36
    60: 31
    61: 28
    62: 27
    63: 28
    64: 31
    65: 36
    66: 43
    67: 52
    68: 63
    69: 76
    70: 91
    71: 108
    72: 6
    73: 27
    74: 50
    75: 75
    76: 102
    77: 10
    78: 41
    79: 74
    80: 109
    81: 25
    82: 64
    83: 105
    84: 27
    85: 72
    86: 119
    87: 47
    88: 98
    89: 30
    90: 85
    91: 21
    92: 80
    93: 20
    94: 83
    95: 27
    96: 94
    97: 42
    98: 113
    99: 65
    100: 19
    101: 96
    102: 54
    103: 14
    104: 97
    105: 61
    106: 27
    107: 116
    108: 86
    109: 58
    110: 32
    111: 8
    112: 107
    

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

    Für p=13:

    23: 121
    24: 165
    25: 42
    26: 90
    27: 140
    28: 23
    29: 77
    30: 133
    31: 22
    32: 82
    33: 144
    34: 39
    35: 105
    36: 4
    37: 74
    38: 146
    39: 51
    40: 127
    41: 36
    42: 116
    43: 29
    44: 113
    45: 30
    46: 118
    47: 39
    48: 131
    49: 56
    50: 152
    51: 81
    52: 12
    53: 114
    54: 49
    55: 155
    56: 94
    57: 35
    58: 147
    59: 92
    60: 39
    61: 157
    62: 108
    63: 61
    64: 16
    65: 142
    66: 101
    67: 62
    68: 25
    69: 159
    70: 126
    71: 95
    72: 66
    73: 39
    74: 14
    75: 160
    76: 139
    77: 120
    78: 103
    79: 88
    80: 75
    81: 64
    82: 55
    83: 48
    84: 43
    85: 40
    86: 39
    87: 40
    88: 43
    89: 48
    90: 55
    91: 64
    92: 75
    93: 88
    94: 103
    95: 120
    96: 139
    97: 160
    98: 14
    99: 39
    100: 66
    101: 95
    102: 126
    103: 159
    104: 25
    105: 62
    106: 101
    107: 142
    108: 16
    109: 61
    110: 108
    111: 157
    112: 39
    113: 92
    114: 147
    115: 35
    116: 94
    117: 155
    118: 49
    119: 114
    120: 12
    121: 81
    122: 152
    123: 56
    124: 131
    125: 39
    126: 118
    127: 30
    128: 113
    129: 29
    130: 116
    131: 36
    132: 127
    133: 51
    134: 146
    135: 74
    136: 4
    137: 105
    138: 39
    139: 144
    140: 82
    141: 22
    142: 133
    143: 77
    144: 23
    145: 140
    146: 90
    147: 42
    148: 165
    149: 121
    

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



  • divisionrest von was?



  • otze schrieb:

    divisionrest von was?

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


Log in to reply