#include <stdio.h>
#include <gmp.h>

int main(int argc, char *argv[]){
  int i;
  mpz_t lucas, lucnew, mod, expo, two;

  mpz_init(lucas);
  mpz_init(lucnew);
  mpz_init(expo);
  mpz_init(mod);

  mpz_init(two);
  mpz_set_si(two,2);

  mpz_set_si(expo, (int)atoi(argv[1]));
  mpz_ui_pow_ui(mod,2,(int)atoi(argv[1]));
  mpz_sub_ui(mod,mod,1);
  mpz_set_si(lucas,4);

  gmp_printf("checking exponent %Zd\n", expo);

  for(i=2;i<mpz_get_si(expo);i++){
    mpz_powm(lucnew,lucas,two,mod);
    mpz_sub(lucnew,lucnew,two);
    //gmp_printf("S(%d) = (%Zd^2 - 2) mod %Zd = %Zd\n", i, lucas, mod, lucnew);
    mpz_set(lucas,lucnew);
  }
  gmp_printf("S(%d) = %Zd\n",i,lucas);
}