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