For both provided features, the whole document is scanned for sectioning commands and for newcommand-commands.

To construct such a solution, we first note the following: , a very basic identity of binomial coefficients. This means . However, this corresponds to the number of possible pairs of sets with . For convenience we can simply say .

Now we desribe the process of choosing elements from the -element set . The obvious way is to choose simply elements. This results in possibilities.

The other way to choose elements would be as follows: We partition our set into two sets (namely and . Then, in the first step we pick elements from the set ( random between 0 and ). Since we are allowed to take elements in total, we pick elements from the set . This means, we picked elements in total. In the first step, we can pick or or or … or elements. Thus, in total we have possibilities.

So, if we want to construct a bijection, we simply take all elements coming from and put them into and all elements coming from and generate the complement set to obtain for the pair .

The functions encode and decode do most of the work. Note that this implementation includes also the number 0 (by accident, since computers usually index lists starting with 0). However, as mentioned in the original post, it’s not a very practicable solution, since we have to deal with quite large numbers and factorize them.

The program can probably be sped up by explicitly stating the types of the functions and compiling the program. I omitted them because my compiler always complained about incompatible types ([Int] and [Integer]).

The program can be tested by simply calling decode (encode [1,2,3,4,5]) or similar.

It has to be compiled specifying some specialties:

gcc -D"q(a,b)"="*c-a||b;" -o pmmbf pmmbf.c

and can be invoked as follows:

./pmmbf ",[-.]" 1000

The first argument specifies the brainf***-program to be run, the second argument determines the size of the tape.

Of course, he was just kidding: Such a number can’t exist, because a number is divisible by 3 if and only if its digit sum is divisible by 3. So, it is no problem to find a number to prepend such the digit sum of the resulting number is divisible by 3. That implies that the resulting number is not a prime.

However, it’s possible to prove a similar theorem…

We prove the following: For any number , there is a number with digits, such there are infinitely many primes ending with this -digit number.

To prove this, let us first consider the case . This means, that we want to show that there is a number such there are infinitely many primes ending in this number .

It’s a well-known fact that there are infinitely many primes. Thus, due to the pigeonhole principle, there must be a number in to occur infinitely many often. Thus, such a number exists.

Now, it’s no big step to generalize this to more digits: Assume we found our number with the desired property. I.e. there are infinitely many primes ending with . Now, we “cross out” all primes ending not in . So, we are now only considering the infinitely many primes ending in

But now, according to the pigeonhole principle, there must be a number such that there are infinitely many primes whose next-to-last digit is . That means, there are infinitely many primes ending in the digits .

Now, we iterate the procedure: We cross out all primes not ending in . This yields – again – infinitely many primes ending in . So we can argument the same way as before: There must be – due to pigeonhole principle – a number $n”$ such that infinitely many primes end in .

We can continue this procedure as long as we want – since there are infinitely many primes.

So, this means, there are arbitrarily large numbers (concatenated digits ) such that there are infinitely many primes ending with exactly the digits .

I like this proof because it is – once again – a proof of existence that does not explicitly construct a solution to the problem, but just shows that there is one.

We prove that this formula is satisfiable.

First, we consider the following random experiment: We assign each occuring variable (in the whole formula) a value 1 or 0 generating a random assignment of values to variables. Then, the probability that one specific clause is satisfied, is . This is due to the fact that one single clause evaluates to false only for one single assignment of variables (the variables occuring in the clause).

So, we now introduce the following: For each clause , we introduce an indicator variable indicating whether the corresponding clause is satisfied or not (i.e. iff is satisfied by our randomly generated assignment). The above considerations yield , where denotes the expected value of and is the probability of event .

Moreover, we now define as the sum over all indication variables. This means, stands for the number of satisfied clauses. We compute the expected value (since the expected value is linear). This means, we can conclude .

This can be simplified to . This means, in average, we have clauses satisfied. Due to the principle of average, this means, that there must exist some assignment of variables such that the number of satisfied clauses .

But since must be a natural number, this can be restated so that we now know that there must exist an assignemt of variables such that , which is the next natural number. But since is exactly the number of clauses, we now know that all clauses are satisfied, and, thus, the whole formula is satisfied.

Thus, the formula is satisfiable.

I personally find this proof so nice because usually existence proofs involve some routine to construct an explicit solution which is then used as a proof of existence. However, this existence proof purely relies on the averaging principle, and proves the existence of a satisfying assignment without explicitly constructing it. Moreover, the proof uses the probabilistic method, which I consider a very elegant technique.

We can reconstruct the set from a number by taking it’s prime factorization and applying to each prime factor.

Note that the above does not preserve the order of the elements (multiplication is commutative), since we are considering sets. But what happens, if we want to encode ordered tuples this way?

So, let us now consider a tuple , that we want to encode into a number. For now, we exclude 0 from the natural numbers, but the idea can be easily extended to work with 0 as well.

For this, we can derive another encoding from the first. The problem is that – since multiplication is associative – we can not map the generated primes to the elements in , since we therefore must somehow know the position of the element.

We can circumvent this problem as follows: Starting with , we pick the prime . We continue with , but we can not simply choose , since then and would be mapped to the same number.

So, we do the following: For , we start counting primes at and thus, pick the number . Similarily, for we pick .

The rule: For , we choose . Thus, we get the encoding function .

That is, we ensure that the prime numbers are strictly increasing. If we want to reconstruct the tuple given a number, we take the prime factorization, sort the prime numbers, and apply to each prime. Now, we compute the distances between two consecutive elements, and get the elements from the tuple.

Example

I don’t offer a proof, but an example to see how it’s done.

Take . To encode this, we have to compute , which can be evaulated to .

This yields . So, we encode the tuple as 99603.

If we want to recompute the tuple from the given number 99603, we do the following: We prime-factorize: 99603 = 3 * 17 * 31 * 61. Thus, we know that the primes 3, 17, 31 and 61 were used. Now, we compute for each of them and get: , , , .

So, now we consider the numbers 2, 7, 11, 18. We now can conclude, that the first number must have been 2, the second number must have been 7-2=5, while the third number must have been 11-7=4 and the last number must have been 18-11=7. This yields the tuple (2,5,4,7).

Remarks

The presented encoding is (probably) of no practical relevance due to the following:

• The size of the prime numbers (not to speak about the product of them) grows rapidly. It is not possible to efficiently store numbers generated by tuples containing 100 elements
• Decomposing a number into its prime factors seems to be rather computationally expensive. It is known to be in NP and coNP, but it is suspected to lie outside of P.

However, the presented encoding reveals a very nice result: It is clear that the above construction can be applied to any tuple of natural numbers and always yields a natural number. Moreover, we can factorize every natural number, and, thus, generate a tuple from every natural number.

We didn’t show this, but it is evident that no two sequences yield the same number. Simply assume that any two tuples would yield the same number: This would immediately imply that both tuples must have the same number of elements. But if the elements are distinct, this will directly lead to different primes and another resulting number.

So, this means, that each tuple has a natural number (greater that 1, since 1 is no prime), and each natural number corresponds to exactly one tuple. That means, that in essence, we have as many tuples as natural numbers, since we generated a bijection (aside from the number 1). Thus, the tuples of natural numbers are enumberable: We simply start counting 2, 3, 4, 5, 6, 7, … and compute the corresponding tuple for each number.

• pushes negations as close to the predicates as possible
• ensures that variable names are unique
• brings quantifiers to front
• eliminates existential quantifiers

I can’t guarantee that it is working correctly, but at least for my example, it worked out quite well.

Note that this implementation is not optimal at all. There are several unelegant and inefficient passages, which is most due to the fact that I didn’t do very much in Haskell in the past. However, I always liked the way one can express and transform some kind of algebraic formulas in this programming language.

This can be quite naturally seen by reducing the NP-complete HAMILTON to the given problem: Given any graph , we interpret its vertices as guests. We say that two guests get alogn with each other if there is an edge connecting the corresponding vertices. This is a quite natural tranformation of HAMILTON to our problem.

The rest is easy: We can easily show that the given problem is in NP, because we can check the correctness of a solution in polynomial time. Thus, the problem itself is NP-complete.

Special cases might be solved efficiently

Even if this problem can (probably) not be solved efficiently generally, we note the following: If we impose some restrictions onto the original problem (guests at a festival), we might be able to compute a solution efficiently. E.g. we can express guests as numbers and say that two guests get alogn with each other if their numbers are both even resp. odd. Then, we just have to check whether there are as many even as odd numbers and put them alternating (even-odd-even-odd-…) one after another.

Another example could be that two numbers (guests) get along, if their sum is less than a given maximum value. In this case, we can employ a greedy algorithm to construct an optimal solution.

So the question arises, why – in those cases – the reduction from HAMILTON isn’t working. It is simply the fact that not all graphs (i.e. not all HAMILTON problems) can be transformed into problem instances with the additionally imposed restrictions. For example, consider the even-odd case: A graph containing 3 vertices (guests) and no edges (i.e. no guest is compatible to any other guest) – this graph does not correspond to any valid problem instance with the restriction that two guests get along if their numbers are both even resp. odd.

In particular, when reducing problems, we have to ensure that each original problem has a corresponding case in the target problem description.