I noticed while working on something else that `255` is

`15*17`, and

`65535` is

`255*257`. In other
words, it sounds like:

2^(2^n)-1 * 2^(2^n)+1 = 2^(2^(n+1)) - 1

Testing some numbers, it looks like this works:

`n` |
`2^(2^n)-1` |
`2^(2^n)+1` |
`2^(2*(n+1)) - 1` |

0 |
1 |
3 |
3 |

1 |
3 |
5 |
15 |

2 |
15 |
17 |
255 |

3 |
255 |
257 |
65535 |

4 |
65535 |
65537 |
4294967295 |

And in fact we can prove that it holds for all

`n`:

2^(2^n)-1 * 2^(2^n)+1
= 2^(2^n)*2^(2^n) + 2^(2^n) - 2^(2^n) - 1
= 2^(2^n)*2^(2^n) - 1
= 2^(2^n + 2^n) - 1
= 2^(2*2^n) - 1
= 2^(2^(n+1)) - 1

If

`255` is

`15*17` and

`15` is

`3*5`,
however, then as long as the numbers

`3, 5, 17, 257,` etc. are
prime we can build up prime factorizations. So

`255` would
factor into

`3*5*17` and

`65535` would factor into

`3*5*17*257`. This suggests that if you have a number in the
form

`2^(2^n)-1` then its prime factorization is the product of

`2^(2^i)+1` from

`i=0` to

`i=n-1`:

`n` |
`2^(2^n)-1` |
prime factorization |

1 |
3 |
3 |

2 |
15 |
3, 5 |

3 |
255 |
3, 5, 17 |

4 |
65535 |
3, 5, 17, 257 |

5 |
4294967295 |
3, 5, 17, 257, 65537 |

Neat!

But then I thought to try one more, and was very surprised:

`n` |
`2^(2^n)-1` |
prime factorization |

6 |
18446744073709551615 |
3, 5, 17, 257, 641, 65537, 6700417 |

Why did our nice pattern break? It looks like

`2^(2^5)+1` (or

`4294967297`) is

`641*6700417`. So not all numbers in
the form

`2^(2^n)+1` are prime, only the first five. The
sequence is the

Fermat numbers,
integer sequence

A000215. Such
are the dangers of extrapolation.

Comment via: google plus, facebook