Post History
#4: Post edited
by
trichoplax
·
2025-03-27T03:11:45Z (6 days ago)
Explain that the pattern of factorisations are not in general prime factorisations
Yes, this pattern continues without end. This can be demonstrated using induction.- ## 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.
- 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.
#3: Post edited
by
trichoplax
·
2025-03-26T19:14:55Z (6 days ago)
Add motivation section
- Yes, this pattern continues without end. This can be demonstrated using induction.
- ## 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$
- Yes, this pattern continues without end. This can be demonstrated using induction.
- ## 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.
#2: Post edited
by
trichoplax
·
2025-03-26T18:53:49Z (6 days ago)
Make explicit the conclusion that it also holds for M+1
- Yes, this pattern continues without end. This can be demonstrated using induction.
- ## 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}$$
- 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$
- Yes, this pattern continues without end. This can be demonstrated using induction.
- ## 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$
#1: Initial revision
by
trichoplax
·
2025-03-25T23:20:12Z (7 days ago)
Yes, this pattern continues without end. This can be demonstrated using induction.
## 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}$$
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$