Binärschreibweise der Primfaktoren von Fibonaccizahlen- Zählthread

[Merrx]

28657 | 28657 | 110111111110001

---

Counting Thread Crusader

[MovieTrash]

46368 | 2^5 x 3^2 x 7 x 23 | 10^101 x 11^10 x 111 x 10111

[Merrx]

75025 | 5^2 x 3001 | 101^10 x 101110111001

---

Counting Thread Crusader

[MovieTrash]

121393 l 233 x 521 l 11101001 x 1000001001
Mein Mathelehrer (und Schulleiter) hat mir heute zwei Tipps verraten, mit denen man die Primfaktoren deutlich leichter bestimmen kann. Wenn ihr wollt, kann ich versuchen sie zu erklären.

[T2-4B]

196418 | 2*17*53*109 | 10*10001*110101*1101101

Mach bitte bin nämlich alle durchgegangen... die 109 war iwie kacke

[Merrx]

317811 | 3 x 13 x 29 x 281 | 11 x 1101 x 11101 x 100011001

(Tipp die Nächste ist prim...)

---

Counting Thread Crusader

[MovieTrash]

514229 | 514229 | 10101110010111110101

(21.11.2012)Merrx schrieb:  (Tipp die Nächste ist prim...)

---

Counting Thread Crusader

Wie unten erklärt, wusste ich, dass das eine Primzahl ist.
Und ich musste sie in eine 20 stellige Binärzahl umwandeln

Tipp: Die Nächste hat 7 Primfaktoren!


Also ich hoffe man versteht das Prinzip
Anmerkung: "=>" bedeutet: "daraus folgt"
Erstmal die Formel zur Berechnung der Fibonaccizahlen:

Spoiler (Öffnen)

Diese Formel liefert die Fibonaccizahl Nummer n!

Hier die Berechnungshilfen für die Primfaktoren:

Spoiler (Öffnen)

Wenn man die Fibonaccizahlen durchnummeriert:

Nummer | Fibonaccizahl
1 | 1
2 | 1
3 | 2
4 | 3
5 | 5
6 | 8
7 | 13
8 | 21
9 | 34
... | ...

Es sei m die Nummer der zu zerlegenden Fibonaccizahl!
Es sei n die Nummer einer beliebigen Fibonaccizahl!
Wenn Nummer n Nummer m teilt, so hat die Fibonaccizahl Nummer n die Fibonaccizahl Nummer m.

Als Formel:

n|m => f(n)|f(m)

Beispiel:
n=4
m=8
m:n=2 => n teilt m => f(n) teilt f(m) => f(m)=f(n)*k -> k ist das Produkt der restlichen Primfaktoren!
=>f(m)=3*k => f(m):3=k => Man muss nur noch die Primfaktorenzerlegung von k finden. Das ist einfacher als die Primfaktorenzerlegung von f(m) zu finden, da k<f(m)
f(m)=21 => k=21:3=7

Das nächste wird ein bisschen komplizierter

Erstmal die Formel:

ggT{f(n);f(m)}=f(ggT{n;m})
Wer das versteht, bekommt nen Keks!
Der größte gemeinsame Teiler der Fibonaccizahlen Nummer n und m ist gleich der Fibonaccizahl mit der Nummer q [=f(q)].
Es gilt: q ist der größte gemeinsame Teiler von n und m
Also gilt: f(m)=f(q)*k -> k ist das Produkt der restlichen Primfaktoren!

Beispiel:
m=18
n=12
ggT{n;m}=6 => f(6) teilt f(m) => f(m=18)=f(6)*k
=> f(18):f(6)=k => k=323=17*19


Man kann übrigens mehrere Primfaktoren herausfinden, wenn man beide Ansätze miteinander kombiniert!

Beispiel:
m=18
n1=12
[nach: siehe 2.Ansatz] f(m=18)=f(6)*k
f(6)=8=2*2*2 => 2^3 teilt f(18)
[nach: siehe 1.Ansatz] f(m=18)=f(9)*i -> i ist das Produkt der restlichen Primfaktoren! Es gilt: i ungleich f(6) und f(9) ungleich k
f(9)=34=2*17 => 17*2 teilt f(18)
Achtung! Es folgt nicht: 17*2^4 teilt f(18), da die "2" von "17*2" einer der Primfaktoren aus "2^3" sein kann (und im Beispiel auch ist. ).

Ich habe noch 2 weitere kleine Tricks auf Lager, jetzt aber keine Zeit sie zu posten! Wenn ihr wollt, kann ich sie euch in meinem nächsten Post verraten.
Wenn ihr etwas an meinen Ausführungen nicht verstanden habt, schreibt mir eine PN.

PS.: Die Erklärungen habe ich alle selbst aus den Formeln abgeleitet.

[Merrx]

Meine Berechnung geht da irgendwie einfacher: Fibonacci[i] liefert die i-te Fib-Zahl, die ist aber auch noch am einfachsten herauszufinden.

832040 | 2^3 x 5 x 11 x 31 x 61 | 10^11 x 101 x 1011 x 11111 x 111101

(Die Nächste hat nur 2 Primfaktoren..)

---

Counting Thread Crusader

[404compliant]

Netter Thread, wenn auch mit Computeralgebraprogrammen keine Herausforderung...

1346269 | 557*2417 | 1000101101*100101110001

Ein paar Seiten geht das noch mit brute force, irgendwann wird das Primfaktorzerlegen etwas problematisch. Aber da gibts ja dann schon Ansätze.

Vorschau Seite 20 (Öffnen)

460835978753503578226215883073872246385764472086797082873203188542544616448248343576 | 2^3 * 269 * 4021 * 116849 * 1429913 * 24994118449 * 2686039424221 * 940094299967491 * 5050260704396247169315999021 | 10^11 * 100001101 * 111110110101 * 11100100001110001 * 101011101000110011001 *
10111010001110000111111101100110001 * 100111000101100100011011001111110011011101 *
11010101110000001011000010110011100001000000000011 * 100000101000101111010010011010101110111000001001100110100111111100001110101011000110100101101

[Merrx]

2179309 | 3 x 7 x 47 x 2207 | 11 x 111 x 101111 x 1001101101011001

---

Counting Thread Crusader

[MovieTrash]

3524578 l 2 x 89 x 19801 l 10 x 1011001 x 100110111011001

[appleblack]

5702887 l 1597 x 3571 l 11000111101 x 110111110011

[Merrx]

9227465 | 5 x 13 x 141961 | 101 x 1101 x 100010101010001001

---

Counting Thread Crusader

[Ianus]

Das wird ja immer... ausgefallener
15030352 | 2^4 x 29^2 x 1117 | (10)^4 x (11101)^2 x (10001011101)
Fehlt nur noch ein Zählthread, in welchem man zur Berechnung ein NP-Vollständiges Probelm lösen muss.

[Merrx]

Ianus... deine Fibonacci-Zahl ist falsch... richtig wäre
14930352 | 2^4 x 3^3 x 17 x 19 x 107 | 10^100 x 11^11 x 10001 x 10011 x 1101011

meine ist:
24157817 | 73 x 149 x 2221 | 1001001 x 10010101 x 100010101101

Ein NP-Vollständiges Problem?
Machen wir ein Rucksack-Problem-Zählthread auf?
aber "4 gewinnt" ist doch auch schon relativ anspruchsvoll

---

Counting Thread Crusader

[tofl]

39088169 | 37*113*9349 | 100101*1110001*10010010000101

[Merrx]

63245986 | 2 x 233 x 135721 | 10 x 11101001 x 100001001000101001

---

Counting Thread Crusader

[tofl]

102334155 | 3*5*7*11*41*2161 | 11*101*111*101001*100001110001

[cooglephish]

16580141 | 111111001111111000101101

[Merrx]

@cooglephish: dieser Thread geht etwas anders...

165580141 | 2789 * 59369 | 101011100101 * 1110011111101001

---

Counting Thread Crusader