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)