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


import "/fmt" for Fmt
import "/sort" for Sort
 
var fairshare = Fn.new { |n, base|
    var res = List.filled(n, 0)
    for (i in 0...n) {
        var j = i
        var sum = 0
        while (j > 0) {
            sum = sum + (j%base)
            j = (j/base).floor
        }
        res[i] = sum % base
    }
    return res
}
 
var turns = Fn.new { |n, fss|
    var m = {}
    for (fs in fss) {
        var k = m[fs]
        if (!k) {
            m[fs] = 1
        } else {
            m[fs] = k + 1
        }
    }
    var m2 = {}
    for (k in m.keys) {
        var v = m[k]
        var k2 = m2[v]
        if (!k2) {
            m2[v] = 1
        } else {
            m2[v] = k2 + 1
        }
    }
    var res = []
    var sum = 0
    for (k in m2.keys) {
        var v = m2[k]
        sum = sum + v
        res.add(k)
    }
    if (sum != n) return "only %(sum) have a turn"
    Sort.quick(res)
    var res2 = List.filled(res.count, "")
    for (i in 0...res.count) res2[i] = res[i].toString
    return res2.join(" or ")
}
 
for (base in [2, 3, 5, 11]) {
    Fmt.print("$2d : $2d", base, fairshare.call(25, base))
}
System.print("\nHow many times does each get a turn in 50,000 iterations?")
for (base in [191, 1377, 49999, 50000, 50001]) {
    var t = turns.call(base, fairshare.call(50000, base))
    Fmt.print("  With $5d people: $s", base, t)
}