Knobelaufgabe zu Zahlentheorie. Kleinste natürliche Zahl, die bei Division durch k den Rest k-1 lässt, mit 2≤k≤100.

Question

Ich komme selber auf keinen grünen Zweig. Das ist eine freiwillige Zusatzaufgabe, welche ich aber verstehen/lösen will.

Die Aufgabe:

Gesucht ist die kleinste natürliche Zahl, die bei Division durch k den Rest k-1 lässt, mit 2 ≤ k ≤ 100.

Also soll meine gesuchte Zahl, wenn ich sie durch 100 teile, den Rest 99 haben. Gleichzeitig aber, wenn ich sie durch 99 teile, den Rest 98 usw.

Gesucht sind nur die letzten beiden Ziffern, die ersten beiden Ziffern und die Gesamtzahl an Ziffern.

Ich habe mich nun lange damit auseinandergesetzt und vieles rumprobiert. Hab auch ein C-Programm geschrieben, mit dem ich es lösen könnte, jedoch ist die Zahl viel zu groß, als dass ich sie direkt und mit allen Stellen berechnen kann. Mir fällt aber keine alternative Herangehensweise ein.

Herausgefunden habe ich bereits, dass die letzten beiden Ziffern 99 sind. Das muss ja so sein, wegen der 100, die den Rest 99 braucht.

Hier füge ich mal spaßeshalber die Zahlen an, die mein Programm noch ausspucken konnte. Es werden immer mehr Zahlen berücksichtigt und ihr seht, wie sehr die Zahl dabei wächst.

100 & 99 :

9899

100 & 99 & 98 :

 485099

100 & 99 & 98 & 97 :

 47054699

100 & 99 & 98 & 97 & 96 :

 376437599

100 & 99 & 98 & 97 & 96 & 95 :

 7152314399

100 & 99 & 98 & 97 & 96 & 95 & 94 :

 336158776799

100 & 99 & 98 & 97 & 96 & 95 & 94 & 93 :

 10420922080799

100 & 99 & 98 & 97 & 96 & 95 & 94 & 93 & 92 :

 239681207858399

100 & 99 & 98 & 97 & 96 & 95 & 94 & 93 & 92 & 91 :

 3115855702159199

100 & 99 & 98 & 97 & 96 & 95 & 94 & 93 & 92 & 91 & 90 :

 6231711404318399

100 & 99 & 98 & 97 & 96 & 95 & 94 & 93 & 92 & 91 & 90 & 89 :

 554622314984337599

100 & 99 & 98 & 97 & 96 & 95 & 94 & 93 & 92 & 91 & 90 & 89 & 88 :

 1109244629968675199

Answer 1

Als ich mir per Iterationsrechner die kgV - Folge ansah:

Habe ich auch gleich die bekannte Folge dahinter gefunden: A003418.

Unter http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php  kann man damit bis Argument 599 (ergibt über 200 stellige Zahlen!!) berechnen:

Deine exakte Lösung lautet also A[100]-1=69720375229712477164533808935312303556799

Und Du kannst Deinem "Lehrer" sagen, dass Du die Lösungen bis 599 kennst.

Comments

Wow es ist wirklich sooo simpel! Ich muss einfach das kleinste gemeinsame Vielfache suchen, was man ja super leicht über Primfaktorzerlegung machen kann.

Da bleibt mir nur noch eine Frage, falls das jemand weiß: Sind diese Zahlen wirklich von ein Computer gerechnet, oder sind sie  händisch einfach vorberechnet und die Zahlen werden nur noch angezeigt?? Denn die Genauigkeit auf einem 64-Bit System reicht ja gerade mal für 19 Stellen...

---

Ich habe selbst alles per php programmiert, und da gibt es bc-Funktionen: man übergibt Strings und die Anzahl der Nachkommastellen, die man haben will.

Da man aber nur Grundrechenarten hat, ist der Rest (über 300Funktionen) Optimierungsarbeit! Für etwa 85% der Funktionen konnte ich hypergeometrische Funktionen einbauen

Answer 2

Hi,

es reicht, wenn du nur die jeweiligen höchsten Potenzen der unterschiedlichen Primzahlen bis 100 überprüfst. (Anstatt 99 Kongruenzen, hast du also nur 25). Warum das so ist kannst du ja gerne erstmal selbst überlegen.

Gruß

Comments

Vielen Dank, jetzt hab ich die Lösung 6.97203752×10⁴⁰

Allerdings bin ich kein Mathestudent und scheitere gerade daran mir die Erklärung zusammen zu reimen. Ich springe von einer Wikipediaseite zur anderen. Primzahlen -> Kongruenz -> Teilerfremdheit -> Kleiner Satz von Fermat -> Eulersche Phi-Funktion usw. usw.

Das meiste lese ich zum ersten mal hehe. Ich weiß auch gar nicht ob ich überhaupt auf dem richtigen Weg bin.

---

Zahlentheorie ist schon eine interessante Sache aber für diese Aufgabe braucht man echt nur ein paar elementare Überlegungen. Wenn dich das Thema allgemein interessiert solltest du vielleicht ein Buch über Zahlentheorie zur Hand nehmen, damit du ein wenig Struktur in die Einarbeitung bekommst. Wikipedia-Artikel können zwar auch hilfreich sein, aber für den ungeübten eventuell auch manchmal zu kryptisch sein.
Wo ist denn diese Aufgabe her?

---

Okay das macht Mut. Dann werde ich mich noch weiter damit beschäftigen :)

Jedes Semester machen ein paar Mathe-Profs irgendeine Knobelaufgabe, für Leute, die an solchen mathematischen Dingen Spaß haben. Ich bin aber in der Fakultät Mechatronik und wir haben eben nur sehr spezielle Gebiete der Mathematik. Andauernd machen wir Vereinfachungen bzw. lassen schwierige Fälle einfach weg(oft mit der Begründung, dass sie sowieso nicht praxisrelevant sind).

---

Alles klar interessant :). Dann viel Spaß weiterhin!