Große Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 13:50 Fr 17.09.2010 | | Autor: | Ferma |
Hallo Forum,
kann dieses Problem mathematisch oder mittels Programmierung gelöst werden?
Gesucht die größte Quadratzahl, welche jede Ziffer so viele Male enthält, wie deren Wert ist. Beispiel: 543345144355225 ist eine Quadratzahl und enthält 5 Mal die 5, 4 Mal die 4, 3 Mal die 3, 2 Mal die 2 und einmal die 1.
Allerdings hat die gesuchte Zahl 45(!) Stellen. (Die Summe aller Zahlen von 1 bis 9)
Viele Grüße, Ferma
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:34 Sa 18.09.2010 | | Autor: | felixf |
Moin!
> kann dieses Problem mathematisch oder mittels
> Programmierung gelöst werden?
> Gesucht die größte Quadratzahl, welche jede Ziffer so
> viele Male enthält, wie deren Wert ist. Beispiel:
> 543345144355225 ist eine Quadratzahl und enthält 5 Mal die
> 5, 4 Mal die 4, 3 Mal die 3, 2 Mal die 2 und einmal die 1.
> Allerdings hat die gesuchte Zahl 45(!) Stellen. (Die Summe
> aller Zahlen von 1 bis 9)
Natuerlich laesst sich das ganze mit einem Programm loesen. Die Frage ist eher, wie lange das dauert.
Ein naives Programm probiert einfach alle Zahlen durch, die 9 mal die 9, 8 mal die 8, ... als Ziffern haben, und testet ob es Quadrate sind. Testen ob eine Zahl mit $n$ Bits ein Quadrat ist kann man in [mm] $O(\log^3 [/mm] n)$ Bitoperationen ganz naiv machen. (Ganzzahlige Approximation der Wurzel finden per binaerer Suche, das Ergebnis quadrieren und mit der urspruenglichen Zahl vergleichen.) (Oder man macht es zahlentheoretischer; siehe weiter unten in meiner Antwort.)
Es bleibt also die Frage, wieviel Kombinationen es gibt. Die Antwort ist [mm] $\binom{45}{1,2,3,4,5,6,7,8,9} [/mm] = [mm] \frac{45!}{1! 2! 3! \cdots 9!}$ [/mm] (das ist ein ![[]](/images/popup.gif) Multinomialkoeffizient).
Das ist gleich 65191584694745586153436251091200000, also eine ziemlich grosse Zahl. Alle diese Kombinationen durchzugehen dauert also viel zu lange. Aber es ist moeglich 
Man kann das ganze natuerlich jetzt mit dem Wissen kombinieren, wie Quadrate modulo 10, 100, 1000, ... aussehen. Die letzte Ziffer kann z.B. nur 0, 1, 4, 5, 6, 9 sein. Modulo 1000 gibt es z.B. nur 159 Quadrate. Und modulo [mm] $10^6$ [/mm] gibt es 78132 Quadrate. Diese kann man z.B. tabulieren und schon hat man sich auf unter 8% des Suchraums beschraenkt. Das hilft noch nicht wirklich viel, da es immer noch zu viele Moeglichkeiten sind, aber man kann hier noch weiter optimieren.
Eine Moeglichkeit ist z.B., kraeftig zu prunen, indem man alles modulo [mm] $10^n$ [/mm] prueft. Zuerst waehlt man die letzte Ziffer. Dann die vorletzte, und zwar so, dass die letzten beiden ein Quadrat modulo 100 sind. Dann waehlt man die drittletzte, so dass das ganze ein Quadrat modulo 1000 ist, etc.
Damit sollte schon viel mehr rausfallen. Pruefen, ob etwas modulo [mm] $10^n$ [/mm] ein Quadrat ist, kann man wie folgt: dazu muss es modulo [mm] $2^n$ [/mm] und modulo [mm] $5^n$ [/mm] ein Quadrat sein. Mit dem Henselschen Lemma zeigt man schnell, dass es ausreicht, wenn es modulo [mm] $2^n$ [/mm] und modulo 5 ein Quadrat ist. Und das modulo 5 kann man sehr schnell testen: die letzte Ziffer muss 0, 1, 4, 5, 6, 9 sein.
Bleibt also das testen modulo [mm] $2^n$. [/mm] Das ist etwas schwieriger, aber auch nicht so schwer: eine ungerade Zahl $a [mm] \in \IZ$ [/mm] ist genau dann modulo [mm] $2^n$ [/mm] (mit $n [mm] \ge [/mm] 3$) ein Quadrat, wenn $a [mm] \equiv [/mm] 0, 1 [mm] \pmod{8}$ [/mm] ist. Eine gerade Zahl muss man erst als Produkt einer Zweierpotenz und einer ungeraden Zahl schreiben, um genauere Aussagen treffen zu koennen, das ist aber auch nicht schwer herzuleiten.
Ich weiss nicht wie schnell das Ergebnis dann ist, aber ich vermute mal wesentlich schneller als die optimierte naive Methode.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:29 Sa 18.09.2010 | | Autor: | Ferma |
Guten Morgen,
eigentlich sind nur die Zahlen von 11060445038765649355157 bis 31622776599926972380056 zu untersuchen. das sind die kleinste und die größte Zahl, deren Quadrat die gesuchte Zahl beinhaltet. Das lässt sich optimal nur mittels Programmierung lösen. In VBA-Excel finde ich keinen Datentyp, der mit so großen Zahlen zurecht kommt. Vielleicht "Matlab"?
For a=z1 To z2
s=CStr((CDec(a)*CDec(a))
if Len(s)-Len(Replace(s,9,""))=9 Then
.
.
.
if Len(s)-Len(s,1,""))=1 Then
in etwa so könnte das Programm aussehen. Kann jemand weiterhelfen?
VG, Ferma
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:06 Sa 18.09.2010 | | Autor: | Sigma |
Hallo Ferma,
ich glaube die Arbeit kannst du dir sparen.
Die Quersumme deiner Quadratzahl ist [mm] $\sum _{n=1}^9 n^2=285$. [/mm] Jetzt kommen die Teilbarkeitsregeln ins Spiel.
Eine natürliche Zahl n ist genau dann durch 3 bzw. 9 teilbar, wenn ihre Quersumme q(n) ohne Rest durch 3 bzw. 9 teilbar ist.
285 ist ohne Rest durch 3 teilbar, damit ist auch deine Quadratzahl [mm] n=m^2 [/mm] durch 3 teilbar. Wenn deine Quadratzahl durch 3 Teilbar ist, dann auch m da 3 eine Primzahl ist. Also ersetzen wir m=3k. Damit ist n = [mm] m^2 [/mm] = [mm] (3k)^2 [/mm] = [mm] 9k^2 [/mm] durch 9 teilbar. Da die Quersumme von n aber nicht durch 9 ohne Rest teilbar ist kann keine Quadratzahl mit Quersumme 285 existieren.
mfg sigma
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:49 Sa 18.09.2010 | | Autor: | Ferma |
Hallo Sigma,
gut, dann ist das mit der Zahl, welche 9 Mal die 9 beinhaltet klar. ich suche nämlich die größte Zahl mit dieser Eigenschaft(1x die 1, 2x die 2....)Dann ist das mit 8 Mal die 8 auch klar. Quersumme 204 teilbar durch 6, nicht teilbar durch 9. Die Lösung rückt dann näher. Die Zahlen befinden sich zwischen 1223334444555556666667777777 und 7777777666666555554444333221. Die Quadrate der Zahlen zwischen 34976198257608 und 88191709738878 müssten geprüft werden. Das ist immer noch viel. hat jemand eine Vorstellung, wie das "zu Lebzeiten" gelöst werden kann. Das Programm müsste recht schnell sein!
VG, Ferma
|
|
|
| |
|
Hallo Ferma,
es ist [mm] \summe_{i=1}^{n}i^2=\bruch{n(n+1)(2n+1)}{6}
[/mm]
Für n=7 ergibt sich also 140.
Weiter gilt [mm] 140\equiv 5\mod{9}.
[/mm]
Es gibt aber [mm] \mod{9} [/mm] nur die quadratischen Reste 0,1,4,7.
Also kann die "Siebenerzahl" auch keine Quadratzahl sein.
Dass diese etwas erweiterte Neunerprobe aber die Fünfer- und Sechserzahl nicht ausschließt, wirst Du auch schon gefunden haben.
***
Wie man schneller vorgeht als mit einem "naiven" Test, hat Felix hier doch schon angedeutet.
Übrigens wäre selbst für die Siebenerzahl die Mühe noch hinreichend übersichtlich, sie hätte ja nur die Größenordnung [mm] x*10^{27} [/mm] (mit 1<x<10). Die zu prüfenden Quadrate sind dann entsprechend höchstens [mm] y*10^{13} [/mm] mit [mm] \wurzel{10}
Außer dem Hinweis von Felix kannst Du Dir aus der Betrachtung der quadratischen Reste [mm] \mod{9} [/mm] (s.o.) aber auch noch erschließen, dass die Wurzel der gesuchten Sechserzahl [mm] \mod{9} [/mm] nur 1 oder 8 sein kein, die der Fünferzahl ebenso.
Die von Felix genannte Einschränkung (Hensel) ist noch weiter zu verschärfen, wenn Du von hinten ausgehend die Zahl aufbaust und derweil die verwendeten Ziffern mitzählst, Nullen natürlich ausschließt etc.
Ich vermute, dass Du so den Suchaufwand so auf unter 1% reduzieren kannst, also bei der Sechserzahl nur eine Größenordnung von [mm] 3*10^8 [/mm] Zahlen zu untersuchen hast.
Das ist innerhalb eines Lebens bequem auf dem PC zu schaffen.
Bei geeigneter Programmierung sollte das sogar innerhalb eines Bruchteils eines Tages gehen.
dieser Absatz ist editiert. Ich war in Gedanken noch bei der nicht existenten Siebenerzahl. Sorry.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:06 So 19.09.2010 | | Autor: | Ferma |
Guten Morgen,
mit der "Sechserzahl" hat es wunderbar geklappt. Mein Programm brauchte gerade 13 Sekunden, um die 21-stellige Quadratzahl zu finden! Da war allerdings auch Glück dabei, weil die Zahl sehr nahe an dem oberen Limit war.
Ist es richtig, dass die größtmögliche Quadratzahl, mit der Einschränkung, dass keine 1 und keine 2 in der Zahl sind, die 42-stellige Zahl ist, die 9 Mal die 9, 8 Mal die 8......3 Mal die 3 beinhaltet, ist? Die Quersumme ist 280. Mod 9 dieser Zahl ist 1. Und wenn das so ist, ist diese Zahl mit dem PC in übersichtlicher Zeit zu ermitteln?
VG, Ferma
|
|
|
| |
|
Hallo Ferma
> mit der "Sechserzahl" hat es wunderbar geklappt. Mein
> Programm brauchte gerade 13 Sekunden, um die 21-stellige
> Quadratzahl zu finden! Da war allerdings auch Glück dabei,
> weil die Zahl sehr nahe an dem oberen Limit war.
Was meinst du mit dem bestimmten Artikel "die" in
"die 21-stellige Quadratzahl" ?
Mich würde auch interessieren, wie die Zahl lautet, die du
gefunden hast - und mit welcher Methode du sie gesucht
hast.
> Ist es richtig, dass die größtmögliche Quadratzahl, mit
> der Einschränkung, dass keine 1 und keine 2 in der Zahl
> sind, die 42-stellige Zahl ist, die 9 Mal die 9, 8 Mal die
> 8......3 Mal die 3 beinhaltet, ist? Die Quersumme ist 280.
> Mod 9 dieser Zahl ist 1. Und wenn das so ist, ist diese
> Zahl mit dem PC in übersichtlicher Zeit zu ermitteln?
> VG, Ferma
Hier hast du aus den modulo-Einschränkungen offenbar
eine notwendige Bedingung aufgestellt: "wenn alle Ziffern
von 9 bis hinunter zur 3 dabei sind, dann kann weder die 2
noch die 1 oder beide zusammen auch noch dabei sein".
Diese notwendige Bedingung ist aber möglicherweise nicht
hinreichend für die Existenz einer derartigen 42-stelligen
Quadratzahl. Da es aber in der Menge der [mm] 9*10^{41}
[/mm]
42-stelligen Zahlen etwa $\ [mm] 1.5*10^{30}$ [/mm] Zahlen mit dem angegebenen
Ziffern-Mix (9-mal die 9, ..... , 3-mal die 3) gibt (ich nenne
solche Zahlen jetzt einmal "Mixzahlen" und etwa [mm] 6.8*10^{20} [/mm] Quadratzahlen,
besteht wohl doch eine große Wahrscheinlichkeit, dass sich
unter den Mixzahlen auch Quadratzahlen befinden -
allerdings nur dann, wenn wir nicht noch weitere wesentliche
Einschränkungen übersehen haben ...
Effektiv können wir also doch nur eine obere Schranke
angeben, nämlich: eine Quadratzahl der gewünschten
Art kann höchstens 42 Stellen haben, muss also kleiner
als [mm] 10^{42} [/mm] sein.
LG Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:57 Mo 20.09.2010 | | Autor: | Ferma |
das ist mein Makro:
Public Sub GroesstesQuadrat()
Dim L As Variant, t!, s$
t = Timer 'etwa 13 Sek !!!
For L = 25819886828# To 11060445038# Step -1
s = CStr(CDec(L) * CDec(L))
If Len(s) - Len(Replace(s, 6, "")) = 6 Then
If Len(s) - Len(Replace(s, 5, "")) = 5 Then
If Len(s) - Len(Replace(s, 4, "")) = 4 Then
If Len(s) - Len(Replace(s, 3, "")) = 3 Then
If Len(s) - Len(Replace(s, 2, "")) = 2 Then
If Len(s) - Len(Replace(s, 1, "")) = 1 Then
MsgBox s [mm] '666565445353163422564=25817928758^2
[/mm]
Exit Sub
End If: End If: End If: End If: End If: End If
Next
MsgBox Round(Timer - t, 2)
End Sub
Hier habe ich eine Zahl gesucht, die alle Ziffern von 1 bis 6 beinhaltet, das ergibt eine 21-stellige Zahl. Mein nächstes Ziel ist, eine größere Zahl zu suchen. Darin müssen nicht alle Ziffern von 1 bis...vorhanden sein. Aber jede Ziffer, die vorhanden ist, muss so oft vorkommen, wie ihr Wert ist. Zunächst suche ich eine 23-stellige Quadratzahl.
VG, Ferma
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:26 Mo 20.09.2010 | | Autor: | Sigma |
Hallo Ferma,
Ok, hab dein Makro auch mal in Excel laufen lassen. Da findet man schnell eine Lösung. Aber ist wohl eher Zufall. Da du aber an einer 23stelligen Zahl interessiert bist wünsche ich dir viel Glück bzw. Zeit bei der Suche.
Habe jetzt mal eher zufällig 4 Quadratzahlen mit 24 Stellen mit deinen Vorgaben gefunden. Auch eher Zufall.
1. [mm] \sqrt{888866838841468263462436}=942797347706
[/mm]
2. [mm] \sqrt{888846866368843662382144}=942786755512
[/mm]
3. [mm] \sqrt{888844126368663468826384}=942785302372
[/mm]
4. [mm] \sqrt{888668136863464226488384}=942691962872
[/mm]
Wo liegt eigentlich die Motivation zu deiner Suche?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:26 Di 21.09.2010 | | Autor: | Ferma |
Guten Morgen Sigma,
meine Motivation? Das Programmieren! Zu meiner Schulzeit gab es das noch nicht, so bin ich fasziniert von den Möglichkeiten, die sich über das Programmieren ergeben! Aber... wie hast Du dem Zufall auf die Sprünge geholfen? Ich bin aus purer Bescheidenheit bei 23 Ziffern geblieben, da mich die anderen Teilnehmer an dieser Diskussion überzeugt hatten, dass es illusorisch ist, größere Zahlen zu finden. Am liebsten hätte ich natürlich die 42-stellige! Das Makro hat die ganze Nacht über ein Zahl mit 9,8,6 gesucht. Jetzt hat die 23-stellige keine Bedeutung mehr.
VG, Ferma
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:06 Di 21.09.2010 | | Autor: | Sigma |
Hallo Ferma,
habe keine Quadratzahl 9,8,6 mit 23 Stellen gefunden. Denke das es keine gibt. Hab aber schon wieder ein paar Quadratzahlen mit 25 Ziffern gefunden. Steigere mich langsam aber stetig.
1. [mm] \sqrt{8886586586883636536258521}=2981037837211
[/mm]
2. [mm] \sqrt{8885665285682631353888656}=2980883306284
[/mm]
3. [mm] \sqrt{8883836586558666255238681}=2980576552709
[/mm]
4. [mm] \sqrt{8883683285586866185652356}=2980550835934
[/mm]
Alles noch mit der naiven Methode. Natürlich nicht mit Excel sondern mit einem CAS.
|
|
|
| |
|
> Das ist gleich 65191584694745586153436251091200000, also
> eine ziemlich grosse Zahl. Alle diese Kombinationen
> durchzugehen dauert also viel zu lange. Aber es ist
> moeglich
Hallo felix,
das Schmunzelchen am Schluss hat's wirklich in sich:
was heißt denn eigentlich hier "es ist möglich" ? ...
Sonnige Grüße !
Al
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:17 Di 22.11.2011 | | Autor: | wieschoo |
Ich hänge immer noch bei dem Problem. Irgendwie stört es mich, dass das Thema hier ohne fertige Lösung beendet wurde. Das nervt
Da ich mich jetzt ein bisschen besser mit Maple auskenne, habe ich mir dort ein Programm geschrieben, welches erst alle Zahlen berechnet, die von der gewünschten Form (Anzahl der Ziffer = Ziffer) sind und möchte dann testen, ob es eine Quadratzahl ist.
Ich betrachte auch nur die Zahlen, die auf 1, 4, 5, 6, 9 enden.
Ich weiß jetzt auch nicht, wie gemeint ist die Zahl so zu wählen, dass es "ein Quadrat mod 100" ist. Welche kommen da in Frage?
Es gilt doch [mm]56^2 \mod 100 \equiv 27556\mod 100 \equiv 56[/mm]. Allerdings ist 56 keine Quadratzahl. Hab ich da etwas falsch verstanden.
Wenn ich alle Kombinationen aus den Ziffern 1,2,3,4 bilde läuft es in 2 sec alle Kombinationen durch. Bei {1,2,3,4,5} ist aber schon Schluss.
Mein Quelltext liegt in der Zip-Datei. Darin liegt auch ein Modul PPermute, welches die Permutationen iterativ berechnet und nicht wie die mitgelieferte Funktion permute erst alle Permutationen abspeichert.
Es fehlt auch nocht die Zeile "with(combinat)".
Gibt es noch irgendwelche Idee um die Sache abzuschließen?
Ich bleib dran.
|
|
|
| |
|
> Ich betrachte auch nur die Zahlen, die auf 1, 4, 5, 6, 9
> enden.
Damit kannst du die Hälfte aller Zahlen weglassen.
> Ich weiß jetzt auch nicht, wie gemeint ist die Zahl so zu
> wählen, dass es "ein Quadrat mod 100" ist. Welche kommen
> da in Frage?
Oben behältst du nur die Zahlen, die eine Endziffer haben,
die Endziffer einer Quadratzahl sein kann.
Jetzt kannst du dieselbe Idee statt nur auf die Endziffer
auf die letzten beiden Ziffern anwenden. Betrachtet man
die letzten 2 Ziffern von Quadratzahlen, so stellt man fest,
dass für das letzte Ziffernpaar nur 23 (von insgesamt 100)
Möglichkeiten in Frage kommen. Dies ist eine weitere
Verbesserung, da 23/100 < 5/10.
Dasselbe Spiel wäre natürlich auch mit den letzten 3 oder 4 ...
Stellen möglich.
LG Al
|
|
|
| |
|
> Hallo Forum,
> kann dieses Problem mathematisch oder mittels
> Programmierung gelöst werden?
> Gesucht die größte Quadratzahl, welche jede Ziffer so
> viele Male enthält, wie deren Wert ist. Beispiel:
> 543345144355225 ist eine Quadratzahl und enthält 5 Mal die
> 5, 4 Mal die 4, 3 Mal die 3, 2 Mal die 2 und einmal die 1.
> Allerdings hat die gesuchte Zahl 45(!) Stellen. (Die Summe
> aller Zahlen von 1 bis 9)
> Viele Grüße, Ferma
Hallo Ferma,
eine wichtige Frage wäre noch, wie das Wort "jede" in
der Fragestellung genau aufzufassen ist. Deine Bemerkung,
dass die gesuchte Zahl 45 Stellen haben sollte, deutet darauf
hin, dass du meinst "jede der 10 überhaupt möglichen
Dezimalstellen", also die 0 0-mal, die 1 1-mal, ... , die 9 9-mal".
Ich vermute aber, dass wohl eher gemeint war "jede Ziffer, die
in der Zahl überhaupt auftritt". Dein Beispiel 543345144355225
unterstützt jedenfalls diese Ansicht, hat aber noch die (möglicher-
weise verwirrende) Eigenschaft, dass in dieser Zahl genau alle
Ziffern von 1 bis 5 vorkommen. Vielleicht gäbe es aber auch
eine solche Quadratzahl, welche nur die Ziffern 1, 4 und 5 enthält
oder nur die Ziffern 2,4,6 und 7 etc. Das Beispiel zeigt (so wie
übrigens auch das ganz einfache Beispiel der Zahl [mm] 1=1^2), [/mm] dass
es solche Zahlen gibt. Und in der endlichen Menge aller in Frage
kommenden derartigen Quadratzahlen muss es eine größte
geben. Dass die Frage also im Prinzip lösbar ist, ist damit klar.
Schwieriger ist aber das Problem, diese maximale Zahl tatsächlich
dingfest zu machen (und z.B. die Frage, welche Dezimalziffern in ihr
überhaupt auftreten.
Ferma, du hast offenbar eine Quadratzahl gefunden, die 1mal die 1,
2mal die 2, ......., 6mal die 6 enthält. Das sind insgesamt 21 Stellen.
Möglicherweise gibt es aber doch eine 24-stellige Quadratzahl, welche
als Dezimalstellen 7mal die 7, 8mal die 8 und 9mal die 9 enthält ?
Eine solche Zahl wäre dann jedenfalls größer als die, die du ermittelt
hast, nur schon weil sie mehr Stellen besitzt ...
Ich denke also, dass die vorliegende Frage noch nicht geklärt ist.
Die stillschweigende Annahme, dass die Zahl genau 0mal die 0,
1mal die 1, 2mal die 2, ........, k-mal die Ziffer k enthalten soll,
finde ich in der Aufgabenstellung jedenfalls nicht.
LG Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 08:06 Mo 20.09.2010 | | Autor: | Ferma |
Guten Morgen,
Die erste Fragestellung hat sich erledigt, da es höchstens bis zur 6 gehen kann, wenn ALLE Ziffern von 1 angefangen dabei sein sollen. Das ist die nächste Frage: Welches ist die größte Quadratzahl mit der Eigenschaft, dass jede Ziffer darin so oft vorkommt, wie ihr Wert ist? Eine 24-stellige Zahl ist zunächst mein Ziel, weil es illusorisch ist mit einem PC eine größere zu ermitteln. Sogar eine 23-stellige wäre interessant. Die 24-stellige Zahl mit den Ziffern 8,7,5,4 hat die Quersumme 64+49+25+16=154 und 154 Mod 9=1. Also gibt es die Quadratzahl. Ich hoffe, dass ich die Frage jetzt besser formuliert habe!
VG, Ferma
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:23 Mo 20.09.2010 | | Autor: | felixf |
Moin Ferma,
> Die 24-stellige
> Zahl mit den Ziffern 8,7,5,4 hat die Quersumme
> 64+49+25+16=154 und 154 Mod 9=1. Also gibt es die
> Quadratzahl. Ich hoffe, dass ich die Frage jetzt besser
> formuliert habe!
Vorsicht! Du versuchst gerade, aus einem notwendigen Kriterium (welches nicht hinreichend ist!) die Existenz einer Zahl herzuleiten! Das geht so nicht!
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:10 Mo 20.09.2010 | | Autor: | Ferma |
Guten Morgen Felix,
also ist es nicht möglich nur aus der Quersumme einer Zahl zu schließen, ob eine beliebige Kombination ihrer Ziffern eine Quadratzahl ist oder nicht? Ansonsten müsste man halt versuchen, mit jeder Zahl, wo es nicht ausgeschlossen ist. Also wenn die Bedingung z Mod 9 =0,1,4,7 erfüllt ist, wobei z die Quersumme der Zahl darstellt.
VG, Ferma
|
|
|
| |
|
Hallo Ferma,
so ist es. Du kannst nur ggf. zeigen, dass es eine solche Quadratzahl nicht geben kann, mehr nicht. Ob es dann tatsächlich eine gibt, wenn der Test [mm] \mod{9} [/mm] nicht dagegenspricht, ist nur mit anderen Mitteln zu untersuchen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:15 Mo 20.09.2010 | | Autor: | Ferma |
Hallo reverend,
ich habe im Netz, in meinen Mathe-Büchern gesucht, aber nichts Brauchbares für diese Aufgabe gefunden. Es kommt halt selten vor, dass mit so großen Zahlen gerechnet wird. Bleibt letzten Endes wirklich nur der "naive" Versuch übrig, jede Zahl im betreffenden Zahlenraum zu prüfen?. Nach ein paar Stunden, wenn es gut läuft, dann die Meldung bekommen: es gibt keine Quadratzahl. In der Hoffnung, dass jemand mir weiterhelfen kann,
VG, Ferma
|
|
|
| |
|
> Hallo reverend,
> ich habe im Netz, in meinen Mathe-Büchern gesucht, aber
> nichts Brauchbares für diese Aufgabe gefunden. Es kommt
> halt selten vor, dass mit so großen Zahlen gerechnet wird.
> Bleibt letzten Endes wirklich nur der "naive" Versuch
> übrig, jede Zahl im betreffenden Zahlenraum zu prüfen?.
> Nach ein paar Stunden, wenn es gut läuft, dann die Meldung
> bekommen: es gibt keine Quadratzahl. In der Hoffnung, dass
> jemand mir weiterhelfen kann,
> VG, Ferma
Hallo Ferma(t?),
es ist halt möglicherweise einfach so, dass sich bisher noch
niemand die entsprechende Frage gestellt hat. Sie scheint ja
einfach deiner Phantasie entsprungen zu sein und hat kaum
ein irgendwie reales Problem als Hintergrund.
In einem solchen Fall scheint es schon eher unwahrscheinlich,
dass es einen einfachen, schönen und kurzen Lösungsweg gibt.
Falls doch, dann hättest du möglicherweise eine neue der vielen
glänzenden Perlen der Mathematik entdeckt !
Zu deinen weiteren mathematischen Entdeckungsreisen viel
Glück !
Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:10 Sa 16.10.2010 | | Autor: | wieschoo |
Schade, dass ich dieses Thema erst heute früh gesehen habe.
Trotz stundenlangen überlegen ist auch auch kein besser Algorithmus dazu eingefallen, als linear alle Zahlen durchzutesten.
Meine erste Idee war erst die Potenzmenge von {1,2,3,4,5,6,7,8,9} zu bilden. Aus den Teilmengen dann Zahlen zu bilden (z.B. {2,3} --> 22333). Dann alle Permutationen durchzurechnen. Der letzte Schritt gefällt mir nicht ganz, da bei den Permutationen die Reihenfolge beachtet wird, d.h. erspuckt neben 4444 auch 4444.
Meine Frage:
Kennt jemand einen Algorithmus, der Permutationen erzeugt, der nicht die Reihenfolge beachtet. Ich bin nicht fündig geworden.
Werbung ![[hand]](/images/smileys/hand.gif "[hand]") und anderer Weg: Den "naiven Algorithmus" von Ferma habe ich ein bisschen abgeändert.
* Zahlen streben aufwärts (nicht abwärts) also 221,333,...
* Nullen werden durch Einsen ersetzt, da es große Lücken gibt wie 1000 bis 1333.
* sonstige Optimierungen (Es gibt zum Beispiel keine 4 Stellige Zahlen, die die 9 enthalten dürfen)
Trotzdem ist es in kurzer Zeit nicht möglich für mich alles durchzurechnen. Deshalb habe ich so etwas, wie Cloud-Computing programmiert. Das Script holt sich den durchzurechnenden Zahlenbereich (100000000 Zahlen ) vom Server rechnet diesen durch und sendet die gefundenen Zahlen zurück. Das ganze schaut so aus:
Ergebnisse
Quelltext
Ich habe es in PHP getippt, da man schlampig mit den Datentypen umgehen kann. Es ist auch nicht langsamer als das obige Makro. Also wen es interessiert, kann vielleicht "mitrechnen". In der Zipdatei bei den Ergebnissen ist auch eine PHP-Interpreter dabei, sodass nichts installiert werden muss. In der Ergebnisliste ist auch dann der Name vom Upload gespeichert.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:07 So 17.10.2010 | | Autor: | felixf |
Moin!
> Meine Frage:
> Kennt jemand einen Algorithmus, der Permutationen erzeugt,
> der nicht die Reihenfolge beachtet. Ich bin nicht fündig
> geworden.
Ja, ich kenn da einen.
Hier im Pseudocode. Dazu: wir wollen die Symbole $0, [mm] \dots, [/mm] n-1$ permutieren, wobei das Symbol i genau anzahl(i) oft vorkommen soll. Indizierung bei Arrays faengt bei 0 an.
| 1: |
| | 2: | anzahl = Array(n)
| | 3: | current = Array(n)
| | 4: | i = 0
| | 5: | current(0) = -1
| | 6: | while(...)
| | 7: | if i = n then
| | 8: | { // hoechste Ebene erreicht
| | 9: | print current(0), ..., current(n-1)
| | 10: | i = i - 1
| | 11: | }
| | 12: | else
| | 13: | {
| | 14: | j = current(i) + 1
| | 15: | while anzahl(j) = 0 and j < n do
| | 16: | j = j + 1
| | 17: | if j = n then
| | 18: | { // Ebene zurueck
| | 19: | anzahl(current(i)) = anzahl(current(i)) + 1
| | 20: | i = i - 1
| | 21: | }
| | 22: | else
| | 23: | { // Ebene hoeher
| | 24: | current(i) = j
| | 25: | anzahl(j) = anzahl(j) - 1
| | 26: | i = i + 1
| | 27: | }
| | 28: | }
|
Wenn ich mich nicht vertan habe, sollte es funktionieren.
> Trotzdem ist es in kurzer Zeit nicht möglich für mich
> alles durchzurechnen. Deshalb habe ich so etwas, wie
> Cloud-Computing programmiert.
Das ist kein Cloud-Computing, sondern "ganz normales" verteiltes Berechnen :)
LG Felix
|
|
|
| |
|
Das ist nicht wirklich eine Frage. Nur gehen die Mitteilungen leider unter.
Ich selbst konnte nun mittels C++ die ersten 202 Zahlen derart ermitteln (Bruteforce da die Menge der Kandidaten bei den Quadraten kleiner ist als die Menge der Zahlen mit dieser Ziffereigenschaft.
Heute fand ich im OEIS unter
https://oeis.org/A181392
Einen Beitrag, der die größte Zahl derart angibt nämlich:
[mm]\blue{999999999786876856487355368576387875784644}= 999999999893438428238^2[/mm]
Das sind 39 Ziffern!
Verbleibt immer noch die Frage, wie man effektiv die dort angegebenen ersten 1000 Zahlen der Folge berechnet.
Diese haben auch eine interessante Verteilung
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:20 Sa 25.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
