

A054639


Queneau numbers: numbers n such that the QueneauDaniel permutation {1, 2, 3, ..., n} > {n, 1, n1, 2, n2, 3, ...} is of order n.


15



1, 2, 3, 5, 6, 9, 11, 14, 18, 23, 26, 29, 30, 33, 35, 39, 41, 50, 51, 53, 65, 69, 74, 81, 83, 86, 89, 90, 95, 98, 99, 105, 113, 119, 131, 134, 135, 146, 155, 158, 173, 174, 179, 183, 186, 189, 191, 194, 209, 210, 221, 230, 231, 233, 239
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The troubadour Arnaut Daniel composed sestinas based on the permutation 123456 > 615243, which cycles after 6 iterations.
Roubaud quotes the number 141, but the corresponding QueneauDaniel permutation is only of order 47 = 141/3.
This appears to coincide with the numbers n such that a type2 optimal normal basis exists for GF(2^n) over GF(2). But are these two sequences really the same?  Joerg Arndt, Feb 11 2008
The answer is Yes  see Theorem 2 of the Dumas reference. [JeanGuillaume Dumas (JeanGuillaume.Dumas(AT)imag.fr), Mar 20 2008]
a(n) is the nth Tprime (Twist prime). For N >= 2, the family of twist permutations is defined by
p(m,N) == +2m (mod 2N+1) if 1 <= m < k = ceiling((N+1)/2),
p(m,N) == 2m (mod 2N+1) if k <= m < N.
N is Tprime if p(m,N) consists of a single cycle of length N.
The twist permutation is the inverse of the QueneauDaniel permutation.
N is Tprime iff p=2N+1 is a prime number and exactly one of the following three conditions holds;
(1) N == 1 (mod 4) and +2 generates Z_p^* (the multiplicative group of Z_p) but 2 does not,
(2) N == 2 (mod 4) and both +2 and 2 generate Z_p^*,
(3) N == 3 (mod 4) and 2 generate Z_p^* but +2 does not. (End)
The sequence name says the permutation is of order n, but P. R. J. Asveld's comment says it's an ncycle. Is there a proof that those conditions are equivalent for the QueneauDaniel permutation? (They are not equivalent for any arbitrary permutation; e.g., (123)(45)(6) has order 6 but isn't a 6cycle.) More generally, I have found that for all n <= 9450, (order of QueneauDaniel permutation) = (length of orbit of 1) = A003558(n). Does this hold for all n?  David Wasserman, Aug 30 2011


REFERENCES

Raymond Queneau, Note complémentaire sur la Sextaine, Subsidia Pataphysica 1 (1963), pp. 7980.
Jacques Roubaud, Bibliothèque Oulipienne No 65 (1992) and 66 (1993).


LINKS



FORMULA

a(n) >> n log n, and on the BatemanHornStemmler conjecture a(n) << n log^2 n. I imagine a(n) ≍ n log n, and numerics suggest that perhaps a(n) ~ kn log n for some constant k (which seems to be around 1.122).  Charles R Greathouse IV, Aug 02 2023


EXAMPLE

For N=6 and N=7 we obtain the permutations (1 2 4 5 3 6) and (1 2 4 7)(3 6)(5): 6 is Tprime, but 7 is not.  Peter R. J. Asveld, Aug 17 2009


MAPLE

QD:= proc(n) local i;
if n::even then map(op, [seq([ni, i+1], i=0..n/21)])
else map(op, [seq([ni, i+1], i=0..(n1)/21), [(n+1)/2]])
fi
end proc:
select(n > GroupTheory:PermOrder(Perm(QD(n)))=n, [$1..1000]); # Robert Israel, May 01 2016


MATHEMATICA

a[p_] := Sum[Cos[2^n Pi/((2 p + 1) )], {n, 1, p}];
Select[Range[500], Reduce[a[#] == 1/2, Rationals] &] (* Gerry Martens, May 01 2016 *)


PROG

(PARI)
is(n)=
{
if (n==1, return(1));
my( m=n%4 );
if ( m==4, return(0) );
my(p=2*n+1, r=znorder(Mod(2, p)));
if ( !isprime(p), return(0) );
if ( m==3 && r==n, return(1) );
if ( r==2*n, return(1) ); \\ r == 1 or 2
return(0);
}
for(n=1, 10^3, if(is(n), print1(n, ", ")) );


CROSSREFS

Not to be confused with Queneau's "sadditive sequences", see A003044.


KEYWORD

nonn


AUTHOR

Gilles EspositoFarese (gef(AT)cpt.univmrs.fr), May 17 2000


STATUS

approved



