letzte Ziffer?

Hey, kann jemand die Aufgabe mit Phyton lösen?^^

Answer 1

[xxxcyberxxx]

Hey, kann jemand die Aufgabe mit Phyton lösen?^^

ja, kann ich. Das ist aber DEINE Aufgabe, und du sollst es lösen.

Woran hapert es denn genau? Was hast du schon?

Fang doch mal damit an, 7^k + 2 auszurechnen - das kann Python direkt. Am besten speicherst du das in eine Variable ... Das ganze wandelst du dann in Oktal-Zahlen um, dafür gibt es auch eine fertige Funktion. Jetzt musst du davon nur noch die letzte Zahl herausfinden, auch das geht relativ trivial ...

Alternativ kann man das ganze natürlich als Einzeiler lösen, wenn man alles direkt kombiniert.

Man kann natürlich auch schlau vorgehen und die schnelle Exponentation nutzen oder direkt damit arbeiten, dass man im Oktalsystem rechnen soll und nur die letzte Ziffer relevant ist

Comments

[Tannibi]

Python hat Variablen, in denen man 7^(10^9) als Ganzzahl speichern kann?

[xxxcyberxxx]

@Tannibi

Python hat Variablen, in denen man 7^(10^9) als Ganzzahl speichern kann?

Ja. Pythons Integer haben keine Längenlimitierung. Braucht halt eventuell etwas länger zum Berechnen :^)

Muss aber auch zugeben, ich hab zuerst 10^6 gelesen und das wär noch relativ schnell zum berechnen

[tunik123]

@Tannibi

Das wollte ich auch gerade fragen, die Zahl hat knapp 1 Milliarde Ziffern.

[Tommentator]

@xxxcyberxxx

Python kann "Integerzahlen" mit log(7)*1e9 ~ 845.098.040 Stellen darstellen und damit fehlerfrei rechnen? Wau!
D.h. diese Integerzahlen brauch mind. ~100 MByte und bis ~ 900MB Speicher...
Das schon mal ausprobiert? Und bei welcher Rechenzeit?

[YBCO123]

delete

Answer 2

[mihisu]

Ich glaube, du meinst „Python“ statt „Phyton“.

============

Die letzte Ziffer im Oktalsystem ist gleich dem Rest, der bei Division durch 8 mit Rest entsteht.

Für die Potenz 7ᵏ modulo 8 (also für den Rest bei Division von 7ᵏ durch 8) kann man in Python pow(7, k, 8) verwenden. Und dann addiert man noch 2 (und bildet gegebenenfalls nochmal modulo 8, um sicherzugehen, dass man durch die Addition von 2 nicht größer oder gleich 8 geworden ist, womit man dann nicht die gesuchte Ziffer hätte, sondern etwas zu viel).

Der Trick ist hier pow(7, k, 8) statt pow(7, k) bzw. 7**k zu verwenden. Denn 7ᵏ ist doch nicht gerade eine kleine Zahl. Wenn man versucht zuerst 7ᵏ zu berechnen und dann danach erst modulo 8 zu rechnen, dauert das viel länger und braucht mehr Speicher, als wenn man im Vergleich dazu mit pow(7, k, 8) direkt während des Potenzierens schon modulo 8 rechnet.

Also...

k = 10**9
r = (pow(7, k, 8) + 2) % 8
print("Gesuchte Ziffer:", r)

Ausgabe, die dieser Code liefert:

Gesuchte Ziffer: 3

============

Bemerkung: Man könnte das auch ohne Python relativ leicht im Kopf berechnen...

Aber da nach einer Lösung mit Python gefragt worden ist, habe ich dir natürlich auch eine Lösung mit Python geliefert.

Comments

[gaba88]

hey, vielen Dank für die ausführliche Antwort. Was macht man, wenn man bsp. die 3 letzten Ziffern ausgeben soll? macht man dann %800? Also einfach nur 0"nullen" ranhängen??

[mihisu]

@gaba88

Wenn man im Dezimalsystem die drei letzten Ziffern haben möchte, würde man modulo 10³ = 1000 rechnen.

Wenn man im Oktalsystem die drei letzten Ziffern haben möchte, müsste man modulo 8³ = 512 rechnen.

Du müsstest also modulo 512 statt modulo 800 rechnen.

==========

Das mit „Nullen dranhängen“ könnte man so sehen. Aber die Nullen dürfen nicht im Dezimalsystem drangehängt werden, sondern entsprechend im Oktalsystem. Du bräuchtest also statt der Zahl 800 (was gleich [1440]₈ im Oktalsystem wäre), die Oktalzahl [1000]₈, also...

[1000]₈ = 1 ⋅ 8³ + 0 ⋅ 8² + 0 ⋅ 8¹ + 0 ⋅ 8⁰ = 8³ = 512

============

Wenn man nun beispielsweise für die Zahl 7^(10^9) + 2 die letzten 3 Ziffern der Darstellung im Oktalsystem haben möchte...

k = 10**9
b = 8**3
r = (pow(7, k, b) + 2) % b
print(f"Gesuchte Ziffern: {r:03o}")

Ausgabe:

Gesuchte Ziffern: 003

============

Bei dem Beispiel habe ich die Zahl r im Format-String mit 03o formatiert.

Der Teil „03“ bewirkt, dass mit führenden Nullen aufgefüllt wird, bis man drei Stellen hat. Sonst würde man für die letzten 3 Ziffern im konkreten Fall nur „3“ statt „003“ erhalten, da die Ziffern vor der 3 jeweils 0 sind, und daher bei der Ausgabe der berechneten Zahl r weggelassen werden würden.

Das „o“ von „03o“ bei der Formatierung bewirkt, dass die Zahl im Oktalsystem dargestellt wird. Im konkreten Fall würde das nichts machen, wenn man es im Dezimalsystem darstellen würde, da [3]₈ = 3 ist. Aber wenn man beispielsweise das folgende Beispiel betrachten würde...

Die Dezimalzahl 1234567 hat im Oktalsystem die Darstellung [4553207]₈. Wenn man in Python nun 1234567 % 8**3 berechnen lässt, so liefert dass die Zahl 135, welche [207]₈ als Darstellung im Oktalsystem hat. Man muss nun aufpassen, dass man nicht einfach „135“ ausgibt, sondern „207“.

Falsch wäre also bei der Dezimalzahl 1234567 für die letzten drei Ziffern im Okalsystem:

r = 1234567 % 8**3
print(f"Gesuchte Ziffern: {r}")
#Ausgabe...
#Gesuchte Ziffern: 135

Richtig wäre in diesem Fall:

r = 1234567 % 8**3
print(f"Gesuchte Ziffern: {r:03o}")
#Ausgabe...
#Gesuchte Ziffern: 207

Answer 3

[LUKEars]

du willst also rechnen:

$\left(7^{\left(10^9\right)}+2\right)\ \text{modulo}\ \ 8\ =\ ?$

also: was für ein Rest bleibt, wenn man 7 hoch 1 Milliarde durch 8 teilt?

$7\cdot....\ \cdot7$

49 modulo 8 ist 1... welche Restklassen Rechenregeln kennt ihr denn? Die da vllt?

$\left[a\right]_m\cdot\left[b\right]_m\ =\ \left[a\cdot b\right]_m$ reicht's schon? https://www.lernhelfer.de/schuelerlexikon/mathematik-abitur/artikel/restklassen

Woher ich das weiß: Studium / Ausbildung

Answer 4

[Erden155]

Nein, muss man auch nicht, denn die lösung lautet 3.

Comments

[tunik123]

Ja mit Zahlentheorie ist das keine Kunst - aber mit Python?

[Erden155]

@tunik123

Die kunst am Programmieren ist es gerade auf so tricks zurück zugreifen, unter anderem.

[tunik123]

@Erden155

Das stimmt.

Aber das bisschen, was bei dieser Aufgabe rechnen muss, hat man auch schnell von Hand gerechnet.