/* rpshuffle.c (reverse perfect shuffle)
 * 
 * (c) 2003 Jean-Paul Davalan <jpdvl@wanadoo.fr>
 * http://perso.wanadoo.fr/jean-paul.davalan/mots/pshuffle/index.html
 *
 * compile: gcc -o rpshuffle rpshuffle.c
 * usage: rpshuffle N
 * image:
 * ------------------------------
   #!/bin/sh
   rpshuffle 1000 > rev.g 
   # echo "set grid;plot 'rev.g' w steps;pause 50"|gnuplot  # (pour voir)
   echo "set grid;set nolabel;set term post eps color; \
         set output 'rev.eps';plot 'rev.g' w i lt 1"|gnuplot 
   pstoimg -antialias -aaliastext -type png -o rev.png rev.eps
 * ------------------------------
 */

#include <stdio.h>
#include <stdlib.h>

/* antécédent 
 * résolution de T_n(x) = y
 * */
long long ante(long long k, long long y) {
  if(y > 2*k) return y;
  if(y%2==0) return y/2;
  return k+(y+1)/2;
}

/* antécédent initial de 1
 * résolution de T_1(T_2(...(T_n(x))...)) = 1
 *
 * détermine x connaissant le rang n où apparaît l'image 1
 * */
long long val(long long n) {
  long long y=1, k;
  for(k=n;k>=1;k--) 
    y = ante(k,y);
  return y;
}

/* Pour n variant de 1 à N 
 * */

int main(int argc, char *argv[]) {
  long long n, y, N;
  if(argc<2) 
    printf("usage : %s N\n",argv[0]), exit(0);
  N = strtoul(argv[1], NULL, 10);
  for(n=1; n<= N; n++) {
    y = val(n);
    printf("%Ld %Ld\n",n, y);
  }
  return 0;
}