[seqfan] Re: Sequence related to jittery function

[bacher]

Hi Jens,
Try

(a,b)=(38731904,40833784) for n=67108863

for k=27

(found randomly as follows:

Consider a,b and x=n as variables and set up a cycle
involving 27 of your two transformation different from 27
iterations of the first formula and apply it to (a,b)
getting (l_1,l_2) with l_1,l_2 two linear forms in a,b,x + constants.
Solve the system for a=l_1,b=l_2 getting affine expressions
with rational coefficients in terms of x.
It seems that x=-1/2 is always a solution to both
systems (I tried a few times with random compositions, this seems also  
not to depend on the cycle length 27)
Computing -1/2 modulo the numerator of the rational expression for a  
or b yields n,
plugging this values in the expressions for a and b, yields a,b.

Check that it works using your formulae (it did with my solution,
I hope I did not misstype it).

I did not really think this over: all these things should be rather trivial
to prove or this has to be a wonderful theory (I suspect that the
first assertion is true)

Best wishes Roland Bacher

Jens Voß <jens at voss-ahrensburg.de> a écrit :

> Let n be an integer greater than or equal to 2, and define
>
>   X_n := { (a, b) | 1 <= a < b <= n }
>
> to be the set of ordered pairs of distinct positive integers <= n.
>
> For every such pair (a, b) € X_n, let
>
>                  /  (b-a, b+a)      if  b+a <= n
>   j_n ((a,b)) := |
>                  \  (b-a, 2n+1-b-a) otherwise
>
> It is easy to see that
>
> (I)  j_n ((a,b)) € X_n for all (a, b) € X_n, i.e. j_n: X_n -> X_n and
> (II) j_n is injective.
>
> Since X_n is finite, j_n is bijective, i.e. a permutation of X_n.
>
> I am interested in the cycle representation of j_n; in particular,
> for every positive integer k, I would like to know the set of values
> of n for which j_n contains a cycle of length k.
>
> It is not too hard to show that
>
> (1) j_n has a cycle of length 1 (i.e. a fixed point) iff n == 2 (mod 5).
> (2) No n exists for which j_n has a cycle of length 2.
> (3) j_n has a cycle of length 3 iff n == 3 (mod 7) or n == 6 (mod 13).
>
> I suppose that larger cycle lengths can be classified in a similar way,
> but calculations quickly become rather tedious, so I used a simple
> computer program to calculate the cycle lengths of j_n for all values
> of n up to 3000 (after that, the program gets really slow).
>
> It appears that most smaller cycle lengths (except of course for 2) do
> come up eventually, the first stubborn exception being the number 27.
> However, the fact that this number (as well as the subsequent exceptions
> 38, 41, 53, 57, 62, 98, 103, 122, ...) does not show up as a cycle
> length of an j_n with n <= 3000 does not necessarily mean it can't do so
> for some larger n.
>
> So the questions I am facing right now are: Is 27 a cycle length of an
> f_n for some n? If so, what is the smallest such n? How about the other
> exceptions I mentioned? How many numbers k > 2 do not occur as cycle
> lengths; are there infinitely or finitely many or none at all?
>
> Does anyone have an idea on how to tackle these kind of problems? Has the
> function j_n perhaps already been studied by someone - it does not look
> too artificial to me!
> Ideally, if every integer > 2 is in fact a cycle length of some j_n, I'd
> like to submit the sequence of the smallest such n - currently, I am
> limited to the values for 3 through 26 and don't even know whether it
> can be extended beyond that point or whether it has a "hole" at k=27.
>
> Thanks and best regards
> Jens
>
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/