Cybermancer wrote: ↑11.03.2019, 11:20
Leute, ich bräuchte mal eure Hilfe.
Also ich bin letztens auf folgendes kleines Rätsel gestoßen:
https://fivethirtyeight.com/features/ho ... r-numbers/
Kleines Zahlentheorie-Rätsel dachte ich mir, naja kann man sich mal kurz mit beschäftigen, dachte ich ........
Inzwischen bin ich so verzweifelt, dass ich eben in einem unbeobachten Moment ein Programm geschrieben habe, um das Problem zu brute-forcen (ich weiß, stillos. Ich schäme mich auch entsprechend
![blush :blush:](./images/smilies/c01-blush.gif)
)
Kann mich vielleicht jemand von euch an die Hand nehmen und zu einer analytischen Lösung des Problems führen oder zumindest die Zeitkomplexität des Problems reduzieren.
Ich hab mir jetzt den Code nicht angesehen.
Aber folgende Regeln fallen sofort ins Auge:
- Die 0 kommt nicht vor
- Die Form ist t1n1t2n... (ti =tully/Anzahl, ni = number/Ziffer)
- Die Länge der Zahlen ist teilbar durch 2
- Maximale Länge der Zahl = 18
- Die Summe der ti ist gleich der Länge der Zahl
- Die möglichen ti beschränken sich auf die Menge der möglichen Summanden der Länge der Zahl (bsp. Länge 4 -> T1=(1,3) T2=(2,2)
- Die zu den ti gehörenden ni N(ti) sind genau Häufigkeit der ti +1 (mit Ausnahme von "22")
- Ein ni das nicht den möglichen Summanden entspricht ist nur einfach vorhanden, da es nicht als ti verwendet wird kann.
- Deren Anahl ist Länge/2 - Anzahl der verschiedenen ti.
- Vermutung: Ein "gültiger" Anfang kann nicht gültig ergänzt werden ("22" ist gültig, "22...." ist immer ungültig)
Länge 2:
T=(2) -> "22" (Sonderfall)
Länge 4:
T=(1,3) -> N(1)=2 (nicht in T.)
T=(2,2)-> N(2)=3 (nicht in T.)
Länge 6:
T=(1,1,4) -> N(1)=3 (nicht in T)
T=(1,2,3)-> N(1)=2, N(2)=2 (nicht (mehr) in T)
T=(2,2,2)-> N(2)=4 (nicht in T)
Länge 8:
T=(1,1,1,5) -> N(1)=4 (nicht in T)
T=(1,1,2,4) -> N(1)=3 (nicht in T)
T=(1,1,3,3) -> N(1)=3, N(3)=3
mögiche Folge: 31 33 1x 1y mit (x,y)=(4,5),(4,6),(4,7),(4,8),(4,9),(5,6),(5,7)....
mögiche Folge: 31 12 33 1y mit x=2, y=4,5,6,7,8,9
T=(1,2,2,3)-> N(1)=2, N(2)=3, N(3)=2
mögliche Folge: 21 32 23 1x mit x=4,5,6,7,8,9
T=(2,2,2,2)-> N(2)=5 (nicht in T)
Länge 10:
T=(1,1,1,1,6)-> N(1)=5 (nicht in T)
T=(1,1,1,2,5)-> N(1)=4 (nicht in T)
T=(1,1,1,3,4)-> N(1)=4, N(3)=2 (nicht in T)
T=(1,1,2,2,4)-> N(1)=3 (nicht in T)
T=(1,1,2,3,3)-> N(1)=3, N(2)=2, N(3)=3
mögliche Folge: 31 22 33 1x 1y mit (x,y)=(4,5),(4,6),(4,7),(4,8),(4,9),(5,6),(5,7)....
T=(1,2,2,2,3)-> N(1)=2, N(2)=4 (nicht in T)
T=(2,2,2,2,2)-> N(2)=5, (nicht in T)
Länge 12:
T=(1,1,1,1,1,7)-> N(1)=6 (nicht in T)
T=(1,1,1,1,2,6)-> N(1)=5 (nicht in T)
T=(1,1,1,1,3,5)-> N(1)=5, N(3)=2 (nicht in T)
T=(1,1,1,1,4,4)-> N(1)=5, (nicht in T)
T=(1,1,1,2,2,5)-> N(1)=4,(nicht in T)
T=(1,1,1,2,3,4)-> N(1)=4,N(2)=2,N(3)=2(nicht mehr in T)
T=(1,1,2,2,2,4)-> N(1)=3 (nicht in T)
T=(1,1,2,2,3,3)-> N(1)=3, N(2)=3, N(3)=3 (nicht mehr in T)
T=(1,2,2,2,2,3)-> N(1)=2, N(2)=5 (nicht in T)
T=(2,2,2,2,2,2)-> N(2)=7
etc... für die Längen 14,16,18
![devil :devil:](./images/smilies/c06-devil.gif)
Physik ist keine grüne Ideologie.