# Interesting or non-obvious finite subsets of the natural numbers

I was recently explaining to someone how to prove that there are infinitely many prime numbers, and I mentioned to them that it's not immediately obvious, upon first encountering the natural numbers, that there should be infinitely many primes. Their response was along the lines of, "what? Shouldn't it be obvious? If there are infinitely many natural numbers then shouldn't there be infinitely many prime numbers?"

I explained that, just because a set is infinite, that doesn't mean that a subset thereof is infinite, and pointed to the set of natural numbers less than 10 as a counterexample. This was an unsatisfactory counterexample in a way though since the set of natural numbers less than 10 is very obviously not infinite.

Are there some more interesting finite subsets of the natural numbers? Or interesting finite sets of other infinite sets?

-
How about the set of twin primes en.wikipedia.org/wiki/Twin_prime , actually is not known if it is finite but it could be a example, that it is hard to conclude.. – clark Sep 12 '12 at 9:40
This is a good example of a conjecture for which the "obviously infinite test" fails to be conclusive, but I'm looking for a finite subset where the "obviously infinite test" produces the wrong answer. – crf Sep 12 '12 at 9:49

How about $$\lbrace n: \text{n is odd and the regular n-gon is constructible}\rbrace?$$It is known that any prime $n$ must have the form $2^{2^k} + 1$ (a Fermat prime), of which the only known examples are $3, 5, 17, 257, 65537$. Fermat conjectured that all $2^{2^k}+1$ were prime, but now I think it is more widely thought that they are composite for $k>4$. Any other $n$ must be a product of distinct Fermat primes, so there is conjecturally only finitely many.

If you want something less conjecture-y, how about $$\lbrace n: \text{there exists a regular polyhedron with n faces}\rbrace?$$It's known that this set is $\lbrace 4,6,8,12,20\rbrace$.

-

Project Euler problem 23 begins as follows:

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of $28$ would be $1 + 2 + 4 + 7 + 14 = 28$, which means that $28$ is a perfect number.

A number $n$ is called deficient if the sum of its proper divisors is less than $n$ and it is called abundant if this sum exceeds $n$.

As $12$ is the smallest abundant number, $1 + 2 + 3 + 4 + 6 = 16$, the smallest number that can be written as the sum of two abundant numbers is $24$. By mathematical analysis, it can be shown that all integers greater than $28123$ can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

i.e. the set of numbers that are not the sum of two abundant numbers is finite.

-