Die n. Permutation im Lucas-Lehmer-Code darstellen

[p. specht]

Abt. "Die n. Permutation im Lucas-Lehmer-Code darstellen"
=====================================
Dezimalzahlen sind so aufgebaut, daß links neu dazukommende Stellen jeweils um den Faktor 10 mehr wert sind als die vorherige Stelle rechts davon.

Lucas-Lehmer-Zahlen sind so aufgebaut, daß die Basis nicht fix 10 ist, sondern sich mit der Stellenzahl ändert. Der Stellenwert ist also nicht 10^(Stellenzahl-1) ist, sondern "Produkt aller Zahlen von 1 bis (Stellenzahl-1)".

Solche "Zahlen" haben die besondere Eigenschaft, daß sie lexikalische Permutationen von Elementen "ein-eindeutig" kennzeichnen. Man kann also z.B. die 12.354ste Umordnung (Permutation) der Elemente A B C D E F G H I direkt damit erzeugen, und muss nicht von 0 bis dorthin alle Umordnungen der Reihe nach ermitteln, um das herauszubekommen. Auch die umgekehrte Fragestellung ("Die wievielte Permutation ist dieses vorgegebene Muster eigentlich?") lässt sich so leichter klären. Praktische Anwendungen finden die Lucas-Lehmer-Codes z.B. beim Knacken von RSA-Cryptosystemen.

Hier ein kurzes Programm, das die (dezimal) n.te Umordnung in den Lucas-Lehmer-Code wandelt:

WindowTitle "Permutationen im eindeutigen Lucas-Lehmer Code darstellen"
CLS
AppendMenuBar 10, "Summe aufeinanderfolgenden Fakultäten mal ihrem Index ist Nächste_Fakultät-1"
' "http://de.wikipedia.org/wiki/Fakult%C3%A4tsbasiertes_Zahlensystem"
var xf!=0.797:var xr%=(%WinRight- %WinLeft-width(%Hwnd))+1
var yf!=0.72 :var yr%=(%WinBottom-%WinTop-height(%Hwnd))+1
var u%= 640*1.5 : var v%= 480*1.5
Window (u%-xr%)*xf!+xr%, (v%-yr%)*yf!+yr%
SetWindowPos %HWnd=(%maxx-u%)/2,((%maxy-v%)/2) - u%,v%
Declare s$,s!,n!,m!,m&,mmax&,prod!,lprod!,w&[200]

set("decimals",0)
Font 2:randomize
nomoi:
CLS rnd(8^8)
Print " Zugrundeliegende Frage: Welches Produkt aller Integerzahlen von n bis 1 "
Print " ergibt ein bestimmtes Ergebnis 'Fakultät von n' = \n ";
Input s$
s!=val(s$)
Print "\n (Rest)-Laufprodukt:"

ausloten:
prod!=1
WhileLoop 2147483647
  n!=&Loop
  lprod!=prod!
  Prod!=Prod!*n!
  case Prod!>S!:break
EndWhile
'print " Drüber:  Produkt 1 .. "; n!;" mit Produkt ";tab(40);Prod!
'print " Drunter: Produkt 1 .. "; n!-1; " mit Produkt ";tab(40);LProd!
m!=n!-1
m&=m!
case mmax&<m&:mmax&=m&
'print m!,
w&[m&]=w&[m&]+1
S!=s!-LProd!
case s!>0: goto "ausloten"


print
print 
'print " = ";mmax&;":";
WhileLoop mmax&,0,-1
  if W&[&Loop]>9:print "'";
      if W&[&Loop]>99:print "'";
        if W&[&Loop]>999:print "'";
        endif
      endif
  endif
  print W&[&Loop];
  'case (&Loop>1):print ",";
  
EndWhile

WaitInput
clear w&[]
mmax&=0
goto "nomoi"

'  Beispiel, um die n. Permuation tatsächlich zu ermitteln:
'  
'  "4041000" = 4*6!+0*5!+1*3!+0*2!+0*1!
'  Stellenwert = (len-pos)! = (7-1)! = 6!
'  Permutation erzeugen aus Fakultätsbasierter Zahl:
'  ps: 0123456
'  -4  0123456	4
'  -0  012356	0
'  -4  12356 	6
'  -1  1235		2		
'  -0  135		1
'  -0  35		3
'  -0  5              5

Die 4.041.000 Anordnung ist also: "4062135"

P.S.: Details hier