Zahl aus Quadratzahl-Paaren < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:41 Mi 26.01.2011 | | Autor: | Ferma |
Hallo Forum,
ich versuche, eine Zahl zu finden, die aus 18 oder mehr verschiedenen Quadratzahl-Paaren besteht. Z.B.
5225=49+5476; 196+5329; 484+5041; 625+4900; 1681+3844; 2500+3025
Das sind leider nur 6 verschiedene Quadratzahl-Paar Summen.
Mit einem Programm(VBA) habe ich Zahlen gefunden, die 9 Q.-P. beinhalten. Ich bin bis 65000 vorgestoßen. Hat jemand eine Vorstellung von einem Programm, das "leichtfüßig" auch viel größere Zahlen testen kann?
VG Ferma
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:17 Mi 26.01.2011 | | Autor: | felixf |
Moin!
> Hallo Forum,
> ich versuche, eine Zahl zu finden, die aus 18 oder mehr
> verschiedenen Quadratzahl-Paaren besteht. Z.B.
> 5225=49+5476; 196+5329; 484+5041; 625+4900; 1681+3844;
> 2500+3025
> Das sind leider nur 6 verschiedene Quadratzahl-Paar
> Summen.
> Mit einem Programm(VBA) habe ich Zahlen gefunden, die 9
> Q.-P. beinhalten. Ich bin bis 65000 vorgestoßen. Hat
> jemand eine Vorstellung von einem Programm, das
> "leichtfüßig" auch viel größere Zahlen testen kann?
Schau dir mal diese Artikel an:
* http://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares
* http://mathworld.wolfram.com/SumofSquaresFunction.html (schau z.B. bei Formel Nr. 17)
* http://en.wikipedia.org/wiki/Arithmetic_function#Sums_of_squares
Mit der Formel Nr. 17 aus dem Wolfram-Artikel kannst du schnell bestimmen, auf wieviele Arten sich eine Zahl als Summe von zwei Quadraten darstellen laesst (du brauchst nur die Faktorisierung der Zahl zu kennen). Damit kannst du dir schnell eine Zahl konstruieren, die auf mind. 18 Arten darstellbar ist (indem du eine passende Primfaktorzerlegung hinschreibst), oder du laesst eine suchen die dies erfuellt.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 07:39 Do 27.01.2011 | | Autor: | Ferma |
Guten Morgen Felix,
die gesuchte Zahl muss also diese Form haben:
[mm] 2^*q1^1*q2^3*q3^3....
[/mm]
q1,q2,q3 sind Primzahlen der Form q=4k+1. Es dürfen auch Primzahlen der Form p=4k+3 vorkommen, aber nur zu einer geraden Potenz.
q1,q2,q3.... müssen ungerade Potenzen haben(b1,b2,b3...).
B=(b1+1)*(b2+1)*(b3+1)....Ich versuche es mit einer Zahl.
[mm] z=2*17^1*13^3*5^3
[/mm]
B=(1+1)*(3+1)*(3+1)=32 Dann ist die Anzahl der Quadratzahl-Paare B/2=16; z=9337250
Wie man jetzt die konkreten Quadratzahl-Paare findet ist mir bei der relativ großen Zahl noch unklar. Ist das bis her so richtig? Es reichen 16 Paare.
VG Ferma
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:38 Do 27.01.2011 | | Autor: | felixf |
Moin Ferma,
> die gesuchte Zahl muss also diese Form haben:
> [mm]2^*q1^1*q2^3*q3^3....[/mm]
wenn es vorne [mm] $2^0$ [/mm] heissen soll, geht das. Es gibt aber auch Zahlen, die nicht von dieser Form sind, und die trotzdem auch gehen.
> q1,q2,q3 sind Primzahlen der Form q=4k+1. Es dürfen auch
> Primzahlen der Form p=4k+3 vorkommen, aber nur zu einer
> geraden Potenz.
![[ok]](/images/smileys/ok.gif "[ok]")
> q1,q2,q3.... müssen ungerade Potenzen haben(b1,b2,b3...).
Wieso das?
> B=(b1+1)*(b2+1)*(b3+1)....Ich versuche es mit einer Zahl.
> [mm]z=2*17^1*13^3*5^3[/mm]
> B=(1+1)*(3+1)*(3+1)=32 Dann ist die Anzahl der
> Quadratzahl-Paare B/2=16; z=9337250
> Wie man jetzt die konkreten Quadratzahl-Paare findet ist
> mir bei der relativ großen Zahl noch unklar. Ist das bis
> her so richtig? Es reichen 16 Paare.
Naja, das ist doch jetzt echt nicht schwer. Der in der Frage ![[]](/images/popup.gif) hier skizzierte naive Algorithmus ist hier doch ziemlich schnell fertig, schliesslich ist [mm] $\sqrt{z/2} \approx [/mm] 2161$ ziemlich klein.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:36 Do 27.01.2011 | | Autor: | Ferma |
Guten Abend Felix,
die 16 Quadrat-Paare habe ich mit einem kleinen Programm ermitteln können. Ehrlich gesagt, ich habe die mathematische Prozedur für die Ermittlung der 16 Paare nicht verstanden. Die ermittelte Zahl war richtig.
Herzlichen Dank für die kompetente Hilfe!
Ferma
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:18 Fr 28.01.2011 | | Autor: | felixf |
Moin!
> Guten Abend Felix,
> die 16 Quadrat-Paare habe ich mit einem kleinen Programm
> ermitteln können. Ehrlich gesagt, ich habe die
> mathematische Prozedur für die Ermittlung der 16 Paare
> nicht verstanden. Die ermittelte Zahl war richtig.
Naja, so schwer ist es nicht 
Es muss ja [mm] $a^2 [/mm] + [mm] b^2 [/mm] = z$ sein.
Aufgeloest nach $b$: $b = [mm] \sqrt{z - a^2}$.
[/mm]
Du probierst also alle $a$ durch und schaust, wann $z - [mm] a^2$ [/mm] ein Quadrat in [mm] $\IZ$ [/mm] ist. In dem Fall hast du $b$ mit [mm] $a^2 [/mm] + [mm] b^2 [/mm] = z$.
Und wenn du $a [mm] \le [/mm] b$ annimmst, dann ist $z = [mm] a^2 [/mm] + [mm] b^2 \ge [/mm] 2 [mm] a^2$, [/mm] also $a [mm] \le \sqrt{z/2}$. [/mm] Es reicht also, $a = 0, [mm] \dots, \lfloor \sqrt{z/2} \rfloor$ [/mm] durchzuprobieren.
LG Felix
PS: [mm] $\lfloor \sqrt{n} \rfloor$ [/mm] fuer $n [mm] \in \IN$ [/mm] zu bestimmen und gleichzeitig testen ob $n$ ein Quadrat in [mm] $\IZ$ [/mm] ist geht uebrigens recht schnell in [mm] $O(\log^3 [/mm] n)$ Binaeroperationen. Dazu hatte ich hier mal etwas geschrieben.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:38 Fr 28.01.2011 | | Autor: | reverend |
Moin Felix,
durchprobieren ist doch langweilig, zumal wenn die (Mindest-)Zahl der Quadrataufteilungen schon bekannt ist.
Gibt es da keinen anderen Weg? Ich habe nur ein paar Minuten gesucht und auch gerade keine Lust auf mehr Einsatz, aber der aktuelle Stand ist für mich doch unbefriedigend.
Liebe Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 So 30.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
