// Computes the sequence A277109:
//  Starting from 2^n+1, the length of the longest sequence of consecutive numbers
//  which all take the same number of steps to reach 1 in the Collatz (or '3x+1') problem.
//
// Requires gmp big number library (https://gmplib.org/)
// Compile with: g++ -o runMe A277109.c -lgmp
//
// By Dmitry Kamenetsky, 30th September 2016

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "gmp.h"

//NOTE: copies b so it doesn't get modified
int countSteps(mpz_t b)
{
  mpz_t a; mpz_init(a);
  mpz_set(a,b);
  
  int steps=0;
  
  while(1)
  {
    if (mpz_cmp_ui(a,1)==0) break;
    
    //if even then set a to a/2
    if (mpz_even_p(a))
    {
      steps++;
      mpz_divexact_ui(a,a,2);
    }
    //if odd then set a to (3a+1)/2, counts as two steps
    else
    {
      steps+=2;
      mpz_mul_ui(a,a,3);
      mpz_add_ui(a,a,1);
      mpz_divexact_ui(a,a,2);
    }
  }
  
  return steps;
}


int main (int argc, char **argv)
{ 
  mpz_t a; mpz_init(a);
   
  for (int n=0; true; n++)
  {
    mpz_ui_pow_ui(a,2,n);
    mpz_add_ui(a,a,1);

    int startHeight=countSteps(a);  

    //k=number of consecutive with the same height
    for (int k=1; true; k++)
    {
      mpz_add_ui(a,a,1);
      int height=countSteps(a);
            
      if (height!=startHeight)
      {        
        printf("%d %d\n",n,k);
        break;
      }
    }
  }
}