70
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Fermat primes? Not proved finite, but for the purposes of such conversations...? $\endgroup$ – B. Goddard Nov 13 at 12:09
  • 32
    $\begingroup$ Not a direct answer, but may help by analogy. Is the sum $1+1/2+1/3+1/4+\cdots$ infinite? What about $1+1/2^2+1/3^2+1/4^2+\cdots$? The fact that the first is $\infty$ and the second is $\pi^2/6$ demonstrates the necessity of proof over intuition when it comes to questions of infinity. $\endgroup$ – Matt Nov 13 at 20:06
  • 3
    $\begingroup$ I wonder if sequences that might be infinite, but less obviously so might help - is there maybe some point before "it's finite" at which most people will stop considering infiniteness obvious? Do they think there are infinitely many twin primes for instance? Or primes that end with the digits $123456789$? Or primes that are one less than a power of $2$? Or primes that are one more than a power of $2$? What about numbers that can't be written as a sum of three squares? $\endgroup$ – Milo Brandt Nov 13 at 21:51
  • 6
    $\begingroup$ Ask them if it is "obvious" that there are infinitely many elements just because there are infinitely many chemical compounds $\endgroup$ – John Coleman Nov 14 at 1:47
  • 3
    $\begingroup$ Why not just lead them with "but the more numbers there are the more possible divisors there are" and guide them to Euclid's proof. $\endgroup$ – jgn Nov 14 at 5:18

13 Answers 13

50
$\begingroup$

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.$$

$\endgroup$
  • 3
    $\begingroup$ I read the description several times but couldn't quite get it until the example $153 = 1^3 + 5^3 + 3^3$ $\endgroup$ – Burnsba Nov 14 at 15:16
  • 1
    $\begingroup$ That's the smallest example with more than one digit. I will add it to my answer. $\endgroup$ – José Carlos Santos Nov 14 at 15:18
  • 5
    $\begingroup$ I am a non-mathematician, and showing this to me as a counter argument would not be much helpful, because it's not obvious that this sequence ends. And the proof of the fact that it ends is most likely too complicated. $\endgroup$ – Tomáš Zato - Reinstate Monica Nov 15 at 10:01
  • 3
    $\begingroup$ @TomášZato If it was obvious that the sequence ends, then it would not be much of an example, right?! $\endgroup$ – José Carlos Santos Nov 15 at 14:27
  • 11
    $\begingroup$ @TomášZato The proof here isn't particularly complicated (ofc, that's very subjective). If $n$ has $k$ digits, you have $10^{k-1}\le n$. The maximum possible sum of the $k$th power of the digits is $k\cdot 9^k$ (for $n = 99\ldots 99$). If $n$ is also narcissistic (i.e. equal to that sum), $10^{k-1}\le k\cdot 9^k$. But this is only true for $k\le 60$ (can just plug it into Wolfram Alpha), so any base-10 narcissistic number must have 60 digits or less. Source $\endgroup$ – HTNW Nov 15 at 16:46
38
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ +1; I once gave a general audience talk which culminated in twin primes as an example. Also I mentioned Green--Tao theorem and the fact that sum of reciprocals of twin primes converges (and so does not settle the conjecture; this was interesting to some people) $\endgroup$ – T_M Nov 14 at 11:29
  • $\begingroup$ What is a twin prime? $\endgroup$ – Cory Klein Nov 14 at 21:35
  • 1
    $\begingroup$ @CoryKlein Twin primes are primes that are two apart (as illustrated in the answer). $\endgroup$ – Ethan Bolker Nov 14 at 21:51
  • $\begingroup$ I really think this is exactly the example not to give in this scenario. "But it feels like twin primes just go on forever" is just like the statement about normal primes. And then you can't even say they are wrong, in fact, the general opinion is that they are right, it just hasn't been proven yet. This is completely contrary to what the OP would like to demonstrate. $\endgroup$ – Apollys supports Monica Nov 16 at 0:07
  • $\begingroup$ @ApollyssupportsMonica Clearly the OP can use any of these answers they like. If I were explaining the need for a proof that something does or does not go on forever I would use a question to which we don't know the answer. That refutes any claim that something is "obvious" . $\endgroup$ – Ethan Bolker Nov 16 at 2:07
24
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "as no non-zero digit added to the left results in a new prime" -- I believe you that the statement is true, but it doesn't follow directly from your parenthetical, does it? Conceivably, there could be another left-truncatable prime with the same number of digits, that can be extended. $\endgroup$ – tomsmeding Nov 14 at 12:47
  • $\begingroup$ @tomsmeding Feel free to try it for yourself. Notice that the largest term starts with a 3 (meaning the only other digits available for a same-length prime must either be a 1 or a 2). Unfortunately, 157686312646216567629137 is not prime (factors: 19, 103, 659, 46662713, and 2620280423) nor is 257686312646216567629137 (factors: 3, 61, 1427, 18731411, and 52680003487). You an try the larger digits yourself. Its not so much that there aren't other 24 digit primes, but that for it to be in the sequence, all substrings by removing n leftmost digits must be prime. $\endgroup$ – Draco18s Nov 14 at 14:17
  • $\begingroup$ See A132394 for the order in which they are generated (eg. 2, 3, 5, 7, (1||_) 13, (2||_) 23, (4||_) 43...) and A227916 for "primes that remain prime when the leftmost digit is removed" which is an infinite sequence, as it does not require that the new prime also be in the sequence. A024785 is recursive. $\endgroup$ – Draco18s Nov 14 at 14:25
  • $\begingroup$ The link you gave describes a very different definition than the one introduced in the second sentence of your post. "Left-truncatable primes: every suffix is prime and no digits are zero." $\endgroup$ – Apollys supports Monica Nov 16 at 0:10
  • $\begingroup$ @ApollyssupportsMonica "every suffix" and "repeatedly remove left most digit" are the same thing. Every suffix of ABCD are BCD, CD, and D. You get these suffixes by repeatedly removing the leftmost digit. You start with a prime and every result is also a prime (which also means that every suffix is itself in the sequence). $\endgroup$ – Draco18s Nov 16 at 1:19
20
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Also unknown whether there infinitely many Sophie Germain primes, or Mersenne primes. (Before the computer era, $2^{127}-1$ was the largest explicitly known prime.) $\endgroup$ – DanielWainfleet Nov 14 at 3:26
  • 4
    $\begingroup$ The last is probably the easiest to understand. It obviously stops when you exceed 10 digits. $\endgroup$ – Barmar Nov 14 at 16:52
  • 1
    $\begingroup$ @Barmar Of all examples in answers, the last one is so fat the only one I understand. $\endgroup$ – Tomáš Zato - Reinstate Monica Nov 15 at 10:02
  • $\begingroup$ The question asked for examples appropriate for non-mathematicians. Why is being "too obvious" a problem? I upvoted the answer because of that example. $\endgroup$ – Barmar Nov 15 at 17:29
  • $\begingroup$ @Barmar Added back. $\endgroup$ – user76284 Nov 15 at 17:37
12
$\begingroup$

The number of faces which can form a regular solid.

4, 6, 8, 12, 20

$\endgroup$
  • 1
    $\begingroup$ The proof is left to the student as an exercise. $\endgroup$ – LowKeyEnergy Nov 14 at 22:22
  • $\begingroup$ Yes, but that short sequence does not exactly 'thin out'. $\endgroup$ – David R Tribble Nov 15 at 20:08
  • 3
    $\begingroup$ Yes, it exactly does. Here are the distances between elements: 2, 2, 2, 4, 8 . By the way... that even shorter sequence also "thins out". $\endgroup$ – LowKeyEnergy Nov 15 at 20:25
11
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ Just curious, what about $n$ that are smaller than d(n)³? $\endgroup$ – Eric Duminil Nov 15 at 20:54
  • 1
    $\begingroup$ @EricDuminil That would be OEIS sequence A056757. Apparently it's finite with $50967$ elements. Just fyi, if you search the first few terms of the sequence, you can normally find the OEIS entry and refer from there. I know as much about these sequences as you do :) $\endgroup$ – Jam Nov 16 at 13:23
  • $\begingroup$ thanks. Next question, is it still finite for any exponent? $\endgroup$ – Eric Duminil Nov 16 at 16:32
10
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Ye, but also numbers less than ten. I'd like a sequence whose fundamental property isn't something we can "just read off". (although to be fair I didn't say this...) $\endgroup$ – tomos Nov 13 at 11:52
  • $\begingroup$ @tomos It's kinda strange that so far all the answers are aither something obvious or someting way too advanced for a non-mathematician. Isn't there a middle ground? $\endgroup$ – Tomáš Zato - Reinstate Monica Nov 15 at 10:04
  • $\begingroup$ i couldn't find one :) $\endgroup$ – tomos Nov 15 at 14:51
  • $\begingroup$ Numbers less than 10 does not "thin out". It is also not finite, nor countable. $\endgroup$ – LowKeyEnergy Nov 20 at 3:35
8
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ I don't think this would work in casual conversation. "What do you do?" - "Read this book and I'll get back in a couple hours." - It also doesn't answer the question. $\endgroup$ – Mindwin Nov 14 at 15:35
  • $\begingroup$ As it seems, the question does not mention "casual" conversation, but one talking about mathematics. Also it does answer the question, if you also read the paper. $\endgroup$ – Konstantinos Gaitanas Nov 14 at 16:03
  • $\begingroup$ You didn’t offer a link to the paper but a link to a Wikipedia article about it. And the article does not answer the question, which is more concerned with large numbers than small ones. $\endgroup$ – WGroleau Nov 14 at 16:32
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ @PeterTaylor: Thanks for the feedback; I've edited it. =) $\endgroup$ – user21820 Nov 16 at 14:21
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This works for any pair of numbers whose greatest common factor is 1. For such numbers $a$ and $b$, you can write anything beyond $ab-(a+b)$ as a linear combination of the sort you've described. So, anything beyond $143-24=119$ can be written as a sum of $11$s and $13$s. $\endgroup$ – Benjamin Dickman Nov 25 at 21:53
3
$\begingroup$

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


$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.