Count distinct numbers constructed with k limited prime factors

Question

I can't understand the solution for the following problem:

Alice and Bob are playing a game.

In this game, the players are supposed to show at the same time using the hands an integer between 0 and 10 million. If the numbers shown by both players are equal, we have a tie. Otherwise, the players alternate writing down numbers in a piece of paper.

Let A be an integer shown by Alice in the beginning of the match and let B be an integer show by Bob, each number written down must be a product of |A - B| factors, with all factors being prime numbers, not necessarily distinct, belonging to the interval defined by the integers A and B.

Alice always play first.

For example, if A = 2 and B = 5, there are only 10 numbers (Bob Wins) which can be written down in the paper, which are:

8 = 2 x 2 x 2   
12 = 2 × 2 × 3  
20 = 2 × 2 × 5  
18 = 2 × 3 × 3  
30 = 2 × 3 × 5  
50 = 2 × 5 × 5  
27 = 3 × 3 × 3  
45 = 3 × 3 × 5  
75 = 3 × 5 × 5  
125 = 5 × 5 × 5  

The input has two numbers A and B as described.

The output has 1 line containing singly the match winner's name, assuming that both players play optimally. If the match ties, the output line shall contain singly the symbol '?'.

Here is a solution to this problem :

#include <stdio.h>
#include <math.h>
#include <string.h>

#define MAX 11234567

int primes[MAX], primeIndex;

inline void sieve(int limit) {

    bool sieve[limit];
    memset(sieve, 0 , sizeof(sieve));

    primeIndex = 0;
    primes[primeIndex] = 2;

    for (int i = 3; i < limit ; i += 2) {
        if(!sieve[i]){
            primes[++primeIndex] = i;
            for (int j = i + i; j <= limit; j += i) {
                sieve[j] = 1;
            }
        }
    }

    ++primeIndex;
}

inline int mul(int n) {
    int ret = 0;
    while (n > 0) {
        n /= 2;
        ret += n;
    }
    return ret;
}

inline void swap(int *a, int *b){
    int aux = *a;
    *a = *b;
    *b = aux;
}

int main(void) {
    int A, B;
    scanf("%d %d", &A, &B);

    if (A == B) {
        puts("?");
        return 0;
    }

    if (A > B) {
        swap(&A, &B);
    }


    sieve(B);

    int position_of_largest_prime;
    for (position_of_largest_prime = 0; position_of_largest_prime < primeIndex && primes[position_of_largest_prime] < A; ++position_of_largest_prime);

    int intervalBA = B - A;
    int primeCount = (primeIndex - position_of_largest_prime);

    puts(primeCount > 0 && mul(intervalBA + primeCount - 1) == mul(primeCount - 1) + mul(intervalBA) ? "Alice" : "Bob");

    return 0;
}

mul(intervalBA + primeCount - 1) == mul(primeCount - 1) + mul(intervalBA)

I don't understand the above condition. Is this some number theory problem ? Someone can help me to identify it ?

As pointed on the answer there is a lack of information on the description. Here is a link to the problem with a detailed description.

Answer 1

There are some details about the game which are not all that clearly explained. For example, it may be the case that Alice and Bob do not choose the same number at the beginning of the match, but there are no primes between their chosen numbers. If A = 14 and B = 16, is this a tie? If so, I do not think that the solution you provide is correct in all circumstances, since it appears that the output will be Bob rather than ? in the case that primeCount = 0. Also, I am assuming that whoever writes down the last number is the winner, but this is not stated clearly in the game description.

Your primary question, though, seems to be about the combinatorics involved. If I understand the game correctly, then if there are prime numbers between A and B, we need to determine whether the number of distinct products of | B - A | of these prime numbers is even or odd. The first question one might ask is, "How many distinct products are there?" One good way to count these is to use a stars and bars approach. You can read more about stars and bars here, but in your example game, there are |B-A| = 3 primes that need to be chosen, which I'll call the three stars, and two bars, the divider between the prime two and three and the divider between three and five. Thus *|*|* represents the product 2 x 3 x 5, **|*| represents the product 2 x 2 x 3, and *||** represents the product 2 x 5 x 5. Notice that the number of bars is one less than the number of primes in the interval between A and B inclusive. As a combinatorial problem, then, we are choosing the locations of the stars and bars within the sequence as a whole. The length of the whole sequence is intervalBA + primeCount - 1, and the number of star locations to choose is intervalBA.

If we were to calculate the number of different combinations that there are, then, we would calculate how many combinations of size intervalBA can be made from intervalBA + primeCount - 1 objects. In other words, we would compute intervalBA + primeCount - 1 choose intervalBA. However, that number could easily exceed the size of an integer on the computer you are working with, so direct computation is not feasible. Instead we should find a way to decide whether the result of that computation will be even or odd without directly computing the result.

Deciding whether the result is even or odd can be done using Lucas's theorem. I'll provide a link to a Wikipedia article about the theorem and a question on Math stack exchange where one of the comments discusses how Lucas's theorem can be applied to answer the question of whether a combination will be even or odd using the binary representations of numbers.

The mul function of the solution can also be used to determine whether the result is even or odd without directly computing the result. It does something slightly different than the solution that would be obtained with Lucas's theorem. It's not something I've seen before, but I eventually determined that mul(n) computes the largest power of 2 that will divide n factorial. Using ! to mean factorial, the basic definition of n choose k is usually given as n!/(k!(n-k)!). Thus the condition mul(intervalBA + primeCount - 1) == mul(primeCount - 1) + mul(intervalBA) is checking whether the largest power of 2 that divides the numerator is equal to the largest power of 2 that divides the denominator, where n is intervalBA + primeCount - 1 and k is intervalBA. If the largest power of 2 that divides the numerator is equal to the largest power of 2 that divides the denominator, then n choose k will be an odd number and Alice will win. Otherwise n choose k will be even and Bob will win.

Code like the code in the solution would be much easier to understand if it properly documented what it does.