# Euclid Euler Theorem

According to Euclid Euler Theorem, a perfect number which is even, can be represented in the form where n is a prime number and is a Mersenne prime number. It is a product of a power of 2 with a Mersenne prime number. This theorem establishes a connection between a Mersenne prime and an even perfect number.

```Some Examples (Perfect Numbers) which satisfy Euclid Euler Theorem are:

6, 28, 496, 8128, 33550336, 8589869056, 137438691328

Explanations:
1) 6 is an even perfect number.
So, is can be written in the form
(22 - 1) * (2(2 - 1)) = 6
where n = 2 is a prime number and 2^n - 1 = 3 is a Mersenne prime number.

2) 28 is an even perfect number.
So, is can be written in the form
(23 - 1) * (2(3 - 1)) = 28
where n = 3 is a prime number and 2^n - 1 = 7 is a Mersenne prime number.

3) 496 is an even perfect number.
So, is can be written in the form
(25 - 1) * (2(5 - 1)) = 496
where n = 5 is a prime number and 2^n - 1 = 31 is a Mersenne prime number.
```

Approach(Brute Force):

Take each prime number and form a Mersenne prime with it. Mersenne prime = where n is prime. Now form the number (2^n – 1)*(2^(n – 1)) and check if it is even and perfect. If the condtion satisfies then it follows Euclid Euler Theorem.

## C++

 `// CPP code to verify Euclid Euler Theorem ` `#include ` `using` `namespace` `std; ` ` `  ```#define show(x) cout << #x << " = " << x << " "; ``` ` `  `bool` `isprime(``long` `long` `n) ` `{ ` `    ``// check whether a number is prime or not ` `    ``for` `(``int` `i = 2; i * i <= n; i++) ` `        ``if` `(n % i == 0) ` `            ``return` `false``; ` `    ``return` `false``; ` `} ` ` `  `bool` `isperfect(``long` `long` `n) ``// perfect numbers ` `{ ` `    ``// check is n is perfect sum of divisors ` `    ``// except the number itself = number ` `    ``long` `long` `s = -n; ` `    ``for` `(``long` `long` `i = 1; i * i <= n; i++) { ` ` `  `        ``// is i is a divisor of n ` `        ``if` `(n % i == 0) { ` `            ``long` `long` `factor1 = i, factor2 = n / i; ` `            ``s += factor1 + factor2; ` ` `  `            ``// here i*i == n ` `            ``if` `(factor1 == factor2) ` `                ``s -= i; ` `        ``} ` `    ``} ` `    ``return` `(n == s); ` `} ` ` `  `int` `main() ` `{ ` `    ``// storing powers of 2 to access in O(1) time ` `    ``vector<``long` `long``> power2(61); ` `    ``for` `(``int` `i = 0; i <= 60; i++) ` `        ``power2[i] = 1LL << i; ` ` `  `    ``// generation of first few numbers ` `    ``// satisfying Euclid Euler's theorem ` ` `  `    ``cout << ``"Generating first few numbers "` `            ````"satisfying Euclid Euler's theorem "````; ` `    ``for` `(``long` `long` `i = 2; i <= 25; i++) { ` `        ``long` `long` `no = (power2[i] - 1) * (power2[i - 1]); ` `        ``if` `(isperfect(no) and (no % 2 == 0)) ` `            ``cout << ``"(2^"` `<< i << ``" - 1) * (2^("`  `                ``<< i << ``" - 1)) = "` `<< no << ````" "````; ` `    ``} ` `    ``return` `0; ` `} `

## PHP

 ` `

Output:

```Generating first few numbers satisfying Euclid Euler's theorem
(2^2 - 1) * (2^(2 - 1)) = 6
(2^3 - 1) * (2^(3 - 1)) = 28
(2^5 - 1) * (2^(5 - 1)) = 496
(2^7 - 1) * (2^(7 - 1)) = 8128
(2^13 - 1) * (2^(13 - 1)) = 33550336
(2^17 - 1) * (2^(17 - 1)) = 8589869056
(2^19 - 1) * (2^(19 - 1)) = 137438691328
```

Explanation of the outputs are provided in the the explanations to the examples above.