What is an example of a sequence which "thins out" and is finite?

Question

When I talk about my research with non-mathematicians who are, however, interested in what I do, I always start by asking them basic questions about the primes. Usually, they start getting reeled in if I ask them if there's infinitely many or not, and often the conversation remains by this question. Almost everyone guesses there are infinitely many, although they "thin out", and seem to say it's "obvious": "you keep finding them never mind how far along you go" or "there are infinitely many numbers so there must also always be primes".

When I say that's not really an argument there then they may surrender this, but I can see they're not super convinced either. What I would like is to present them with another sequence which also "thins out" but which is finite. Crucially, this sequence must also be intuitive enough that non-mathematicians (as in, people not familiar with our terminology) can grasp the concept in a casual conversation.

Is there such a sequence?

Answer 1

1) Numbers with distinct digits. (Somewhat obvious this is $<10^{10}$ though)

2) Numbers that are less than the sum of the individual digits raised to the 10th power.

Answer 2

An example would be the narcissistic numbers, which are the natural numbers whose decimal expansion can be written with $n$ digits and which are equal to sum of the $n$^th powers of their digits. For instance, $153$ is a narcissistic number, since it has $3$ digits and$$153=1^3+5^3+3^3.$$Of course, any natural number smaller than $10$ is a narcissistic number, but there are only $79$ more of them, the largest of which is$$115\,132\,219\,018\,763\,992\,565\,095\,597\,973\,971\,522\,401.$$

Answer 3

There are plenty such sequences on OEIS that are tagged with the keyword “fini”.

An example is A072938, “Highly composite numbers that are half of the next highly composite number”. This is a finite list, consisting of a mere 7 numbers (1, 2, 6, 12, 60, 360, 2520) which “thin out”. But it's a straightforward subset of the highly composite numbers (A002182), which is an infinite sequence.

Answer 4

The best answer is to give them to read The strong law of small numbers by Richard Guy.
This gives many examples which show that something which seems to be true is not true in general.

Answer 5

There are only finitely many:

• Heegner numbers (OEIS A003173).

• Idoneal numbers (OEIS A000926).

• Numbers $n$ such that $k^{n+1} \equiv_n k$ holds for all $k$ (OEIS A014117).

• Consecutive numbers whose prime factors are at most 7 (OEIS A085153).

• Numbers $n$ such that $\sigma_0(n) = \phi(n)$ (OEIS A020488).

• Numbers which are not the sum of distinct squares (OEIS A001422).

• Orders of sporadic simple groups (OEIS A001228).

• Numbers $n$ such that $n \leq \sigma_0(n)^2$ (OEIS A035033).

• Primes with distinct digits (OEIS A029743).

You can find other such finite sequences by searching keyword:fini on OEIS.

It is unknown whether there are infinitely many

• Twin primes (OEIS A014574).

• Fermat primes (OEIS A019434).

• Mersenne primes (OEIS A000668).

• Sophie Germain primes (OEIS A005384).

Answer 6

I think OEIS sequence A34884 is a good one as it's quite simple to explain to a non-mathematician, and it would be easy to imagine it could be infinite. This is the sequence of $n$ that are less than the square of the number of their divisors, $d(n)^2$.

For example, $12$ has $6$ divisors and is included, since it is less than $36$. We could feasibly expect it to be easy to find some large $n$ smaller than its $d(n)^2$, since large $n$ intuitively can have many factors. But alas, this is not the case as the sequence thins and ends with just $1260$.

Answer 7

You ask for a sequence that thins out, seems infinite but is finite. I suggest you follow up instead with an open question.

For people who know (or think they know, or think it's obvious) that the primes go on forever you could talk about twin primes. They begin $$ (3,5), (5,7), (11,13), (17, 19), (29,31), \ldots, (101, 103), \ldots $$ Clearly they thin out faster than the primes, but no one knows whether they stop entirely at some point.

If your audience still has your attention you can say that professionals who know enough to have an opinion on the matter think they go on forever. Then say how famous you would be (in mathematical circles) if you could answer the question one way or the other.

If they are still intrigued tell the story of Yitang Zhang's 2013 breakthrough showing that a prime gap less than $70$ million occurs infinitely often. That was the first proof that any gap had that property. The number has since been reduced to 246. If you could get it down to 2 you'd have the twin prime conjecture.

Answer 8

How about left-truncatable primes? That is, a number that when you remove the leftmost digit leaves a number that is still prime, repeated until only one digit remains (so 467 is prime, 67 is prime, 7 is prime, but not 233 because 33 is not prime). There are 4260 left-truncatable primes.

Not easy to prove that there are finitely many (if you allow 0, then there are infinitely many; eg. 107, for that sequence see A144714), but it mostly comes down to trying to construct a longer prime from a shorter one, which is an exercise that anyone can do on paper (provided you have a primality checker on hand).

Related, there are right truncatable primes as well, of which there are also finitely many (83); probably easier to doodle out on paper and find them all in a couple minutes.

The largest left-truncatable prime is 357686312646216567629137 (as no non-zero digit added to the left results in a new prime) and the largest right-truncatable is 73939133. There are also several related sequences (such as truncating from either side, truncating from both sides at once, or doing it in different bases).

Note that all truncations must be prime:

357686312646216567629137
57686312646216567629137
7686312646216567629137
686312646216567629137
86312646216567629137
...
7

All must be prime to be in the sequence.

Answer 9

Here is an example related to primes that essentially all number theory experts believe to be finite.

The even numbers $n$ that cannot be written as the sum of two primes in more than $\sqrt{n}$ ways.

By the standard probabilistic heuristic distribution of the primes, there should be asymptotically $Θ(n/\ln(n)^2)$ ways, so such even numbers should not only 'thin out' but also cease to exist above a certain point! Unfortunately, we still do not have a proof of this almost certainly true conjecture. But to the 'uninitiated', it may seem like there might be infinitely many such even numbers, as the last few are not that small and not that spread out, ending with $14438$, $14624$, $14648$, $12422$ and $15788$.

And here is an example that mathematicians do in fact know to be finite.

The number of positive integers that cannot be written as the sum of $16$ perfect fourth powers.

The sequence is Sloane's A046048 and the full list climbs quite slowly through until $6368$, $7152$, $8672$, $10992$, $13792$ and then just stops! Also rather interestingly, according to wikipedia, it was only shown in 2000 that every number from $13793$ to $10^{245}$ requires at most $16$ fourth powers. Then in 2005 it was finally shown that every number above $10^{216}$ and indivisible by $16$ (hence every number above $10^{220}$) requires at most $16$ fourth powers. So at least from the amount of effort mathematicians needed to prove the finiteness, it seems to be a highly non-trivially finite sequence!

Answer 10

Pollack[1] has several examples of the shape "for each positive integer, $k$, there are finitely many members of [interesting sequence of numbers] with [number theoretic function] bounded by $k$."

Examples:

• Theorem 1. For each $k$, there are finitely many odd perfect numbers, $N$, with $\omega(N) \leq k$.
• Theorem 2. For rational $\alpha$ and positive integer $k$, there are only finitely many $N$ for which $\sigma(N)/N = \alpha$ and $\Omega(N) \leq k$.
• Theorem 3. For each $k$, there are only finitely many amicable pairs $(N, M)$ for which $\Omega(N M) \leq k$. Theorem 4 is a similar result for $k$-sociable numbers and amicable $k$-tuples.
• Theorem 8. For each $k$, there are only finitely many amicable pairs $(N, M)$ for which $\omega(N M) \leq k$ and $\Omega(\gcd(N,M)) \leq k$.

These results may require a little more explaining than you might be looking for. But there is an easy contrast in Dirichlet's theorem : the sequence of primes congruent to $k \pmod{m}$ thins out, but is infinite. This seems like a natural "add a constraint" variation to the primes, similar to the above theorems, that contrasts with the finiteness in the above theorems.

[1] Pollack, Paul. (2012). Finiteness Theorems for Perfect Numbers and Their Kin. American Mathematical Monthly. 119. 10.4169/amer.math.monthly.119.08.670.

Answer 11

How about this:

The sequence of all numbers which can not be written as a sum of $11$'s and $13$'s.
(the numbers are abitrary, as it works for every pair of odd numbers with a distance of 2)

Depending on how high you choose the numbers, you'll obtain an arbitrarily long finite sequence that will thin out.

Answer 12

Divisible prefixes

Here's one you might find useful:

• Numbers like 1200549600848 have the property that the first $k$ digits form a number divisible by $k$. For example, 12 is divisible by 2, 120 is divisible by 3, 1200 is divisible by 4, 12005 is divisible by 5, and so on.

• If you're already talking with someone about primes, this divisibility property might build on what they already understand and therefore be relatively easy to grasp.

• It turns out there are only finitely many numbers with this property.

• In particular, you can prove that 3608528850368400786036725 is the only 25-digit number with this property. And this number can't be extended to a 26-digit number with this property. It follows that there are no higher numbers with this property (because if there were, the 26-length prefix of such a number would have this property).

---

Answer 13

In a rather different vein is a sequence involving proof of infini-tude of prime numbers having the form $mn+b$.

If we select $m=8,b=5$ for instance, we may prove that no finite list of $8n+5$ primes can contain all of them; for given the product $\Pi$ of any such list the polynomial $4\Pi^2+1$ is forced to have $8n+5$ primes factors not in the original list. This method works generally if $b^2\equiv1\bmod m$.

Erdos found a more advanced method that works for all $b$ relatively prime to $m$, including cases such as $m=15, b=8$ where $b^2\not\equiv1 \bmod m$. But this applies only if the prime factorization of $m$ meets certain constraints, which ultimately limits the sequence of linear-term coefficients:

$1,2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,26,28,30,36,40,42,48,50,54,60,66,70,72,78,84,90,102,108,114,120,126,132,138,150,156,168,180,210,240,270,300,330,390,420,630,840$ [natural numbers $m$ for which the reciprocals of smaller primes not dividing $m$ add up to less than $1$]

plus any additional divisors of these numbers (thus we can use the Erdos method with $m=7$ because $7$ divides $14$). Impressive as this extension is for linear-term coefficients up to $28$ (all of which are numbers in the above list or divisors thereof), it fizzles completely for linear-term coefficients greater than $840$. For latrger linear-term coefficients, and some others such as primes greater than $29$ and multiples of $32$, we have to resort to Dirichlet's Theorem or a similar complex analysis.