In meinen alten Programmiertrainingsunterlagen habe ich folgendes
Schmankerl entdeckt und möchte euch dazu animieren es zu lösen:
Folgender Satz aus der Zahlentheorie ist bewiesen:
Oder natürlichsprachlich: Zu jeder natürlichen Zahl n exisitiert eine
natürliche Zahl k so dass die letzten n Ziffern von 2^k nur aus 1en und
2en bestehen.
Eure Aufgabe besteht nun zu den folgenden gegebenen n's die passenden
k's zu finden. Um der Sache ein wenig Würze zu verleihen soll immer das
kleinstmöglichste k gefunden werden.
Da ich ein genügsamer Mensch bin reicht es mir wenn ihr die k's findet
für
Und da ich noch dazu ein sehr freundlicher Mensch bin, gibts die ersten
beiden k's gratis:
Der erste mit der kompletten richtigen Lösung, darf auf seinen E-Pen*s
1cm bis 2cm addieren :)
Edit: Es ist sowohl "händisch" als auch "programmiertechnisch" erlaubt,
die Lösung zu finden. Aber ich stelle mir ersteres sehr mühsam vor ;)
Huch, da hat sich ein Fehler bei mir eingeschlichen. k muss noch mit 5
initialisiert werden und für n = 1 kann die Funktion dann natürlich kein
Ergebnis mehr finden.
Hast du für 11 schon was rausgekriegt? Meine erste Version hat jetzt mit
fast einer Stunde CPU immer noch nichts gefunden.
Mir scheint, daß man da noch etwas zahlentheoretischen Hirnschmalz
investieren muß...
Jop, 11 hab ich. 12 ist schwerer, ich optimiere erstmal den Algo für 1
bis 11 auf ein paar Sekunden. Tipp: Teilbarkeitsregeln und
Potenzgesetze. Damit kannst du die zu überprüfenden k enorm Einschränken
bzw. (Vermutung) wenn du es vollständig ausformulierst alle k direkt
berechnen.
Ihr solltet euch mal nach Algorithmen für diskrete Logarithmen umsehen,
damit hängt das Problem letztlich zusammen soweit ich sehen kann. Eine
allgemeine schnelle Lösung dafür gibt es nicht, nicht umsonst werden die
für einige asymmetrische Cryptoalgorithmen eingesetzt. Ich will aber
nicht ausschliessen dass es in diesem Spezialfall vielleicht einen Trick
gibt.
Ausserdem ist bei dem vorliegenden naiven Ansatz modulare Exponentiation
in der Schleife schneller als die Multiplikation plus Modulo, da es
dafür optimierte Algorithmen gibt.
Mein schnell hingeschmiertes Perl-Script (siehe Attachment, mit
Rückgriff auf die GMP-Lib und ihre Funktion für modulare Exponentiation)
berechnet mit einem Kern bis n=10 in 3,8 Sekunden und bis n=11 in ca.
100 Sekunden, weiter hab' ich's nicht laufen lassen (bzw. irgendwo bei
k=2*10^8 abgebrochen).
Für weiteres Nachdenken ist mir zu warm ;-)
Andreas
Langsam wirds. Für n = 1 bis 10 braucht meiner nun nur noch 102ms. Ab n
= 11 meckert Ruby, dass die Datentypen zu klein werden. Muss mir mal
eine geeigneteres Format für die Potenzen ausdenken.
Prinzipiell geh ich das Problem nun rückwärts an: Ich erzeuge immer
längere Ketten aus 1en und 2en, die auf 2^n passen.
Ein trivialer Algorithmus, der allerdings nicht das minimale k findet
(das ist die Crux), funktioniert wie folgt:
- Bestimme die ersten beiden k's so dass gilt k1 < k2 => n1 < n2
- Berechne die Differenz k2-k1
- Addiere diese Differenz solange auf k2, bis man ein k2_neu erhält bei
dem gilt: k2 < k2_neu => n2 < n2_neu
- setze k1 = k2 und k2 = k2_neu
- Berechne die Differenz k2-k1;
So kann man in ein paar Sekunden bis n = 100 rechnen (siehe Datei), aber
leider nicht minimal.
Ich schätze, ich habe einen ähnlichen Algorithmus wie Nils, deswegen
auch die ähnliche Laufzeit.
Da den Code auf Anhieb sowieso keiner verstehen wird, poste ich ihn
hier mal:
1
nmax = 50
2
3
def only12(k, n):
4
sk = str(k)[-n:]
5
return len(sk) >= n and sk.count('1') + sk.count('2') == len(sk)
6
7
p10nmax = 10 ** nmax
8
k = 1
9
p2k = 2 ** k
10
f = 4
11
p2f = 2 ** f
12
print 1, 1
13
for n in range(2, nmax+1):
14
while not only12(p2k, n):
15
k += f
16
p2k = p2k * p2f % p10nmax
17
f *= 5
18
p2f = p2f ** 5 % p10nmax
19
print n, k
Wer also noch weiter tüfteln will, einfach nicht so genau hinschauen ;-)
Yo Yalu, so ist es, quasi Musterlösung :) aber Nils war in der Tat
schneller, d.h. 1cm für dich, 2cm für Nils :D
In den nächsten Tagen folgt dann wieder eins
Der nächste Schritt wäre jetzt natürlich, einen geschlossenen Ausdruck
für k(n) zu finden. Aber ich glaube, das spare ich mir, zumindest für
heute ;-)
PS: Ich habe gestern ebenfalls ein Rätsel gepostet, was aber evtl. im
Analogtechnikforum etwas verloren gegangen ist:
Beitrag "Widerstandsknobelei"
Vielleicht hat ja der eine oder andere Lust, dort mal vorbeizuschauen.
Die einfachere erste Teilaufgabe ist bereits gelöst, die zweite sucht
noch nach einem klugen Kopf :)
Yalu X. schrieb:> D. I. schrieb:>> Was ist denn das für ein Programm?>> Welches meinst du?
Das mit dem man die Widerstände verschalten kann und automatisch die
Ströme berechnen
D. I. schrieb:>> Welches meinst du?>> Das mit dem man die Widerstände verschalten kann und automatisch die> Ströme berechnen
Achso, das ist LTSpice, eine Spice-Implementation von Linear Technology:
http://www.linear.com/designtools/software/#Spice
Das hilft aber bei der zweiten Teilaufgabe, wo auch der Gesamtwiderstand
vorgegeben ist nicht, so arg viel, weil man den Gesamtwiderstand mit
Spice zwar ermitteln kann, man aber sehr viele Schaltungen eingeben und
simulieren müsste, um irgendwann den richtigen Wert zu treffen. Da kommt
man wahrscheinlich schneller zum Ziel, wenn man sich den Algorithmus zur
Berechnung der Ströme selbst schreibt, wobei man sich dabei noch die
Tatsache zunutze machen kann, dass alle Widerstände gleich groß sind.