login
Queneau numbers: numbers n such that the Queneau-Daniel permutation {1, 2, 3, ..., n} -> {n, 1, n-1, 2, n-2, 3, ...} is of order n.
15

%I #108 Oct 19 2024 15:57:32

%S 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,

%T 86,89,90,95,98,99,105,113,119,131,134,135,146,155,158,173,174,179,

%U 183,186,189,191,194,209,210,221,230,231,233,239

%N Queneau numbers: numbers n such that the Queneau-Daniel permutation {1, 2, 3, ..., n} -> {n, 1, n-1, 2, n-2, 3, ...} is of order n.

%C The troubadour Arnaut Daniel composed sestinas based on the permutation 123456 -> 615243, which cycles after 6 iterations.

%C Roubaud quotes the number 141, but the corresponding Queneau-Daniel permutation is only of order 47 = 141/3.

%C This appears to coincide with the numbers n such that a type-2 optimal normal basis exists for GF(2^n) over GF(2). But are these two sequences really the same? - _Joerg Arndt_, Feb 11 2008

%C The answer is Yes - see Theorem 2 of the Dumas reference. [Jean-Guillaume Dumas (Jean-Guillaume.Dumas(AT)imag.fr), Mar 20 2008]

%C From _Peter R. J. Asveld_, Aug 17 2009: (Start)

%C a(n) is the n-th T-prime (Twist prime). For N >= 2, the family of twist permutations is defined by

%C p(m,N) == +2m (mod 2N+1) if 1 <= m < k = ceiling((N+1)/2),

%C p(m,N) == -2m (mod 2N+1) if k <= m < N.

%C N is T-prime if p(m,N) consists of a single cycle of length N.

%C The twist permutation is the inverse of the Queneau-Daniel permutation.

%C N is T-prime iff p=2N+1 is a prime number and exactly one of the following three conditions holds;

%C (1) N == 1 (mod 4) and +2 generates Z_p^* (the multiplicative group of Z_p) but -2 does not,

%C (2) N == 2 (mod 4) and both +2 and -2 generate Z_p^*,

%C (3) N == 3 (mod 4) and -2 generate Z_p^* but +2 does not. (End)

%C The sequence name says the permutation is of order n, but P. R. J. Asveld's comment says it's an n-cycle. Is there a proof that those conditions are equivalent for the Queneau-Daniel permutation? (They are not equivalent for any arbitrary permutation; e.g., (123)(45)(6) has order 6 but isn't a 6-cycle.) More generally, I have found that for all n <= 9450, (order of Queneau-Daniel permutation) = (length of orbit of 1) = A003558(n). Does this hold for all n? - _David Wasserman_, Aug 30 2011

%D Raymond Queneau, Note complémentaire sur la Sextaine, Subsidia Pataphysica 1 (1963), pp. 79-80.

%D Jacques Roubaud, Bibliothèque Oulipienne No 65 (1992) and 66 (1993).

%H P. R. J. Asveld, <a href="/A054639/b054639.txt">Table of n, a(n) for n = 1..10085</a>

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 42.9 "Gaussian normal bases", pp. 914-920

%H P. R. J. Asveld, <a href="http://dx.doi.org/10.1016/j.dam.2011.07.019">Permuting operations on strings and their relation to prime numbers</a>, Discrete Applied Mathematics 159 (2011) 1915-1932.

%H P. R. J. Asveld, <a href="http://eprints.eemcs.utwente.nl/20685/">Permuting operations on strings and the distribution of their prime numbers</a>, TR-CTIT-11-24, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.

%H P. R. J. Asveld, <a href="http://eprints.eemcs.utwente.nl/15678/">Some families of permutations and their primes </a> (2009), TR-CTIT-09-27, Dept. of CS, Twente University of Technology, Enschede, The Netherlands.

%H P. R. J. Asveld, <a href="http://eprints.eemcs.utwente.nl/23422/">Queneau Numbers--Recent Results and a Bibliography</a>, University of Twente, 2013.

%H P. R. J. Asveld, <a href="http://purl.utwente.nl/publications/67513">Permuting Operations on Strings-Their Permutations and Their Primes</a>, Twente University of Technology, 2014.

%H Michèle Audin, <a href="http://images-archive.math.cnrs.fr/Poesie-spirales-et-battements-de.htm">Poésie, Spirales, et Battements de Cartes</a>, Images des Mathématiques, CNRS, 2019 (in French).

%H M. Bringer, <a href="http://www.numdam.org/item?id=MSH_1969__27__13_0">Sur un problème de R. Queneau</a>, Math. Sci. Humaines No. 25 (1969) 13-20.

%H Jean-Guillaume Dumas, <a href="http://hal.archives-ouvertes.fr/hal-00188240">Caractérisation des Quenines et leur représentation spirale</a>, Mathématiques et Sciences Humaines, Centre de Mathématique Sociale et de statistique, EPHE, 2008, 184 (4), pp. 9-23, hal-00188240.

%H G. Esposito-Farese, <a href="http://www.cpt.univ-mrs.fr/~gef/oulipo7.html#150300">C program</a>

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%F a(n) = (A216371(n)-1)/2. - _L. Edson Jeffery_, Dec 18 2012

%F a(n) >> n log n, and on the Bateman-Horn-Stemmler 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

%e 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 T-prime, but 7 is not. - _Peter R. J. Asveld_, Aug 17 2009

%p QD:= proc(n) local i;

%p if n::even then map(op,[seq([n-i,i+1],i=0..n/2-1)])

%p else map(op, [seq([n-i,i+1],i=0..(n-1)/2-1),[(n+1)/2]])

%p fi

%p end proc:

%p select(n -> GroupTheory:-PermOrder(Perm(QD(n)))=n, [$1..1000]); # _Robert Israel_, May 01 2016

%t a[p_] := Sum[Cos[2^n Pi/((2 p + 1) )], {n, 1, p}];

%t Select[Range[500],Reduce[a[#] == -1/2, Rationals] &] (* _Gerry Martens_, May 01 2016 *)

%o (PARI)

%o is(n)=

%o {

%o if (n==1, return(1));

%o my( m=n%4 );

%o if ( m==4, return(0) );

%o my(p=2*n+1, r=znorder(Mod(2,p)));

%o if ( !isprime(p), return(0) );

%o if ( m==3 && r==n, return(1) );

%o if ( r==2*n, return(1) ); \\ r == 1 or 2

%o return(0);

%o }

%o for(n=1,10^3, if(is(n),print1(n,", ")) );

%o \\ _Joerg Arndt_, May 02 2016

%Y Not to be confused with Queneau's "s-additive sequences", see A003044.

%Y A005384 is a subsequence.

%Y Union of A163782 (Josephus_2-primes) and A163781 (dual Josephus_2-primes); also the union of A163777 (Archimedes_0-primes) and A163778 (Archimedes_1-primes); also the union of A071642/2 (shuffle primes) and A163776/2 (dual shuffle primes). - _Peter R. J. Asveld_, Aug 17 2009

%Y Cf. A216371, A003558 (for which a(n) == n).

%K nonn,changed

%O 1,2

%A Gilles Esposito-Farese (gef(AT)cpt.univ-mrs.fr), May 17 2000