// 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 #include #include #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; } } } }