# How does this method work to find prime numbers?

I'm curious about this pattern that I saw while adding many powers of two together, and then taking the prime factorisation of each result, and I'm curious as to why this occurs.

Here is the pattern:

$$2^n$$ will have the prime factors of $$2^n$$ For example, $$4$$ has $$2x2$$ as prime factors.

$$2^n + 2^{(n+1)}$$ will have prime factors of $$2^n* 3$$ For example, $$12$$ $$(4+8)$$ has $$2x2x3$$ as prime factors.

$$2^n + 2^{(n+2)}$$ will have prime factors of $$2^n* 5$$ For example, $$20$$ $$(4+16)$$ has $$2x2x5$$ as prime factors.

$$2^n + 2^{(n+1)} + 2^{(n+2)}$$ will have prime factors of $$2^n* 7$$

But this is where it changes:

$$2^n + 2^{(n+3)}$$ will have prime factors of $$2^n* 3^2$$ For example, $$36$$ $$(4+32)$$ has $$2x2x3x3$$

$$2^n + 2^{(n+1)} + 2^{(n+3)}$$ will then return to prime factors of $$2^n* 11$$

Iterating through every combination of powers we can sum up, I have found that we will get every prime number excluding $$2$$ (as it would factor into $$2^n$$) and all possible combinations of prime numbers excluding $$2$$ like so in ascending order for the prime factors:

$$3, 5, 7, 3*3, 11, 13, 3*5, 17, 19, 3*7, 23, 5*5, 3*3*3, 29...$$

$$2$$ and combinations with two are of course excluded because it would just be a prime factor of $$2^n$$.

A similar sequence begins with powers of $$3$$:

$$2*2, 5, 7, 2*2*2, 11, 13, 2*2*2*2, 17...$$

Removing all the numbers that sometimes disappear that are larger than the base m in m^n:

$$2, 3, 5, 7, 11, 13, 17, 23, 29...$$

We have the prime numbers.

I am curious as to how and why this works, and if it can be generalised.

• Welcome to MSE. Please use MathJax to format both, your questions and your answers :) – mrtaurho Oct 15 '18 at 20:50
• @mrtaurho thank you for this link, I'll start formatting it now. – user10176969 Oct 15 '18 at 20:51
• Use $\cdot$ instead of $*$. – Shine On You Crazy Diamond Oct 15 '18 at 21:08

## 1 Answer

Note that $$2^n+2^{n+1}=3\cdot 2^n\quad \quad 3=11_2\\ 2^n+2^{n+2}=5\cdot 2^n\quad \quad 5=101_2\\2^n+2^{n+1}+2^{n+2}=7\cdot 2^n\quad \quad 7=111_2$$ You can express your odd prime in binary and multiply by $$2^n$$ to get the pattern you are seeing.

• Ah, that makes a lot of sense. So, it take it that instead of generating the primes, I am just making all numbers excluding $2^n$ as I am including it in all equations, hence all numbers end with 1 in binary. Thanks, this makes a lot more sense now! – user10176969 Oct 15 '18 at 21:00