Fairshare between two and more

From Rosetta Code
Task
Fairshare between two and more
You are encouraged to solve this task according to the task description, using any language you may know.

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
References


C[edit]

#include <stdio.h>
#include <stdlib.h>
 
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) {
int i;
 
printf("Base %2d:", base);
for (i = 0; i < count; i++) {
int t = turn(base, i);
printf(" %2d", t);
}
printf("\n");
}
 
void turnCount(int base, int count) {
int *cnt = calloc(base, sizeof(int));
int i, minTurn, maxTurn, portion;
 
if (NULL == cnt) {
printf("Failed to allocate space to determine the spread of turns.\n");
return;
}
 
for (i = 0; i < count; i++) {
int t = turn(base, i);
cnt[t]++;
}
 
minTurn = INT_MAX;
maxTurn = INT_MIN;
portion = 0;
for (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);
}
 
free(cnt);
}
 
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;
}
Output:
Base  2:  0  1  1  0  1  0  0  1  1  0  0  1  0  1  1  0  1  0  0  1  0  1  1  0  0
Base  3:  0  1  2  1  2  0  2  0  1  1  2  0  2  0  1  0  1  2  2  0  1  0  1  2  1
Base  5:  0  1  2  3  4  1  2  3  4  0  2  3  4  0  1  3  4  0  1  2  4  0  1  2  3
Base 11:  0  1  2  3  4  5  6  7  8  9 10  1  2  3  4  5  6  7  8  9 10  0  2  3  4
How many times does each get a turn in 50000 iterations?
  With 191 people: 261 or 262
  With 1377 people: 36 or 37
  With 49999 people: 1 or 2
  With 50000 people: 1
  With 50001 people: Only 50000 have a turn

Factor[edit]

Works with: Factor version 0.99 2020-01-23
USING: formatting kernel math math.parser sequences ;
 
: nth-fairshare ( n base -- m )
[ >base string>digits sum ] [ mod ] bi ;
 
: <fairshare> ( n base -- seq )
[ nth-fairshare ] curry { } map-integers ;
 
{ 2 3 5 11 }
[ 25 over <fairshare> "%2d -> %u\n" printf ] each
Output:
 2 -> { 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 }
 3 -> { 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 }
 5 -> { 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 }
11 -> { 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4 }

Go[edit]

package main
 
import (
"fmt"
"sort"
"strconv"
"strings"
)
 
func fairshare(n, base int) []int {
res := make([]int, n)
for i := 0; i < n; i++ {
j := i
sum := 0
for j > 0 {
sum += j % base
j /= base
}
res[i] = sum % base
}
return res
}
 
func turns(n int, fss []int) string {
m := make(map[int]int)
for _, fs := range fss {
m[fs]++
}
m2 := make(map[int]int)
for _, v := range m {
m2[v]++
}
res := []int{}
sum := 0
for k, v := range m2 {
sum += v
res = append(res, k)
}
if sum != n {
return fmt.Sprintf("only %d have a turn", sum)
}
sort.Ints(res)
res2 := make([]string, len(res))
for i := range res {
res2[i] = strconv.Itoa(res[i])
}
return strings.Join(res2, " or ")
}
 
func main() {
for _, base := range []int{2, 3, 5, 11} {
fmt.Printf("%2d : %2d\n", base, fairshare(25, base))
}
fmt.Println("\nHow many times does each get a turn in 50000 iterations?")
for _, base := range []int{191, 1377, 49999, 50000, 50001} {
t := turns(base, fairshare(50000, base))
fmt.Printf(" With %d people: %s\n", base, t)
}
}
Output:
 2 : [ 0  1  1  0  1  0  0  1  1  0  0  1  0  1  1  0  1  0  0  1  0  1  1  0  0]
 3 : [ 0  1  2  1  2  0  2  0  1  1  2  0  2  0  1  0  1  2  2  0  1  0  1  2  1]
 5 : [ 0  1  2  3  4  1  2  3  4  0  2  3  4  0  1  3  4  0  1  2  4  0  1  2  3]
11 : [ 0  1  2  3  4  5  6  7  8  9 10  1  2  3  4  5  6  7  8  9 10  0  2  3  4]

How many times does each get a turn in 50000 iterations?
  With 191 people: 261 or 262
  With 1377 people: 36 or 37
  With 49999 people: 1 or 2
  With 50000 people: 1
  With 50001 people: only 50000 have a turn

Haskell[edit]

import Data.List (intercalate, unfoldr)
import Data.Tuple (swap)
import Data.Bool (bool)
 
thueMorse :: Int -> [Int]
thueMorse base = baseDigitsSumModBase base <$> [0 ..]
 
baseDigitsSumModBase :: Int -> Int -> Int
baseDigitsSumModBase base n =
mod
(sum
(unfoldr ((bool Nothing . Just . swap . flip quotRem base) <*> (0 <)) n))
base
 
---------------------------TEST----------------------------
main :: IO ()
main =
putStrLn $
fTable
"First 25 fairshare terms for a given number of players:\n"
show
(('[' :) . (++ " ]") . intercalate "," . fmap (justifyRight 2 ' ' . show))
(take 25 . thueMorse)
[2, 3, 5, 11]
 
--------------------------DISPLAY--------------------------
fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String
fTable s xShow fxShow f xs =
unlines $
s :
fmap (((++) . justifyRight w ' ' . xShow) <*> ((" -> " ++) . fxShow . f)) xs
where
w = maximum (length . xShow <$> xs)
 
justifyRight :: Int -> a -> [a] -> [a]
justifyRight n c = (drop . length) <*> (replicate n c ++)
Output:
First 25 fairshare terms for a given number of players:

 2 -> [ 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ]
 3 -> [ 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 ]
 5 -> [ 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 ]
11 -> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 0, 2, 3, 4 ]

Java[edit]

 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class FairshareBetweenTwoAndMore {
 
public static void main(String[] args) {
for ( int base : Arrays.asList(2, 3, 5, 11) ) {
System.out.printf("Base %d = %s%n", base, thueMorseSequence(25, base));
}
}
 
private static List<Integer> thueMorseSequence(int terms, int base) {
List<Integer> sequence = new ArrayList<Integer>();
for ( int i = 0 ; i < terms ; i++ ) {
int sum = 0;
int n = i;
while ( n > 0 ) {
// Compute the digit sum
sum += n % base;
n /= base;
}
// Compute the digit sum module base.
sequence.add(sum % base);
}
return sequence;
}
 
}
 
Output:
Base 2 = [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0]
Base 3 = [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1]
Base 5 = [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3]
Base 11 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4]

JavaScript[edit]

(() => {
'use strict';
 
// thueMorse :: Int -> [Int]
const thueMorse = base =>
// Thue-Morse sequence for a given base
fmapGen(baseDigitsSumModBase(base))(
enumFrom(0)
)
 
// baseDigitsSumModBase :: Int -> Int -> Int
const baseDigitsSumModBase = base =>
// For any integer n, the sum of its digits
// in a given base, modulo that base.
n => sum(unfoldl(
x => 0 < x ? (
Just(quotRem(x)(base))
) : Nothing()
)(n)) % base
 
 
// ------------------------TEST------------------------
const main = () =>
console.log(
fTable(
'First 25 fairshare terms for a given number of players:'
)(str)(
xs => '[' + map(
compose(justifyRight(2)(' '), str)
)(xs) + ' ]'
)(
compose(take(25), thueMorse)
)([2, 3, 5, 11])
);
 
// -----------------GENERIC FUNCTIONS------------------
 
// Just :: a -> Maybe a
const Just = x => ({
type: 'Maybe',
Nothing: false,
Just: x
});
 
// Nothing :: Maybe a
const Nothing = () => ({
type: 'Maybe',
Nothing: true,
});
 
// Tuple (,) :: a -> b -> (a, b)
const Tuple = a => b => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
 
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
const compose = (...fs) =>
x => fs.reduceRight((a, f) => f(a), x);
 
// enumFrom :: Enum a => a -> [a]
function* enumFrom(x) {
// A non-finite succession of enumerable
// values, starting with the value x.
let v = x;
while (true) {
yield v;
v = 1 + v;
}
}
 
// fTable :: String -> (a -> String) -> (b -> String)
// -> (a -> b) -> [a] -> String
const fTable = s => xShow => fxShow => f => xs => {
// Heading -> x display function ->
// fx display function ->
// f -> values -> tabular string
const
ys = xs.map(xShow),
w = Math.max(...ys.map(length));
return s + '\n' + zipWith(
a => b => a.padStart(w, ' ') + ' -> ' + b
)(ys)(
xs.map(x => fxShow(f(x)))
).join('\n');
};
 
// fmapGen <$> :: (a -> b) -> Gen [a] -> Gen [b]
const fmapGen = f =>
function*(gen) {
let v = take(1)(gen);
while (0 < v.length) {
yield(f(v[0]))
v = take(1)(gen)
}
};
 
// justifyRight :: Int -> Char -> String -> String
const justifyRight = n =>
// The string s, preceded by enough padding (with
// the character c) to reach the string length n.
c => s => n > s.length ? (
s.padStart(n, c)
) : s;
 
// length :: [a] -> Int
const length = xs =>
// Returns Infinity over objects without finite
// length. This enables zip and zipWith to choose
// the shorter argument when one is non-finite,
// like cycle, repeat etc
(Array.isArray(xs) || 'string' === typeof xs) ? (
xs.length
) : Infinity;
 
// map :: (a -> b) -> [a] -> [b]
const map = f =>
// The list obtained by applying f to each element of xs.
// (The image of xs under f).
xs => (Array.isArray(xs) ? (
xs
) : xs.split('')).map(f);
 
// quotRem :: Int -> Int -> (Int, Int)
const quotRem = m => n =>
Tuple(Math.floor(m / n))(
m % n
);
 
// str :: a -> String
const str = x => x.toString();
 
// sum :: [Num] -> Num
const sum = xs =>
// The numeric sum of all values in xs.
xs.reduce((a, x) => a + x, 0);
 
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => 'GeneratorFunction' !== xs
.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
 
 
// unfoldl :: (b -> Maybe (b, a)) -> b -> [a]
const unfoldl = f => v => {
// Dual to reduce or foldl.
// Where these reduce a list to a summary value, unfoldl
// builds a list from a seed value.
// Where f returns Just(a, b), a is appended to the list,
// and the residual b is used as the argument for the next
// application of f.
// Where f returns Nothing, the completed list is returned.
let
xr = [v, v],
xs = [];
while (true) {
const mb = f(xr[0]);
if (mb.Nothing) {
return xs
} else {
xr = mb.Just;
xs = [xr[1]].concat(xs);
}
}
};
 
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
xs => ys => {
const
lng = Math.min(length(xs), length(ys)),
vs = take(lng)(ys);
return take(lng)(xs)
.map((x, i) => f(x)(vs[i]));
};
 
// MAIN ---
return main();
})();
Output:
First 25 fairshare terms for a given number of players:
 2 -> [ 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ]
 3 -> [ 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 ]
 5 -> [ 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 ]
11 -> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 0, 2, 3, 4 ]


Julia[edit]

fairshare(nplayers,len) = [sum(digits(n, base=nplayers)) % nplayers for n in 0:len-1]
 
for n in [2, 3, 5, 11]
println("Fairshare ", n > 2 ? "among" : "between", " $n people: ", fairshare(n, 25))
end
 
Output:
Fairshare between 2 people: [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0]
Fairshare among 3 people: [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1]
Fairshare among 5 people: [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3]
Fairshare among 11 people: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4]

Perl[edit]

Translation of: Perl 6
use strict;
use warnings;
use Math::AnyNum qw(sum polymod);
 
sub fairshare {
my($b, $n) = @_;
sprintf '%3d'x$n, map { sum ( polymod($_, $b, $b )) % $b } 0 .. $n-1;
}
 
for (<2 3 5 11>) {
printf "%3s:%s\n", $_, fairshare($_, 25);
}
Output:
  2:  0  1  1  0  1  0  0  1  0  1  1  0  1  0  0  1  0  1  1  0  1  0  0  1  0
  3:  0  1  2  1  2  0  2  0  1  1  2  0  2  0  1  0  1  2  2  0  1  0  1  2  1
  5:  0  1  2  3  4  1  2  3  4  0  2  3  4  0  1  3  4  0  1  2  4  0  1  2  3
 11:  0  1  2  3  4  5  6  7  8  9 10  1  2  3  4  5  6  7  8  9 10  0  2  3  4

Perl 6[edit]

Works with: Rakudo version 2020.01

Add an extension showing the relative fairness correlation of this selection algorithm. An absolutely fair algorithm would have a correlation of 1 for each person (no person has an advantage or disadvantage due to an algorithmic artefact.) This algorithm is fair, and gets better the more iterations are done.

A lower correlation factor corresponds to an advantage, higher to a disadvantage, the closer to 1 it is, the fairer the algorithm. Absolute best possible advantage correlation is 0. Absolute worst is 2.

sub fairshare (\b) { ^.hyper.map: { .polymod( b xx * ).sum % b } }
 
.say for <2 3 5 11>.map: { .fmt('%2d:') ~ .&fairshare[^25]».fmt('%2d').join: ', ' }
 
say "\nRelative fairness of this method. Scaled fairness correlation. The closer to 1.0 each person
is, the more fair the selection algorithm is. Gets better with more iterations."
;
 
for <2 3 5 11 39> -> $people {
print "\n$people people: \n";
for $people * 1, $people * 10, $people * 1000 -> $iterations {
my @fairness;
fairshare($people)[^$iterations].kv.map: { @fairness[$^v % $people] += $^k }
my $scale = @fairness.sum / @fairness;
my @range = @fairness.map( { $_ / $scale } );
printf "After round %4d: Best advantage: %-10.8g - Worst disadvantage: %-10.8g - Spread between best and worst: %-10.8g\n",
$iterations/$people, @range.min, @range.max, @range.max - @range.min;
}
}
 2: 0,  1,  1,  0,  1,  0,  0,  1,  1,  0,  0,  1,  0,  1,  1,  0,  1,  0,  0,  1,  0,  1,  1,  0,  0
 3: 0,  1,  2,  1,  2,  0,  2,  0,  1,  1,  2,  0,  2,  0,  1,  0,  1,  2,  2,  0,  1,  0,  1,  2,  1
 5: 0,  1,  2,  3,  4,  1,  2,  3,  4,  0,  2,  3,  4,  0,  1,  3,  4,  0,  1,  2,  4,  0,  1,  2,  3
11: 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,  0,  2,  3,  4

Relative fairness of this method. Scaled fairness correlation. The closer to 1.0 each person
is, the more fair the selection algorithm is. Gets better with more iterations.

2 people: 
After round    1: Best advantage: 0          - Worst disadvantage: 2          - Spread between best and worst: 2         
After round   10: Best advantage: 1          - Worst disadvantage: 1          - Spread between best and worst: 0         
After round 1000: Best advantage: 1          - Worst disadvantage: 1          - Spread between best and worst: 0         

3 people: 
After round    1: Best advantage: 0          - Worst disadvantage: 2          - Spread between best and worst: 2         
After round   10: Best advantage: 0.99310345 - Worst disadvantage: 1.0068966  - Spread between best and worst: 0.013793103
After round 1000: Best advantage: 0.99999933 - Worst disadvantage: 1.0000007  - Spread between best and worst: 1.3337779e-06

5 people: 
After round    1: Best advantage: 0          - Worst disadvantage: 2          - Spread between best and worst: 2         
After round   10: Best advantage: 1          - Worst disadvantage: 1          - Spread between best and worst: 0         
After round 1000: Best advantage: 1          - Worst disadvantage: 1          - Spread between best and worst: 0         

11 people: 
After round    1: Best advantage: 0          - Worst disadvantage: 2          - Spread between best and worst: 2         
After round   10: Best advantage: 0.99082569 - Worst disadvantage: 1.0091743  - Spread between best and worst: 0.018348624
After round 1000: Best advantage: 0.99999909 - Worst disadvantage: 1.0000009  - Spread between best and worst: 1.8183471e-06

39 people: 
After round    1: Best advantage: 0          - Worst disadvantage: 2          - Spread between best and worst: 2         
After round   10: Best advantage: 0.92544987 - Worst disadvantage: 1.0745501  - Spread between best and worst: 0.14910026
After round 1000: Best advantage: 0.99999103 - Worst disadvantage: 1.000009   - Spread between best and worst: 1.7949178e-05

Phix[edit]

Translation of: Go
function fairshare(integer n, base)
sequence res = repeat(0,n)
for i=1 to n do
integer j = i-1,
t = 0
while j>0 do
t += remainder(j,base)
j = floor(j/base)
end while
res[i] = remainder(t,base)
end for
return {base,res}
end function
 
constant tests = {2,3,5,11}
for i=1 to length(tests) do
printf(1,"%2d : %v\n", fairshare(25, tests[i]))
end for
Output:
 2 : {0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0}
 3 : {0,1,2,1,2,0,2,0,1,1,2,0,2,0,1,0,1,2,2,0,1,0,1,2,1}
 5 : {0,1,2,3,4,1,2,3,4,0,2,3,4,0,1,3,4,0,1,2,4,0,1,2,3}
11 : {0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,0,2,3,4}

Python[edit]

Procedural[edit]

from itertools import count, islice
 
def _basechange_int(num, b):
"""
Return list of ints representing positive num in base b
 
>>> b = 3
>>> print(b, [_basechange_int(num, b) for num in range(11)])
3 [[0], [1], [2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2], [1, 0, 0], [1, 0, 1]]
>>>
"""

if num == 0:
return [0]
result = []
while num != 0:
num, d = divmod(num, b)
result.append(d)
return result[::-1]
 
def fairshare(b=2):
for i in count():
yield sum(_basechange_int(i, b)) % b
 
if __name__ == '__main__':
for b in (2, 3, 5, 11):
print(f"{b:>2}: {str(list(islice(fairshare(b), 25)))[1:-1]}")
Output:
 2: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0
 3: 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1
 5: 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3
11: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4

Functional[edit]

'''Fairshare between two and more'''
 
from itertools import count, islice
from functools import reduce
 
 
# thueMorse :: Int -> [Int]
def thueMorse(base):
'''Thue-Morse sequence for a given base.'''
return map(baseDigitsSumModBase(base), count(0))
 
 
# baseDigitsSumModBase :: Int -> Int -> Int
def baseDigitsSumModBase(base):
'''For any integer n, the sum of its digits
in a given base, modulo that base.
'''

def go(n):
return sum(unfoldl(
lambda x: Nothing() if 0 == x else Just(divmod(x, base))
)(n)) % base
return lambda n: go(n)
 
 
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''First 25 fairshare terms for a given number of players'''
 
print(
fTable(
main.__doc__ + ':\n'
)(repr)(
lambda xs: '[' + ','.join(
[str(x).rjust(2, ' ') for x in xs]
) + ' ]'
)(
compose(take(25), thueMorse)
)([2, 3, 5, 11])
)
 
 
# GENERIC -------------------------------------------------
 
# Just :: a -> Maybe a
def Just(x):
'''Constructor for an inhabited Maybe (option type) value.
Wrapper containing the result of a computation.
'''

return {'type': 'Maybe', 'Nothing': False, 'Just': x}
 
 
# Nothing :: Maybe a
def Nothing():
'''Constructor for an empty Maybe (option type) value.
Empty wrapper returned where a computation is not possible.
'''

return {'type': 'Maybe', 'Nothing': True}
 
 
# compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
'''Composition, from right to left,
of a series of functions.
'''

return lambda x: reduce(
lambda a, f: f(a),
fs[::-1], x
)
 
 
# fTable :: String -> (a -> String) ->
# (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
'''Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
'''

def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
 
 
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.
'''

return lambda xs: (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
 
 
# unfoldl(lambda x: Just(((x - 1), x)) if 0 != x else Nothing())(10)
# -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# unfoldl :: (b -> Maybe (b, a)) -> b -> [a]
def unfoldl(f):
'''Dual to reduce or foldl.
Where these reduce a list to a summary value, unfoldl
builds a list from a seed value.
Where f returns Just(a, b), a is appended to the list,
and the residual b is used as the argument for the next
application of f.
When f returns Nothing, the completed list is returned.
'''

def go(v):
x, r = v, v
xs = []
while True:
mb = f(x)
if mb.get('Nothing'):
return xs
else:
x, r = mb.get('Just')
xs.insert(0, r)
return xs
return lambda x: go(x)
 
 
# MAIN ---
if __name__ == '__main__':
main()
Output:
First 25 fairshare terms for a given number of players:

 2 -> [ 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ]
 3 -> [ 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 ]
 5 -> [ 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 ]
11 -> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 0, 2, 3, 4 ]

REXX[edit]

/*REXX program calculates  N  terms of the fairshare sequence for some group of peoples.*/
parse arg n g /*obtain optional arguments from the CL*/
if n=='' | n=="," then n= 25 /*Not specified? Then use the default.*/
if g='' | g="," then g= 2 3 5 11 /* " " " " " " */
/* [↑] a list of a number of peoples. */
do p=1 for words(g); r= word(g, p) /*traipse through the bases specfiied. */
$= 'base' right(r, 2)': ' /*construct start of the 1─line output.*/
do j=0 for n; $= $ right( sumDigs( base(j, r)) // r, 2)','
end /*j*/ /* [↑] append # (base R) mod R──►$ list*/
say strip($, , ",") /*elide trailing comma from the $ list.*/
end /*p*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
base: parse arg #,b,,y; @= 0123456789abcdefghijklmnopqrstuvwxyz; @@= substr(@,2)
do while #>=b; y= substr(@, #//b + 1, 1)y; #= #%b; end; return substr(@, #+1, 1)y
/*──────────────────────────────────────────────────────────────────────────────────────*/
sumDigs: parse arg x; !=0; do i=1 for length(x); != !+pos(substr(x,i,1),@@); end; return !
output   when using the default inputs:
base  2:   0,  1,  1,  0,  1,  0,  0,  1,  1,  0,  0,  1,  0,  1,  1,  0,  1,  0,  0,  1,  0,  1,  1,  0,  0
base  3:   0,  1,  2,  1,  2,  0,  2,  0,  1,  1,  2,  0,  2,  0,  1,  0,  1,  2,  2,  0,  1,  0,  1,  2,  1
base  5:   0,  1,  2,  3,  4,  1,  2,  3,  4,  0,  2,  3,  4,  0,  1,  3,  4,  0,  1,  2,  4,  0,  1,  2,  3
base 11:   0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,  0,  2,  3,  4

Rust[edit]

Translation of: Python
struct Digits {
rest: usize,
base: usize,
}
 
impl Iterator for Digits {
type Item = usize;
 
fn next(&mut self) -> Option<usize> {
if self.rest == 0 {
return None;
}
let (digit, rest) = (self.rest % self.base, self.rest / self.base);
self.rest = rest;
Some(digit)
}
}
 
fn digits(num: usize, base: usize) -> Digits {
Digits { rest: num, base: base }
}
 
struct FairSharing {
participants: usize,
index: usize,
}
 
impl Iterator for FairSharing {
type Item = usize;
fn next(&mut self) -> Option<usize> {
let digit_sum: usize = digits(self.index, self.participants).sum();
let selected = digit_sum % self.participants;
self.index += 1;
Some(selected)
}
}
 
fn fair_sharing(participants: usize) -> FairSharing {
FairSharing { participants: participants, index: 0 }
}
 
fn main() {
for i in vec![2, 3, 5, 7] {
println!("{}: {:?}", i, fair_sharing(i).take(25).collect::<Vec<usize>>());
}
}
Output:
2: [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0]
3: [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1]
5: [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3]
7: [0, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 0, 2, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6]

Sidef[edit]

for b in (2,3,5,11) {
say ("#{'%2d' % b}: ", 25.of { .sumdigits(b) % b })
}
Output:
 2: [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0]
 3: [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1]
 5: [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3]
11: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4]

zkl[edit]

fcn fairShare(n,b){    // b<=36
n.pump(List,'wrap(n){ n.toString(b).split("").apply("toInt",b).sum(0)%b })
}
foreach b in (T(2,3,5,11)){
println("%2d: %s".fmt(b,fairShare(25,b).pump(String,"%2d ".fmt)));
}
Output:
 2:  0  1  1  0  1  0  0  1  1  0  0  1  0  1  1  0  1  0  0  1  0  1  1  0  0 
 3:  0  1  2  1  2  0  2  0  1  1  2  0  2  0  1  0  1  2  2  0  1  0  1  2  1 
 5:  0  1  2  3  4  1  2  3  4  0  2  3  4  0  1  3  4  0  1  2  4  0  1  2  3 
11:  0  1  2  3  4  5  6  7  8  9 10  1  2  3  4  5  6  7  8  9 10  0  2  3  4 

For any base > 1

fcn fairShare(n,base){
sum,r := 0,0; while(n){ n,r = n.divr(base); sum+=r }
sum%base
}
foreach b in (T(2,3,5,11)){
println("%2d: %s".fmt(b,[0..24].pump(String,fairShare.fp1(b),"%2d ".fmt)));
}