[Knobeln] Heute: Zahlentheorie

[D. I. (Gast)]

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:

$$\forall n \in \mathbb{N} \; \exists k \in \mathbb{N}: \forall digits(2^k\;mod\;10^n) \in \{1,2\}$$

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

$$n \in \{1,2,3,...,20\}$$

Und da ich noch dazu ein sehr freundlicher Mensch bin, gibts die ersten 
beiden k's gratis:

$$n = 1 \rightarrow k = 1$$

$$n = 2 \rightarrow k = 9$$

$$n = 3 \rightarrow k = ?$$

$$n = 4 \rightarrow k = ?$$

$$n = 5 \rightarrow k = ?$$

$$n = 6 \rightarrow k = ?$$

$$n = 7 \rightarrow k = ?$$

$$n = 8 \rightarrow k = ?$$

$$n = 9 \rightarrow k = ?$$

$$n = 10 \rightarrow k = ?$$

$$n = 11 \rightarrow k = ?$$

$$n = 12 \rightarrow k = ?$$

$$n = 13 \rightarrow k = ?$$

$$n = 14 \rightarrow k = ?$$

$$n = 15 \rightarrow k = ?$$

$$n = 16 \rightarrow k = ?$$

$$n = 17 \rightarrow k = ?$$

$$n = 18 \rightarrow k = ?$$

$$n = 19 \rightarrow k = ?$$

$$n = 20 \rightarrow k = ?$$

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 ;)

[Uhu U. (uhu)]

Damit kannst du dir deine Verlängerung berechnen:

def t(n)
  k = 1
  i = 1
  p = 10 ** n
  while true
    i = i * 2
    s = (i % p).to_s
    return k if s.length == n && s =~ /^[12]+$/
    k = k + 1
  end
end

Dauert ein wenig, aber das Resultatmuster sieht interessant aus.

[Nils S. (tcatm)]

@@ -1,11 +1,14 @@
 def t(n)
   k = 1
-  i = 1
+  i = 2
   p = 10 ** n
   while true
-    i = i * 2
+    i = i * 16
     s = (i % p).to_s
     return k if s.length == n && s =~ /^[12]+$/
-    k = k + 1
+    k = k + 4
   end
 end

Dauert schonmal ein klein wenig weniger... (12s vs. 49s für n = 9)

[Uhu U. (uhu)]

Für 11 rötelt hier ein Kern schon 30 Minuten - das Problem ist etwas 
unübersichtlich...

[Nils S. (tcatm)]

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.

[Uhu U. (uhu)]

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ß...

[Nils S. (tcatm)]

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.

[D. I. (Gast)]

Schön auf Resonanz zu stoßen :)
Netter erster Versuch ;) aber dass ihr so einfach davonkommt, das konnte 
ich natürlich nicht zulassen :)

[Andreas F. (aferber)]

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

[Nils S. (tcatm)]

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.

[Nils S. (tcatm)]

Ich glaub ich habs...

$ time ruby knobeln.rb 
1 => 1
2 => 9
3 => 89
4 => 89
5 => 589
6 => 3089
7 => 3089
8 => 3089
9 => 315589
10 => 315589
11 => 8128089
12 => 164378089
13 => 945628089
14 => 1922190589
15 => 11687815589
16 => 109344065589
17 => 231414378089
18 => 1452117503089
19 => 4503875315589
20 => 65539031565589
21 => 141832976878089
22 => 1667711883128089
23 => 3575060515940589
24 => 32185290008128089
25 => 222920153289378089
26 => 222920153289378089
27 => 222920153289378089
28 => 24064778063445628089
29 => 83669422838836253089
30 => 679715870592742503089
31 => 3659948109362273753089
32 => 7385238407824187815589
33 => 7385238407824187815589
34 => 7385238407824187815589
35 => 1870030387638781219065589
36 => 6526643260716173797190589
37 => 6526643260716173797190589
38 => 181149626001118395476878089
39 => 763226235135792467742503089
40 => 763226235135792467742503089
41 => 763226235135792467742503089
42 => 73522802376970051500945628089
43 => 73522802376970051500945628089
44 => 3711501609468683003161101878089
45 => 21901395644927247761461883128089
46 => 112850865822220071552965789378089
47 => 340224541265452131031725555003089
48 => 1477092918481612428425524383128089
49 => 4319263861522013171910021453440589
50 => 18530118576724016889332506805003089

real  0m0.033s
user  0m0.030s
sys  0m0.010s

[D. I. (Gast)]

Sieht gut aus :) Es steht dir frei ob du auch den Algorithmus dazu 
erzählen möchtest oder ob du die anderen noch tüfteln lassen willst ;)

[D. I. (Gast)]

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.

[Yalu X. (yalu) (Moderator)]

Hab's auch raus, aber Nils war schneller :)

$ time python nk.py 
1 1
2 9
3 89
4 89
5 589
6 3089
7 3089
8 3089
9 315589
10 315589
11 8128089
12 164378089
13 945628089
14 1922190589
15 11687815589
16 109344065589
17 231414378089
18 1452117503089
19 4503875315589
20 65539031565589
21 141832976878089
22 1667711883128089
23 3575060515940589
24 32185290008128089
25 222920153289378089
26 222920153289378089
27 222920153289378089
28 24064778063445628089
29 83669422838836253089
30 679715870592742503089
31 3659948109362273753089
32 7385238407824187815589
33 7385238407824187815589
34 7385238407824187815589
35 1870030387638781219065589
36 6526643260716173797190589
37 6526643260716173797190589
38 181149626001118395476878089
39 763226235135792467742503089
40 763226235135792467742503089
41 763226235135792467742503089
42 73522802376970051500945628089
43 73522802376970051500945628089
44 3711501609468683003161101878089
45 21901395644927247761461883128089
46 112850865822220071552965789378089
47 340224541265452131031725555003089
48 1477092918481612428425524383128089
49 4319263861522013171910021453440589
50 18530118576724016889332506805003089

real    0m0.028s
user    0m0.023s
sys     0m0.003s

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:

nmax = 50

def only12(k, n):
  sk = str(k)[-n:]
  return len(sk) >= n and sk.count('1') + sk.count('2') == len(sk)

p10nmax = 10 ** nmax
k = 1
p2k = 2 ** k
f = 4
p2f = 2 ** f
print 1, 1
for n in range(2, nmax+1):
  while not only12(p2k, n):
    k += f
    p2k = p2k * p2f % p10nmax
  f *= 5
  p2f = p2f ** 5 % p10nmax
  print n, k

Wer also noch weiter tüfteln will, einfach nicht so genau hinschauen ;-)

[D. I. (Gast)]

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

[Yalu X. (yalu) (Moderator)]

Für nmax=1000 braucht's gute 5s.

k(1000) =
615518781133550927510466866560333743905276469414384071264775976996005261
582333424319169262744569107203933909361398767112744041716987032548389396
865721149211989700277761744700088281526981978660685104481509534097152083
798849174934153949598921020219299137483196605381824600377210207048355959
118105502326334547495384673753323864726827644650703466356156319492521379
682428275201262134907960967634887658195264018797348236155773958687977059
474419550906257366056229915615067527218040720408353328787880060032847746
927391316869927283585312014157952623949696812057481086276896651244409107
902992111507870787820359137244857060839675634572294938878098506151681269
336043213294287160464665102314138635395739226878089

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 :)

[D. I. (Gast)]

Was ist denn das für ein Programm? Händisch macht das nicht gerade Fun 
;)

[Yalu X. (yalu) (Moderator)]

D. I. schrieb:
> Was ist denn das für ein Programm?

Welches meinst du?

[D. I. (Gast)]

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

[Yalu X. (yalu) (Moderator)]

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.