Wikipedia:Reference desk/Archives/Mathematics/2007 November 20

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 20

Bubble patterns

When doodling, I created some patterns of bubbles beside and/or within other ones, and I wondered if there is a systematic way to count how many different possibilities there are for a given number of bubbles. For example, with n=3 you can have 4 patterns: all distinct, one distinct and one inside the third, two distinct inside the third, or one inside another inside the third. I found 9 patterns for n=4 bubbles, but wasn't sure how to arrange things to count how many for 5. Is there an explicit formula for any n? 86.132.167.213 (talk) 19:05, 20 November 2007 (UTC)

This is essentially a problem in graph theory. We can construct a directed graph where each bubble is represented by a vertex. I understand that you do not allow bubbles to overlap, so two bubbles can either be disjoint or one is contained in the other. This means that each bubble has up to one parent, a bubble which directly contains it. This will be represented in the graph by an edge from the parent to the child. What we get is a directed forest, and the question is how many non-isomorphic directed forests exist for any n. I don't know for sure, but according to Tree (graph theory), no closed form formula is known for the number of non-isomorphic undirected trees, so I doubt one would be known for directed forests. -- Meni Rosenfeld (talk) 19:29, 20 November 2007 (UTC)

Argh, just as I finished writing a description of a somewhat systematic way to find the number for any n, apparently I clicked something and it vanished into thin air. So I'll just give an outline, and you can ask if it's not clear: Since a forest is a collection of trees, you can find the number of forests of size n using the partitions of n. If $t(n)$ is the number of trees of size n, the number of forests of size 4 is $t(1)^{4}+t(2)t(1)^{2}+t(2)^{2}+t(3)t(1)+t(4)=1+1+1+2+4=9$. You can find $t(n)$ recursively, by looking at the possibilities for $n-1$ and examining every way of adding a single vertex to each. -- Meni Rosenfeld (talk) 19:56, 20 November 2007 (UTC)

If we consider the universe in which these bubbles are drawn itself a bubble, the root of all other bubbles, these directed forests on n vertices simply become rooted trees with n+1 vertices (sequence A000081 in the OEIS).  --Lambiam 22:58, 20 November 2007 (UTC)

Unknown primes

What is the smallest known pair of primes for which it is possible that there is an unknown prime between them. For example if 37 was unknown than it would be 31 and 41. Thanks, *Max* (talk) 21:45, 20 November 2007 (UTC).

There is no meaningful answer. The concept of a "known" prime is not well-defined for relatively small primes, because it's so easy to compute billions of primes that people don't bother to store them. The Goldbach conjecture verification project at [1] has computed all 24,739,954,287,740,860 primes below 10¹⁸. They were only kept shortly in ram. PrimeHunter (talk) 23:14, 20 November 2007 (UTC)

I guess the smallest prime which has never been computed is somewhere between 10¹⁸ and 2·10¹⁸ but nobody knows the value. And the next millions of primes could be computed in seconds. PrimeHunter (talk) 23:21, 20 November 2007 (UTC)

Kind of by definition, no one knows the value. I saw a .sig once: Consider the set of all sets that have never been considered. Hey! They're all gone!. --Trovatore (talk) 23:25, 20 November 2007 (UTC)

Here's another way to look at it: Suppose that the current answer to your question was some primes $p_{1}$ and $p_{2}$. If they are close enough, you can look at all numbers between them, and either find a prime or conclude that there are none. If they are so far apart that this is intractable, there probably is a prime between them. So you start choosing numbers between them randomly, and test them from primality. It shouldn't take too long until you find a prime - it is smaller than $p_{2}$, and it is not known if there is a prime between $p_{1}$ and it. So whatever the case, given an alleged answer to the question, it can easily and quickly be made into not an answer. -- Meni Rosenfeld (talk) 23:23, 20 November 2007 (UTC)

I'd look between the largest known Mersenne prime, M44, and the second largest known prime, M33. Or you could look between M44 and 19,249 × 2^13,018,586 + 1 as seen in Prime_number#Location_of_the_largest_known_prime. Either way, you're sure to find some primes in between. I think it's provable that there are no sequential Mersenne primes. SamuelRiv (talk) 01:04, 21 November 2007 (UTC)

There are many pairs of non-consecutive large primes with no known prime between them, but the poster asked for the smallest pair. The 5000 largest known primes (may be missing a few) are at http://primes.utm.edu/primes/download.php. It follows from the proven Bertrand's postulate that there are no sequential Mersenne primes. PrimeHunter (talk) 01:27, 21 November 2007 (UTC)

Thanks for your help. *Max* (talk) 01:35, 21 November 2007 (UTC) P.S. Maybe we should start a small prime database?

Why? Primes can be computed faster than they can be downloaded and about as fast as they can be read from a hard disk. Anyway, there are several sites which list millions of primes. More than 10 million can be computed in a second on an ordinary PC. List of prime numbers has the first 500 primes and links to some longer lists. PrimeHunter (talk) 02:03, 21 November 2007 (UTC)