Programa para encontrar los primeros N Números de Fermat

Los números de Fermat son números impares no negativos que son válidos para todos los valores de k>=0. Solo los primeros siete términos de la secuencia se conocen hasta la fecha. Primero, cinco términos de la serie son primos pero el resto no lo son. El k-ésimo término del número de Fermat se representa como 
 

La secuencia: 
 

3, 5, 17, 257, 65537, 4294967297, 18446744073709551617 
 

Para un N dado , la tarea es encontrar los primeros N números de Fermat.
Ejemplos: 
 

Entrada: N = 4 
Salida: 3, 5, 17, 257
Entrada: N = 7 
Salida: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617 
 

Planteamiento: 
Usando la fórmula mencionada anteriormente encontraremos el N- ésimo término de la serie.
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to print fermat numbers
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#define llu int128_t
using namespace std;
 
/* Iterative Function to calculate (x^y) in O(log y) */
llu power(llu x, llu y)
{
    llu res = 1; // Initialize result
 
    while (y > 0) {
        // If y is odd, multiply x with the result
        if (y & 1)
            res = res * x;
 
        // n must be even now
        y = y >> 1; // y = y/2
        x = x * x; // Change x to x^2
    }
    return res;
}
 
// Function to find nth fermat number
llu Fermat(llu i)
{
    // 2 to the power i
    llu power2_i = power(2, i);
 
    // 2 to the power 2^i
    llu power2_2_i = power(2, power2_i);
 
    return power2_2_i + 1;
}
 
// Function to find first n Fermat numbers
void Fermat_Number(llu n)
{
     
    for (llu i = 0; i < n; i++) {
         
        // Calculate 2^2^i
        cout << Fermat(i);
         
        if(i!=n-1)
            cout << ", ";
    }
}
 
// Driver code
int main()
{
    llu n = 7;
     
    // Function call
    Fermat_Number(n);
 
    return 0;
}

# Python3 program to print fermat numbers
 
# Iterative Function to calculate (x^y) in O(log y)
def power(x, y):
 
    res = 1 # Initialize result
 
    while (y > 0):
         
        # If y is odd,
        # multiply x with the result
        if (y & 1):
            res = res * x
 
        # n must be even now
        y = y >> 1 # y = y/2
        x = x * x # Change x to x^2
    return res
 
# Function to find nth fermat number
def Fermat(i):
     
    # 2 to the power i
    power2_i = power(2, i)
 
    # 2 to the power 2^i
    power2_2_i = power(2, power2_i)
 
    return power2_2_i + 1
 
# Function to find first n Fermat numbers
def Fermat_Number(n):
 
    for i in range(n):
 
        # Calculate 2^2^i
        print(Fermat(i), end = "")
 
        if(i != n - 1):
            print(end = ", ")
 
# Driver code
n = 7
 
# Function call
Fermat_Number(n)
 
# This code is contributed by Mohit Kumar

<script>
 
// Javascript program to print fermat numbers
 
/* Iterative Function to calculate (x^y) in O(log y) */
function power(x, y)
{
    let res = 1; // Initialize result
 
    while (y > 0) {
        // If y is odd, multiply x with the result
        if (y & 1)
            res = res * x;
 
        // n must be even now
        y = y >> 1; // y = y/2
        x = x * x; // Change x to x^2
    }
    return res;
}
 
// Function to find nth fermat number
function Fermat(i)
{
    // 2 to the power i
    let power2_i = power(2, i);
 
    // 2 to the power 2^i
    let power2_2_i = power(2, power2_i);
 
    return power2_2_i + 1;
}
 
// Function to find first n Fermat numbers
function Fermat_Number(n)
{
     
    for (let i = 0; i < n; i++) {
         
        // Calculate 2^2^i
        document.write(Fermat(i));
         
        if(i!=n-1)
            document.write(", ");
    }
}
 
// Driver code
    let n = 7;
     
    // Function call
    Fermat_Number(n);
 
</script>

Producción:  

3, 5, 17, 257, 65537, 4294967297, 18446744073709551617

Complejidad de tiempo: O(n * log n)

Espacio Auxiliar: O(1)

Referencia: https://en.wikipedia.org/wiki/Fermat_number