Prime factor pattern in numbers one less than a power of 2
The number $4294967295$ has prime factors $3,5,17,257,\text{and }65537$.
The number is one less than a power of $2$, and its prime factors are all one more than a power of $2$. This made me wonder if this happens for other numbers that are one less than a power of $2$.
| $N$ | $2^{N}-1$ | $\text{Prime factors}$ |
|---|---|---|
| $1$ | $1$ | $-$ |
| $\boldsymbol{2}$ | $\boldsymbol{3}$ | $\boldsymbol{3}$ |
| $3$ | $7$ | $7$ |
| $\boldsymbol{4}$ | $\boldsymbol{15}$ | $\boldsymbol{3,5}$ |
| $5$ | $31$ | $31$ |
| $6$ | $63$ | $3,3,7$ |
| $7$ | $127$ | $127$ |
| $\boldsymbol{8}$ | $\boldsymbol{255}$ | $\boldsymbol{3,5,17}$ |
| $9$ | $511$ | $7,73$ |
| $10$ | $1023$ | $3,11,31$ |
| $11$ | $2047$ | $23,89$ |
| $12$ | $4095$ | $3,3,5,7,13$ |
| $13$ | $8191$ | $8191$ |
| $14$ | $16383$ | $3,43,127$ |
| $15$ | $32767$ | $7,31,151$ |
| $\boldsymbol{16}$ | $\boldsymbol{65535}$ | $\boldsymbol{3,5,17,257}$ |
It appears that each $N$ that is a power of $2$ gives a $2^N-1$ that has prime factors in a pattern of numbers one more than a power of $2$. This pattern continues with the number I first mentioned:
| $N$ | $2^{N}-1$ | $\text{Prime factors}$ |
|---|---|---|
| $2$ | $3$ | $3$ |
| $4$ | $15$ | $3,5$ |
| $8$ | $255$ | $3,5,17$ |
| $16$ | $65535$ | $3,5,17,257$ |
| $32$ | $4294967295$ | $3,5,17,257,65537$ |
Does this pattern continue indefinitely?
1 answer
Yes and no. The pattern of $2^{(2^N)}-1$ being the product of numbers one more than a power of $2$ continues without end. This can be demonstrated using induction (see conjecture and proof below). However, not all of these numbers are prime, so the pattern in the prime factors does not continue. It fails for the next number in the sequence after $4294967295$ due to one of the factors of this form being composite (and therefore also fails for all subsequent numbers in the sequence).
$$\begin{aligned}2^{64}-1&=18446744073709551615 \\ &= 3\times5\times17\times257\times65537\times4294967297 \\ &=(2^1+1)(2^2+1)(2^4+1)(2^8+1)(2^{16}+1)(2^{32}+1)\end{aligned}$$However, $4294967297=641\times6700417$ so this is not the prime factorisation, just a factorisation. This means the prime factorisation is no longer composed only of numbers one more than a power of $2$:
$$2^{64}-1=3\times5\times17\times257\times\boldsymbol{641}\times65537\times\boldsymbol{6700417}$$There follows a proof that there will always be a factorisation composed only of numbers one more than a power of $2$ (although that will not be a prime factorisation for any case beyond the 5 examples shown in the second table of the question).
Conjecture
$$\forall N\in\mathbb N:2^{(2^N)}-1=\prod_{n=0}^{N-1}\biggl(2^{(2^n)}+1\biggr)$$Proof
This holds for $N=1$
$$2^{(2^1)}-1=2^{(2^0)}+1$$If it holds for $N=M$
$$2^{(2^M)}-1=\prod_{n=0}^{M-1}\biggl(2^{(2^n)}+1\biggr)$$Multiply both sides by $2^{(2^M)}+1$
$$\begin{aligned}\biggl(2^{(2^M)}+1\biggr)\biggl(2^{(2^M)}-1\biggr)&=\biggl(2^{(2^M)}+1\biggr)\prod_{n=0}^{M-1}\biggl(2^{(2^n)}+1\biggr) \\\\ \biggl(2^{(2^M)}\biggr)\biggl(2^{(2^M)}\biggr)-1&=\prod_{n=0}^M\biggl(2^{(2^n)}+1\biggr) \\\\ 2^{(2^{M+1})}-1&=\prod_{n=0}^{(M+1)-1}\biggl(2^{(2^n)}+1\biggr)\end{aligned}$$This shows that it also holds for $M+1$.
It holds for $N=1$, and if it holds for $N=M$ then it also holds for $N=M+1$.
$\therefore$ by induction it holds $\forall N\in \mathbb N$
Motivation
The reason I chose to multiply both sides by $2^{(2^M)}+1$ is that this is the next term required on the right hand side to take the product from being $\prod_{n=0}^{M-1}$ to being $\prod_{n=0}^{M}$ as desired. The left hand side then happens to reach the desired form by multiplying out the parentheses.
0 comment threads
0 comment threads