## Fermat Numbers | October 3rd, 2013 |

math |

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

More Posts:

- Playing to Lose
- Giving Up On Privacy
- Undisabling A Keyboard's Internal Speakers
- Optimizing Looks Weird
- Mike Mulligan and His Obsolete Technology

Older Post:

Newer Post: