/* pshuffle.c 
 * Perfect Shuffle (trajectory of n)
 * (c) 2003 Jean-Paul Davalan <jpdvl@wanadoo.fr>
 * http://perso.wanadoo.fr/jean-paul.davalan/mots/pshuffle/index.html
 *
 * compile: gcc -o pshuffle pshuffle.c
 * usage: pshuffle n
 * image:
 * pshuffle 80 > traj; echo "set grid;plot 'traj' w l lt 3 lw 2;pause 50"|gnuplot
 */

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

int main(int argc, char *argv[]) {
  long long n, c, p, v, i;
  if(argc<2) 
    printf("usage : %s n\n",argv[0]), exit(0);
  n = strtoul(argv[1], NULL, 10);
  p = c = (n%2 == 0)? n/2 : (n+1)/2;
  v = n;
  printf("1 %Ld\n", v);
  printf("%Ld %Ld\n",p-1, v);
  for(i=0; v != 1; i++){
    v = (v <= c)? 2*v : 2*(v-c)-1;
    printf("%Ld %Ld\n",p+i, v);
    c = c+1;
  }
  printf("\n");
  return 0;
}