Fermat numbers | Rosetta Code | #24

URL to the problem page: http://rosettacode.org/wiki/Fermat_numbers


In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form F_n = 2^{2^n} + 1 where n is a non-negative integer.

Despite the simplicity of generating Fermat numbers, they have some powerful mathematical properties and are extensively used in cryptography & pseudo-random number generation, and are often linked to other number theoric fields.

As of this writing, (mid 2019), there are only five known prime Fermat numbers, the first five (F₀ through F₄). Only the first twelve Fermat numbers have been completely factored, though many have been partially factored.


Find and display here, on this page, the first 10 Fermat numbers - F₀ through F₉.

#include <iostream>

using namespace std;

int power(int a, int b) {

    int result = 1;

    for (int i = 0; i < b; i++) {

        result *= a;

    }

    return result;

}

int main() {

    int number[256] = { 0 }, number2[256] = { 0 }, powernumber[10] = { 0 }, carry = 0, tmp = 0;

    for (int i = 0; i < 10; i++) {

        powernumber[i] = power(2, i);

    }

    number[0] = 0;

    cout << "First 10 Fermat numbers are:" << endl;

    for (int i = 0; i <= powernumber[9]; i++) {

        carry = 0;

        tmp = 0;

        for (int j = 0; j < 256; j++) {

            tmp = (number[j] * 2) + carry;

            number[j] = ((number[j] * 2) + carry) % 10;

            carry = tmp / 10;

        }

        tmp = 0;

        for (int j = 0; j < 10; j++) {

            if (i == powernumber[j]) {

                for (int k = 0; k < 256; k++) {

                    number2[k] = number[k];

                }

                carry = (number2[0] + 1) / 10;

                number2[0] = (number2[0] + 1) % 10;

                for (int k = 1; k < 256; k++) {

                    if (carry == 0) {

                        break;

                    }

                    tmp = (number2[k] + carry);

                    number2[k] = (number2[k] + carry) % 10;

                    carry = tmp / 10;

                }

                tmp = 0;

                for (int k = 255; k >= 0; k--) {

                    if (number2[k] != 0 && tmp == 0) {

                        tmp++;

                    }

                    if (tmp > 0 || k == 0) {

                        cout << number2[k];

                    }

                }

                cout << endl;

                break;

            }

        }

        if (i == 0) {

            number[0]++;

        }

    }

    return 0;

}

CLICK TO SEE THE OUTPUT.