## Fermat Numbers |
October 3rd, 2013 |

math |

I noticed while working on something else that

And in fact we can prove that it holds for all

Neat!

Why did our nice pattern break? It looks like

`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)) - 1Testing 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 |

`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)) - 1If

`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 |

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 |

`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