 |
 |
 |
 |
 |
 |
Startseite » Forum » Beweis für scheinbar simples Problem
Beweis für scheinbar simples Problem
Universität / Fachhochschule
Tags: Quersumme, Teilbarkeit, Zahlentheorie
 
|
  |
|---|
|
Hallo zusammen, ich suche seit Jahren nach einem Beweis für eine denkbar simple Aussage. Ich behaupte: Für alle natürliche Zahlen existiert eine Zahl sodass gilt: und die Quersumme von ist gleich . Beispiel: Für gilt mit dass und die Quersumme(209) . Für gilt: und die Quersumme von ist . Wie beweist man, dass diese Zahl immer existiert? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, vielleicht hilft dir die Antwort dort: math.stackexchange.com/questions/182943/divisibility-by-sum-of-digits Gruß pivot |
|
|
|
Einfach, aber genial - kann man nicht anders sagen. Könnte natürlich manche Leute enttäuschen, die vergleichsweise "kleine" Zahlen erwarten, aber solche sind hier ja nicht gefordert. ;-) |
 |
|
Hallo pivot, besten Dank, das habe ich nie gefunden. Wenn ich das durchgehe, werden tatsächlich nochmal deutlich größere Zahlen kreiert, als es nötig ist :-D) Für ist nach der Weise . Mit wird dann die Zahl mit 4375 Ziffern kreiert, die tatsächlich durch 81 teilbar ist und deren Quersumme ganz offensichtlich 81 ist. Absolut wild, aber es beweist die Existenz, danke vielmals!! @HAL9000: Echt witzig, oder? Die Idee kam beim Spiel Hep: Reihum im Kreis zählt man die natürlichen Zahlen durch, aber bei jeder Zahl, die durch 7 teilbar ist, die 7 enthält oder deren Quersumme die 7 enthält oder durch 7 teilbar ist, sagt man stattdessen Hep und es gibt einen Richtungswechsel. Jeder Fehler verliert das Spiel. Wenn man das mal mit anderen Zahlen als 7 spielt, fällt auf, dass die Quersumme irgendwann mit der Teilbarkeit kollidiert, aber gibt es das eben für jede Grundzahl, mit der man spielt? Jetzt weiß ich: ja :-) Beste Grüße IAsmodai |
|
|
|
> bei jeder Zahl, die durch 7 teilbar ist, die 7 enthält oder deren Quersumme die 7 enthält oder durch 7 teilbar ist Das ist aber nicht noch weiter "iteriert" gemeint, oder? Beispiel 88: Nicht durch 7 teilbar und enthält auch keine 7. Quersumme 16 ist nicht durch 7 teilbar und enthält auch keine 7. Gehört also nicht dazu. Wenn nun aber auch die Quersumme 7 von 16 einbezogen werden soll, sieht es anders aus... |
 |
|
Wir haben ein Trinkspiel, das in den meisten Fällen die 70 nicht passiert hat, nicht derart durchexerziert, nein :-D) Die Quersumme generell ist meiner Erinnerung schon eine Erweiterung des Spiels gewesen. Original heißt das wohl Teiler 7 oder Buzz: www.spielewiki.org/wiki/Teiler_7 |
|
|
|
Hab mal ein kleines Progrämmchen geschrieben, was zu vorgegebenem zwar nicht die kleinste Zahl mit der geforderten Teilbarkeits- und Quersummeneigenschaft findet, aber zumindest eine nur moderat größere, d.h., mit nicht viel mehr als Dezimalstellen: So wirft es beispielsweise für eine Zahl mit 227 Ziffern aus, die ich besser gemäß "Ziffern 2697 gefolgt von 222 x Ziffer 9 und abschließend Ziffer 2" beschreibe als durch die vollständige Ziffernangabe hier im Forum. Oder "mathematischer" ausgedrückt: . |
|
|
|
Hallo HAL9000, du bist ja wirklich sehr engagiert, immer wieder schön zu sehen, welche Faszination die Mathematik hervorruft :-) Mir ist gerade noch eine Frage zu deiner Ambition gekommen: Du schreibst "nicht die kleinste". Welchen Algorithmus hast du dafür denn gewählt? Und finden wir einen effizienten, der tatsächlich die kleinste Zahl definiert? Jetzt wird es vielleicht mathematisch wirklich komisch, aber welcher Ordnung würde denn ein Algorithmus folgen, der tatsächlich die kleinste dieser Zahlen bestimmen kann? Einfach gedacht: Laufe für bis alle Mulitplikationen von n durch und teste die Quersumme. Das Maximum entspricht der Zahl aus dem Beweis, den du gepostet hast. Bleibt das auf Dauer bei (funktioniert mathcal bei onlinemathe nicht?). Beste Grüße IAsmodai |
|
|
|
Mein Vorgehen für "große" (für kleine findet man mit Bruteforce auch die kleinste Lösung): 1) Zerlegung wie im obigen Link, d.h., enthält alle Primteiler 2 und 5 von , und der Restfaktor ist teilerfremd zu 10. 2) Es sei die kleinste Zahl mit . Dann ist auch durch teilbar - diese Zahl liefert die letzten Stellen meiner gebildeten Zahl. 3) Jetzt gebe ich mir eine "genügend große" Stellenzahl vor, und fülle die in 2) erwähnte Zahl vorn mit Neunen auf, die so gebildete -stellige Zahl ist . Diese Anzahl sollte so gewählt werden, dass die Quersumme von kleiner als ist, aber "nicht viel kleiner", also so ungefähr (dazu später mehr). 4) Zahlentheoretisch können wir berechnen , dann habe wir auch . Aus der Teilerfremdheit von und folgt zudem unmittelbar die Teilerfremdheit von und . Wir suchen nun eine Basiszahl , welche durch teilbar ist. Durch ist sie teilbar, wir müssen nun noch sichern, dass sie auch durch teilbar ist. Dazu muss gelten , diese Kongruenzgleichung ist nach auflösbar. 5) Nun wissen wir, dass sämtliche Zahlen durch teilbar sind, jetzt zählen wir hoch bis Bedingung , umgestellt erfüllt ist. Nach obiger Wahl von haben wir , was die Suche nicht allzu lange machen sollte. Das ganze habe ich getestet für (Programmlaufzeit 2 Sekunden für alle (!) diese Werte zusammen, allerdings ohne vollständige Ausgabe auf dem Bildschirm), da funktioniert es. Durch die vielen Neunen in der Zahl ist die gefundene Zahl also nicht viel länger als das Optimum - jenes wird man aber mit dieser Prozedur hier i.d.R. nicht erreichen. Anmerkung: Im Fall , d.h. wenn weder durch 2 noch durch 5 teilbar ist, vereinfacht sich die Betrachtung: So ist in diesem Fall etwa eine Zahl, die aus genau Neunen besteht, wir wissen damit sofort . P.S.: Die Wahl der Grenzen 40 und 60 ist nicht in Stein gemeißelt: Wählt man den unteren Wert zu klein, besteht die Gefahr, dass stets zu groß ist und man nie (*) erfüllen kann. Wählt man es andererseits zu groß, dann dauert die Probierei ewig, bis man zum Erfolg kommt. > Und finden wir einen effizienten, der tatsächlich die kleinste Zahl definiert? Halte ich bei großen für ziemlich ausgeschlossen. Die Rechenzeit für die vielen Kombinationsmöglichkeiten wird sehr schnell ausufernd groß. |
1587711
1587660