Projekt Euler Problem 233
https://stackoverflow.com/questions/623435
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe beschlossen, Projekt Euler Problem 233 nächsten, aber ich angehen bin einige große Probleme haben! Ich habe einige Analysen durchgeführt und haben einige sehr schöne Fortschritte gemacht, aber ich habe jetzt stecken bleiben. Hier ist mein Arbeits:
Lemma 1 : Da der Kreis der 4 Eckpunkte durchläuft gibt es mindestens 4 Lösungen für jeden n. Aber für jeden Punkt auf dem Umfang gibt es 7 andere mit Reflexion gefunden. Deshalb gibt es immer 8k + 4 Gitterpunkte.
Lemma 2 : Der Kreis hat Radius (√2) n und das Zentrum (n / 2, n / 2), so dass ihre Gleichung (x-n / 2) ^ 2 + (y-n / 2) ^ 2 = [n / √2] ^ 2. Dies reduziert bis auf x ^ 2 + y ^ 2 = n (x + y).
Lemma 3 : Wenn eine Lösung von x ^ 2 + y ^ 2 = n (x + y) geschrieben wird (x, y, z), dann ist eine andere Lösung (kx, ky, kz). Der Beweis dafür ist:
(x+y)n = x^2+y^2
(kx)^2+(ky)^2 = (kx+ky)m
k(x^2+y^2) = (x+y)m
m = kn
Das war so viel wie ich mit dieser Linie des Denkens tat - ich konnte nicht überall sieht von dort aus zu gehen, aber es ist enthalten, weil es gut geeignet sein kann
.Mein nächster Gedanke war, die Mitte des Kreises zu bewegen. Es wird die gleiche Anzahl von Lösungen sei es in jeder Dimension eine ganze Zahl zu bewegen. Also, wenn n / 2 eine ganze Zahl ist, so n = 2k, x ^ 2 + y ^ 2 = 2 * k ^ 2. Und es stellt sich auch heraus, dass es zu dieser Gleichung ebenso viele Lösungen sind, wie es die Gleichung x ^ 2 + y ^ 2 = k ^ 2 (siehe Sloane A046109 ).
Das gibt auch eine einfache Methode zur Berechnung der Anzahl von Lösungen für jeden n über A046080 . Wenn die Kräfte auf den Primzahlen in n der Form 4k + 1 f [0] ... f [m], dann die Anzahl der Lösungen 4 * Produkt (2f [i] 1 | i in [0 .. .m]).
Das erlaubte mir, nach hinten zu arbeiten: 4.Product (2f [i] 1 | i in [0 ... m]) = 420, so Produkt (2f [i] 1 | i in [0 .. .m]) = 105 = 3 * 5 * 7. Ich konnte mit diesem Programm kommen, die ich denke, die Summe aller n findet, in Form 2k und weniger als 10 ^ 11, die 420 Kreisgitterpunkte. Die Antwort (hoffentlich!) Ist 257199853438240692.
Hier ist das C-Programm:
#include "stdlib.h"
#include "stdio.h"
#include "math.h"
#include "string.h"
#define lim 1000000000L
char prime[lim];
long primes[50000000];
long len = 0;
int main(void)
{
long i, j;
for(i = 0; i < lim; i++)
{
prime[i] = 1;
}
for(i = 2; i < lim; i++)
{
if(prime[i])
{
for(j = 2*i; j < lim; j += i) prime[j] = 0;
if((i-1)%4 == 0)
{
prime[i] = 2;
//printf("%li\n", i);
primes[len++] = i;
}
}
if(i < 1000 || (i < 10000 && i%1000 == 0) || i%10000 == 0) printf("%li, %li\n", i, len);
}
printf("primes!\n");
long a, b, c, v, total = 0, k;
for(a = 0; a < len; a++)
{
v = primes[a]*primes[a]*primes[a];
if(v > 50000000000L) break;
for(b = 0; b < len; b++)
{
if(b == a) continue;
v = primes[a]*primes[a]*primes[a]*primes[b]*primes[b];
if(v > 50000000000L) break;
for(c = 0; c < len; c++)
{
if(c == a) continue;
if(c == b) continue;
v = primes[a]*primes[a]*primes[a]*primes[b]*primes[b]*primes[c];
if(v > 50000000000L) break;
for(k = 1; k*v <= 50000000000L; k++)
{
if(prime[k] == 2) continue;
total += k*v;
}
}
}
}
for(a = 0; a < len; a++)
{
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a];
if(v > 50000000000L) break;
for(b = 0; b < len; b++)
{
if(b == a) continue;
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[b]*primes[b]*primes[b];
if(v > 50000000000L) break;
for(k = 1; k*v <= 50000000000L; k++)
{
if(prime[k] == 2) continue;
total += k*v;
}
}
}
for(a = 0; a < len; a++)
{
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a];
if(v > 50000000000L) break;
for(b = 0; b < len; b++)
{
if(b == a) continue;
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[b]*primes[b];
if(v > 50000000000L) break;
for(k = 1; k*v <= 50000000000L; k++)
{
if(prime[k] == 2) continue;
total += k*v;
}
}
}
printf("%li\n", 2*total);
return 0;
}
Wir müssen nur auf den Werten von n hinzufügen, die 420 Kreisgitterpunkte und sind in der Form 2k + 1 haben! Doch das scheint schwieriger als für n = 2k und ich kann nicht jede Methode für sie sehen. Ich bin auch ein wenig unsicher, ob meine Antwort noch n korrekt ist, da das Verfahren ziemlich verworren ist ... Kann es jemand bestätigen? Gibt es ein ordentliches Verfahren ohne anders unterschiedliche n Einbeziehung der Behandlung?
Ich bin ganz aus Ideen!
Ich bin meistens daran interessiert, wie ich mit N beschäftigen = 2k + 1 da, wenn N = 2k ich wie John Feminella schlägt tun können.
Lösung
Hinweis. 1: Der Kreis hat Radius n / √2, die nie eine ganze Zahl für Zahl n ist, so A046080 nie gelten
Tipp 2: Stören Sie nicht den Kreis um schieben. Wählen Sie ihn aus dem Millimeterpapier und nur darüber nachdenkt, den Platz, die es definiert, und die noch unbekannten Sehenswürdigkeiten auf dem Umfang in Beziehung zueinander stehen.
Hinweis 3: Der Winkel im Halbkreis eingeschrieben ist immer 90 Grad
.Tipp 4: Wie viele Möglichkeiten kann eine Zahl als Summe von zwei Quadraten geschrieben werden
Hinweis Bonus verwendet wird großzügig in ganz: Symmetrie
SPOILER ALERT!
Lesen Sie nicht weiter, bis Sie versuchen, es aus den Hinweisen zu erarbeiten, über
Wenn diese Hinweise nicht ausreichen, hier sind einige der fehlenden Schritte mit den Hinweisen verschachteln oben:
Hinweis 1.5:. Du gehst deinen Weg ändern müssen, um das Problem der Suche, da der Ansatz, den Sie auf einer fehlerhaften Prämisse wurden mit Basis
Hinweis 2.5: Denken Sie an einem Gitterpunkt auf der linken Seite des Bogens zwischen den oberen Ecken des Platzes. Durch die Symmetrie ist ein weiterer solcher Punkt unmittelbar rechts von ihm und einem direkt unter Drittel. Was kann sagen, Sie über den Abstand zwischen diesen Punkten und über die trangle bilden sie?
3.5 Hinweis: Wie kann man bestimmen, wie viele Gitterpunkte dort auf der linken Seite des Bogens zwischen den oberen Ecken des Platzes für jeden gegebenen n
?Andere Tipps
Tipp # 1. Ihre Lemma # 2 ist nicht ganz richtig. Sind Sie sicher, das ist der Radius?
Hint # 2. Die Antwort ist eng mit der Summe der Quadrate Funktion r (k, n) bezogen. Dies gibt die Anzahl der Möglichkeiten darzustellen n verschiedene Quadrate unter Verwendung von k, so dass Nullen und Unterscheidung zwischen Ordnung. Zum Beispiel, r (2, 5) 8 ist, weil es 8 Möglichkeiten 5 unter Verwendung von 2 Quadraten darzustellen:
(-2)^2 + (-1)^2
(-2)^2 + 1^2
2^2 + (-1)^2
2^2 + 1^2
... (and the 4 additional expressions produced by reversing these 2 terms)
Sie sehen, dass ein Kreis mit dem Radius p am Ursprung r zentriert (2, p ^ 2) Gitterpunkte hat. Zum Beispiel wird ein Kreis mit einem Radius von 5 hat:
(-4)^2 + (-3)^2
... and 7 others like this
5^2 + 0^2
(-5)^2 + 0^2
0^2 + 5^2
0^2 + (-5)^2
für insgesamt 12. Welche Arten von Zahlen würden 420 Kreisgitterpunkte haben? Was nun, wenn sie am Ursprung nicht in der Mitte? Ich lasse Sie nehmen es von hier aus.
Wenn Sie einen viel viel größer Hauch wollen, ich habe rot-13'd ( http://rot13.com ) etwas sollten Sie überprüfen hier:
uggc: //zngujbeyq.jbysenz.pbz/FpuvamryfGurberz.ugzy
können Sie beziehen sich auf http://oeis.org/A046109/b046109.txt zu überprüfen, bis zu 1000 I PARI / GP installiert und verwendet eine der PARI-Skripte hier: http://oeis.org/ A046109 überprüfen Zahlen höher.
