#include #include // length of the array used to hold the sequence terms int arrayLength = 64; // array to hold very large sequence terms // number in brackets should be the same value as arrayLength long long aOfN[64] = {1, 0, 0, 0}; // keeping track if a sequence term reaches max digits bool maxDigitsReached = false; // keeping track of number of terms printed in case max digits aren't reached int termsPrinted = 0; // variable to control the maximum number of terms to be printed // if max digits aren't reached int maxTerms = 15000; // function to multiply very large terms by 4 void largeMultiplyBy4() { // for loop goes backwards to not add carry number before multiplying for (int i = arrayLength - 1; i >= 0; i--) { aOfN[i] *= 4; // don't carry for last entry of array if (i != arrayLength - 1) { // carrying excess over to next part of term number array while (aOfN[i] >= 1000000000000000000) { // parts of array except last entry // should be left no larger than 10 ^ 18 - 1 aOfN[i] -= 1000000000000000000; aOfN[i + 1]++; } } } } // function to add one to very large number // and carry over a one from one array entry to the next if needed void largeAddOne() { for (int i = 0; i < arrayLength; i++) { if (aOfN[i] == 999999999999999999 && i != arrayLength) { aOfN[i] = 0; } else { aOfN[i]++; break; } } } // function to test very large terms for being divisible by 3 bool isDivisibleBy3() { // array to copy the entries from main array into for use in this function long long aOfNCopy[arrayLength]; // copying term number array over for use in this function for (int i = 0; i < arrayLength; i++) aOfNCopy[i] = aOfN[i]; int sum = 0; // going through each part of the term number array for (int i = 0; i < arrayLength; i++) { // adding up each digit of the part of the term number for (long long j = 100000000000000000; j >= 1; j /= 10) { while (aOfNCopy[i] >= j) { aOfNCopy[i] -= j; sum++; } } } // checking for divisibility via sum of digits if (sum % 3 == 0) return true; else return false; } // function to divide very large terms by 3 void largeDivideBy3() { // variable to hold the remainder to be used to carry value over // to lower array entries if needed int remainder = 0; for (int i = arrayLength - 1; i >= 0; i--) { // find the remainder, then divide array entry by 3 and truncate // if there is a remainder remainder = aOfN[i] % 3; aOfN[i] /= 3; // carrying the remainder over if (i != 0) aOfN[i - 1] += remainder * 1000000000000000000; } } // printing the terms of the sequence out void printLargeNumber(FILE *b) { // boolean to make it so that no zeros are left out of printed terms bool addLeadingZeros = false; // printing different array entries in reverse order // to concatenate them together for (int i = arrayLength - 1; i >= 0; i--) { // last non-zero element in array is printed 1st with no leading zeros // all elements of term printed afterwards can have leading zeros if (aOfN[i] != 0 && addLeadingZeros == false) { fprintf(b, "%lld", aOfN[i]); addLeadingZeros = true; } else if (addLeadingZeros == true) { fprintf(b, "%018lld", aOfN[i]); } } } int main() { // creating file FILE *bfile; bfile = fopen("b346035.txt", "w+"); for (int n = 1; n <= maxTerms; n++) { // print the index of the term in the sequence // (e.g. 3rd term has index 3) fprintf(bfile, "%d ", n); // now print out the actual term printLargeNumber(bfile); // then make a new line fprintf(bfile, "\n"); // do math to get to next term in sequence if (isDivisibleBy3() == true) { largeDivideBy3(); } else { largeMultiplyBy4(); largeAddOne(); } if (aOfN[arrayLength - 1] >= 1000000000000000000) { termsPrinted = n + 1; maxDigitsReached = true; break; } } if (maxDigitsReached == true) { // print the index of the term in the sequence again fprintf(bfile, "%d ", termsPrinted); printLargeNumber(bfile); fclose(bfile); } return 0; }