%I #37 Aug 01 2024 08:32:59
%S 0,1,0,4,31,70,3183,39814,261736,3371352,5739969,293929700,4459515314,
%T 7926716167,101442372383,1872646502198,24092766475124,49919329395336,
%U 75900705950969503,882317013876917212,32018280652900418322,883821770134261220212
%N Permutation rank of the initial state S of length n in an RC4-like Key Scheduling Algorithm with key comprising numbers 1 to n.
%C S is a permutation of {0,...,n-1} and a(n) is its rank among such permutations taken in lexicographic order, starting from rank 0 for the identity permutation.
%C S is constructed from the key by the following procedure, and here key[i] = i+1.
%C S[i] := i for i = 0 to n-1
%C j := 0
%C for i = 0 to n-1,
%C j := (j + S[i] + key[i]) mod n
%C swap S[i] and S[j]
%C The normal RC4 algorithm uses a state S of n=256 bytes and a(256) is its initial state rank on this key.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/RC4">RC4</a>.
%e a(8) = 39814 because starting with S=[0,1,2,3,4,5,6,7], the 8 swaps applied are:
%e i | j | S (after i-th swap).
%e --------------------------
%e 0 | 1 | [1, 0, 2, 3, 4, 5, 6, 7]
%e 1 | 3 | [1, 3, 2, 0, 4, 5, 6, 7]
%e 2 | 0 | [2, 3, 1, 0, 4, 5, 6, 7]
%e 3 | 4 | [2, 3, 1, 4, 0, 5, 6, 7]
%e 4 | 1 | [2, 0, 1, 4, 3, 5, 6, 7]
%e 5 | 4 | [2, 0, 1, 4, 5, 3, 6, 7]
%e 6 | 1 | [2, 6, 1, 4, 5, 3, 0, 7]
%e 7 | 0 | [7, 6, 1, 4, 5, 3, 0, 2]
%e And then the Lexicographic rank of S=[7, 6, 1, 4, 5, 3, 0, 2] is 39814.
%o (Python)
%o from sympy.combinatorics.permutations import Permutation
%o def ks(s):
%o j, S = 0, list(range(s))
%o for i in range(s):
%o j = (i + j + 1 + S[i]) % s
%o S[i], S[j] = S[j], S[i]
%o return S
%o def a(n): return Permutation(ks(n)).rank()
%o print([a(n) for n in range(1, 21)])
%K nonn
%O 1,4
%A _DarĂo Clavijo_, Jul 17 2024