Abulsme function information and definition: ------------------------------------------------------------------------------- Symbol: The symbol for the Abulsme function can be constructed as follows: 1) Draw an equilateral triangle with one side parrallel (sp) to the vertical and a vertex pointing to the right. 2) Draw a lines from the midpoint of the left side to the midpoints of the two other sides. 3) Draw a vertical line parrallel to the left side starting at thge vertex on the right and going down until it is at the same level as the bottom of the left side of the triangle. When actually writing something about the Abulsme function this should be used. (also when writing Abulsme has an accent on the final e) When typing the best thing to do would be to simply use "A" as the symbol. The Abulsme function takes two arguments, the first is called "length" for reasons which will soon become obvious, and the second is called "skip" for reasons which shall forever remain shrowded in mystery. So for example if we wished to say that the Abulsme function evaluated at length=3141593, skip=3141592 was equal to 2 (which it is) we would type: A(3141593,3141592)=2 Now of course, if we were actually writing this we would use the Abulsme symbol instead of the A. ------------------------------------------------------------------------------- Informal Definition: To find A(n,s) Given an ordered set F on n discreete elements: F={a(1),a(2),a(3),....,a(n)} Place it into a "window" of width s. That is write out the elements from left to right, up to down, with s elements per line. Produce a new set F' by traversing the set according to the following algorithim, adding elements to F' as they are traversed in F. Traversal Algorithim: 1) Start at the upper right hand element. 2) If there is an element below the current one then A) go to it B) go back to step 2 3) If there is a column to the left of the current one then A) go to it B) go back to step 2 4) You are finished!!!! F' can now be used to generate F'', and that to generate F''', etc. Now the main part of the definition: A(n,s) is the number of times the procedure must be repeated to reform F. In otherwords: F^(A(n,s))=F defines Abulsme!! (actually if F is the nxn matrix representation of the permutation of n elements defined by n and s this is actually correct notation.) ------------------------------------------------------------------------------- Example: Ok, lets find A(12,5) First let's pick an ordered set of 12 elements. How about: { A B C D E F G H I J K L } Lets make that first "window" A B C D E F G H I J K L Now lets traverse that and make our new set Upper right that's E so add it to our new set: { E .... We can go down so lets do it and get J { E J ..... Now we can't go down so go to the top of the column to the left and get D { E J D ..... I hope you get the pattern by now. Eventually we will get: { E J D I C H B G L A F K } This isn't the original pattern so we haven't got Abulsme yet. So we do it again ... { C A I L D G J B K E H F } and again.. { D E L K I B A J F C G H } and again.. { I C K F L J E A H D B G } again.. { L D F H K A C E G I J B } { K I H G F E D C B L A J } { F L G B H C I D J K E A } { H K B J G D L I A F C E } { G F J A B I K L E H D C } { B H A E J L F K C G I D } { J G E C A K H F D B L I } (In case you haven't figured out some patterns yet, the end is near) One more time..... { A B C D E F G H I J K L } Now in case you wern't keeping track we had to reform the set 12 times to get the original set back. SO..... A(12,5)=12 ------------------------------------------------------------------------------- Formal Definition: I'll keep this short. A(n,s) is defined when n and s are natural numbers such that 0<s<=n. A(n,s) is the order of the permutation B where: T(1)=s M(k)=(T(k-1)+s-n+abs(T(k-1)+s-n))div(2*abs(T(k-1)+s-n-1)+2) T(k)=(T(k-1)-M(k))mod(s*M(k)+2*n*abs(M(k)-1))+s*abs(M(k)-1) B={(1,T(1)),(2,T(2)),(3,T(3)),....(n,T(n))} Ha!! Take that for an obtuse definition!!!! ------------------------------------------------------------------------------- Pascal function: Here is a pascal function (TP 5.0) for finding A(n,s). It probably isn't at it's most efficient. I just haven't had time to fix it up. Note however that it does use the formal definition, as well as the (forthcoming) shortcut for finding A(n,s). function Abulsme (L,S: integer) : real; var T,M,C: array[1..5000] of integer; k,i,n,j,z: integer; B: array[1..5000] of boolean; u: boolean; q,g: extended; begin T[1]:=S; for k:=2 to L do begin M[k]:=(T[k-1]+S-L+abs(T[k-1]+S-L))div(2*abs(T[k-1]+S-L-1)+2); T[k]:=((T[k-1]-M[k])mod(S*M[k]+2*L*abs(M[k]-1)))+S*abs(M[k]-1); end; for i:=1 to L do B[i]:=false; n:=0; for i:=1 to L do if B[i]=false then begin j:=i; k:=0; repeat j:=T[j]; B[j]:=true; k:=k+1; until j=i; u:=true; z:=1; if i>1 then repeat if C[z]=k then u:=false; z:=z+1; until (z>n) or (not u); if u=true then begin n:=n+1; C[n]:=k; end; end; q:=C[1]; g:=q; z:=1; while z<n do begin while frac(q/c[z+1])<>0 do q:=q+g; z:=z+1; g:=q; end; Abulsme:=g; end; Comments??? What's a comment????? I would be interested in any improvements to this function. ------------------------------------------------------------------------------- Shortcut: Find only the first permutation of the ordered set. For example for n=12 s=5 the original set would be { A B C D E F G H I J K L } and the first permutation would be { E J D I C H B G L A F K } Now we can see that the A goes to where the J used to be, the B goes where the G used to be, etc. If we follow A we find the following A ---> J J ---> B B ---> G G ---> H H ---> F F ---> K K ---> L L ---> I I ---> D D ---> C C ---> E E ---> A Now we have gotten back to A, we have a loop of length 12. We notice that this loop contains every one of the elements so we have actually found the loops that all the elements traverse. The final result is that A(n,s) is the LCM of the lengths of the loops traveresed by each of the elements. A(12,5) is a very bad example as there is only one loop (actually called a cycle by those who study permutations). A better example would be A(11,3) A possible original set would be: {ABCDEFGHIJK} And the first permutation would be: {CFIBEHKADGJ} Here we get these cycles: A-->H-->F-->B-->D-->I-->C-->A Length: 7 E-->E Length: 1 G-->J-->K-->G Length: 3 Now the Lowest Common Multiple of 7, 1, and 3 is 21 so A(11,3)=21 This is the shortcut for finding A(n,s) that the pascal function uses. I beleive that it is the fastest way to find A(n,s). Please prove me wrong if it is possible!!!! ------------------------------------------------------------------------------- Properties: OK, here are the properties I believe Abulsme to have. The first few are obvious and can be proved rather simply using the informal definition (I haven't tried with the formal). The next few are just claims I am making. They are true for all values of n and s I have looked at but are certainly not proved. If a counterexample is found the claim is destroyed instantly. But I think they are true. The following conventions hold in these discriptions of properties: a,b, and c are positive integers n/d where n and d are two positive integers such that gcf(n,d)=1. Of course the properties only hold for values of x and y such that A(x,y) is defined. Here they are: A(a,1)=1 A(a,a)=A(a+1,a)=2 A(ab,b)=A(ab+1,b) A(a^b-1,a)=A(a^b,a)=A(a^b+1,a)=2b A(a^(n/d),a)=A(a^(n/d)+1,a)=n*[(d mod 2)+1] A(ab,b)/A(ab,a)=A(ab+1,b)/A(ab+1,a)=q where (2q=1 or q=1 or q=2) if 3a=>2b then A(b,a)=A(b+c,a+c) Now obviously some of these (or parts of some of these) are special cases of others. Check some of these out for yourselves. Obviosly these are very wierd properties which were completely unexpected (at least by me!) ------------------------------------------------------------------------------- Extention to rational numbers: If the concept of shuffling around elements in an ordered set is abandoned, and instead we use the model of a line of length L with each point on it marked with it's original length from the left end of the line which we then divide and reorder, we can successfully extend Abulsme so that it A(L,S) exists for all rational numbers L and S such that 0<s<=L. Following the methodology for integral values of L and S we first try to divide the line into several sections in a window of width S. Basically we imagine starting at the left end of the line and cutting it into sections of length S with some remanant of length < S left over. We arange these pieces as we did before with integral values of L and S, the first piece being on the top row with following pieces below it and the remainder on the left of the bottom row. Now we must traverse the setup inorder to produce a new line. With an integral domain we simply started in the upper right hand corner with a piece 1 unit long and traversed the window according to a simple algorithm. Our problem here is we can no longer convieniantly use pieces of length one. It might be possible to use length one segments and traverse the window in the same way as done previously, but problems are incountered. If l mod s is not integral then when we arrived at that location in the window some of the unit length we desire to pick up and add to the new line would be empty! Similarly if L is not integral then this problem occurs as we traverse the entire left side. This problem could be solved by simply taking the portions of the line that are in the section we would be picking up and ignore the blank area. I have not yet analysed this possibility. Instead I have used another possible way to overcome this problem. Namely, changing the length of the segment that is picked up while traversing the window. In order to do this we need a segment length that divides evenly into both L and S. Once we have found this length we realize the we have created a situation completely equivilant to using a unit section having greater values for L and S. If L=n1/d1 and S=n2/d2 where gcf(n1,d1)=gcf(n2,d2)=1 then we get the following relationship: A(n1/d1,n2/d2)=A(n1*d2,n2*d1) which serves to define Abulsme for the rational numbers in terms of the old definition for the natural numbers. In addition certain combinations of irrational values of L and S can be defined using this method, namely when L=n*S/d where as usual gcf(n,d)=1 with n and d integral. The unsatisfactory feature of this extention is that the most of the properties described in the properties section no longer hold true when L and S are not integral. Through the realtion above transformations of all the properties could be found which do hold for the rationals. In addition, more properties may be found using the extention. ------------------------------------------------------------------------------- 2448492.373 Jul (Revised 2448548.4969 Jul) (Revised 2448637.5747 Jul) (Revised 1 Jan 1995)