Fairshare between two and more: Difference between revisions

Content added Content deleted

Inline

Revision as of 21:33, 1 February 2020

The Thue-Morse sequence is a sequnce 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

Non-decimal radices/Convert
Thue-Morse
A010060, A053838, A053840: The On-Line Encyclopedia of Integer Sequences® (OEIS®)

Go

<lang go>package main

import "fmt"

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 main() {

   for _, base := range []int{2, 3, 5, 11} {
       fmt.Printf("%2d : %2d\n", base, fairshare(25, base))
   }

}</lang>

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]

Julia

<lang julia>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

</lang>

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 6

Works with: Rakudo version 2020.01

<lang perl6>constant @prn = lazy (32 .. *).grep( {.chr ~~ /<:Lu>|<:Ll>|<:Nd>/} ).map: { .chr }; my %active = @prn[^20].pairs.invert;

sub in (Int $n, Int $r) { @prn[$n.polymod( $r xx * ).reverse].join }

sub as (Str $n, Int $r) { sum $n.flip.comb.kv.map: { %active{$^v} * $r ** $^k } }

sub fairshare (\b) { ^∞ .hyper.map: {.&in(b).comb».&as(b).sum % b } }

.say for <2 3 5 11>.map: { .fmt('%2d:') ~ .&fairshare[^25]».fmt('%2d').join: ', ' }

my $iterations = 50_000; say "\nTrivial for small number of people, less so for large numbers...\n" ~

   "How many times does each get a turn in $iterations iterations?";

for 191, 1377 -> $people {

   %active = @prn[^$people].pairs.invert;
   say "With $people people: ", fairshare($people)[^$iterations].Bag.values.sort.unique.join: ' or ';

}</lang>

 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

Trivial for small number of people, less so for large numbers...
How many times does each get a turn in 50000 iterations?
With 191 people: 261 or 262
With 1377 people: 36 or 37

Python

<lang python>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]}")</lang>

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

REXX

<lang rexx>/*REXX program calculates N terms of the fairshare sequence for some number of peoples*/ parse arg n bs /*obtain optional arguments from the CL*/ if n== | n=="," then n= 25 /*Not specified? Then use the default.*/ if bs= | bs="," then bs= 2 3 5 7 11 /* " " " " " " */

                                                /* [↑]  a list of a number of peoples. */
    do y=1  for words(bs);   bas= word(bs, y)   /*traipse through the bases specfiied. */
    $= 'base'right(bas, 3)': '                  /*construct start of the 1─line output.*/
       do j=0  for n;  #= base(j, bas)          /*convert a number  (J)  to base  BAS. */
       $= $  right( sumD(#) // bas, 2)','       /*append  "   "   (mod BAS) to the list*/
       end   /*j*/
    say strip($, , ",")                         /*elide a trailing comma (,) from list.*/
    end      /*y*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ base: procedure expose @@; parse arg #,b,,y; @@= 0123456789abcdefghijklmnopqrstuvwxyz

       do while #>=b; y= substr(@@,(#//b)+1,1)y; #=#%b; end;  return substr(@@, #+1, 1)y

/*──────────────────────────────────────────────────────────────────────────────────────*/ sumD: parse arg x; !=0; do i=1 for length(x); !=!+pos(substr(x,i,1),@@)-1; end; return !</lang>

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

Sidef

<lang ruby>for b in (2,3,5,11) {

   say ("#{'%2d' % b}: ", 25.of { .sumdigits(b) % b })

}</lang>

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

<lang zkl>fcn fairShare(n,b){

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

}</lang>

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