The Thue-Morse sequence is a sequence of ones and zeros that if two people
take turns in the given order, the first persons turn for every '0' in the
sequence, the second for every '1'; then this is shown to give a fairer, more
equitable sharing of resources. (Football penalty shoot-outs for example, might
not favour the team that goes first as much if the penalty takers take turns
according to the Thue-Morse sequence and took 2^n penalties)

The Thue-Morse sequence of ones-and-zeroes can be generated by:

"When counting in binary, the digit sum modulo 2 is the Thue-Morse sequence"


Sharing fairly between two or more

Use this method:

When counting base b, the digit sum modulo b is the Thue-Morse sequence of fairer sharing between b people.


Task
Counting from zero;   using a function/method/routine to express an integer count in base b,

sum the digits modulo b to produce the next member of the Thue-Morse fairshare series for b people.



Show the first 25 terms of the fairshare sequence:

   For two people:
   For three people
   For five people
   For eleven people


Related tasks

   Non-decimal radices/Convert
   Thue-Morse


See also

   A010060, A053838, A053840: The On-Line Encyclopedia of Integer Sequences® (OEIS®)


#include <iostream>
#include <vector>
 
int turn(int base, int n) {
    int sum = 0;
    while (n != 0) {
        int rem = n % base;
        n = n / base;
        sum += rem;
    }
    return sum % base;
}
 
void fairshare(int base, int count) {
    printf("Base %2d:", base);
    for (int i = 0; i < count; i++) {
        int t = turn(base, i);
        printf(" %2d", t);
    }
    printf("\n");
}
 
void turnCount(int base, int count) {
    std::vector<int> cnt(base, 0);
 
    for (int i = 0; i < count; i++) {
        int t = turn(base, i);
        cnt[t]++;
    }
 
    int minTurn = INT_MAX;
    int maxTurn = INT_MIN;
    int portion = 0;
    for (int i = 0; i < base; i++) {
        if (cnt[i] > 0) {
            portion++;
        }
        if (cnt[i] < minTurn) {
            minTurn = cnt[i];
        }
        if (cnt[i] > maxTurn) {
            maxTurn = cnt[i];
        }
    }
 
    printf("  With %d people: ", base);
    if (0 == minTurn) {
        printf("Only %d have a turn\n", portion);
    } else if (minTurn == maxTurn) {
        printf("%d\n", minTurn);
    } else {
        printf("%d or %d\n", minTurn, maxTurn);
    }
}
 
int main() {
    fairshare(2, 25);
    fairshare(3, 25);
    fairshare(5, 25);
    fairshare(11, 25);
 
    printf("How many times does each get a turn in 50000 iterations?\n");
    turnCount(191, 50000);
    turnCount(1377, 50000);
    turnCount(49999, 50000);
    turnCount(50000, 50000);
    turnCount(50001, 50000);
 
    return 0;
}