import orbital.math.*; import orbital.math.Integer; import orbital.math.functional.Operations; /** * Application of Chinese Remainder Theorem * for simultaneously solving independent congruences. *
* Drei Karlsruher Studenten haben eine Kneipe entdeckt, die sie * regelmäßig besuchen. Der erste besuchte sie an einem * Montag zum ersten mal, der zweite am darauffolgenden Tag und der * Dritte am darauffolgenden Donnerstag. Da sich alle drei in * gemeinnützigen Organisationen einbringen, können sie * leider nicht täglich die Kneipe besuchen. So kann der erste * nur jeden dritten, der Zweite nur jeden vierten und der Dritte nur * jeden fünften Tag. Trotzdem trafen sie sich am 2. Advent * dieses Jahres zum ersten mal in dieser Kneipe und vereinbarten, * dass sie immer dann Skat spielen, wenn sie sich sonntags * treffen. Wann besuchte der erste Student zum ersten mal die Kneipe * und wann können sie das erste mal Skat spielen? * (from the 8. assignements in algebra I at the University of Karlsruhe on 2001-12-7 * by F. Herrlich and H. Utz) **
* We identify the days of the week per *
Day of week | *Monday | *Tuesday | *Wednesday | *Thursday | *Friday | *Saturday | *Sunday | *
---|---|---|---|---|---|---|---|
Wochentag | *Montag | *Dienstag | *Mittwoch | *Donnerstag | *Freitag | *Samstag | *Sonntag | *
Number | *0 | *1 | *2 | *3 | *4 | *5 | *6 | *
Student | *First arrival | *Period of visits | *Congruence | *
---|---|---|---|
A | *0=Monday | *3 | *x≡0 (mod 3) | *
B | *1=Tuesday | *4 | *x≡1 (mod 4) | *
C | *3=Thursday | *5 | *x≡3 (mod 5) | *
Play "Skat" | *6=Sunday | *7 | *x≡6 (mod 7) | *
* These congruences are independent, since * gcd(3,4)=1, gcd(3,5)=1, gcd(3,7)=1, gcd(4,5)=1, gcd(4,7)=1, and gcd(5,7)=1. * And then we solve the congruences with respect to x. * If we ignore the last congruence we solve the first question of when they first met. * If, however, we take into account the last congruence we solve the second question * of when they will first play "Skat". *
* @author André Platzer * @version $Id: CRTApplication.java 1728 2006-08-30 18:06:46Z andre $ */ public class CRTApplication{ public static void main(String[] args){ // get us a value factory for creating arithmetic objects final Values vf = Values.getDefaultInstance(); Integer x[] = {vf.valueOf(0), vf.valueOf(1), vf.valueOf(3)}; Integer m[] = {vf.valueOf(3), vf.valueOf(4), vf.valueOf(5)}; Integer umod = (Integer) Operations.product.apply(vf.valueOf(m)); System.out.println("computing \"Anzahl Tage vor dem 2.Advent fuer erstes Treffen\""); System.out.println("computing \"number of days before 2.Advent for the first meeting\""); System.out.println("congruent values: " + MathUtilities.format(x)); System.out.println("modulo values: " + MathUtilities.format(m)); System.out.println("solution: " + AlgebraicAlgorithms.chineseRemainder(x,m)); // print nonnegative normalized representation of the solution // (since the number of days is not negative) System.out.println(" (== " + (((Integer)AlgebraicAlgorithms.chineseRemainder(x,m).representative()).intValue() + umod.intValue()) % umod.intValue() + ")"); System.out.println("is unique modulo: " + umod); System.out.println(); x = new Integer[] {vf.valueOf(0), vf.valueOf(1), vf.valueOf(3), vf.valueOf(6)}; m = new Integer[] {vf.valueOf(3), vf.valueOf(4), vf.valueOf(5), vf.valueOf(7)}; System.out.println("computing \"Anzahl Tage bis zum ersten Skatspiel\""); System.out.println("computing \"number of day to first game of \"Skat\"\""); System.out.println("congruent values: " + MathUtilities.format(x)); System.out.println("modulo values: " + MathUtilities.format(m)); System.out.println("solution: " + AlgebraicAlgorithms.chineseRemainder(x,m)); System.out.println("is unique modulo: " + Operations.product.apply(vf.valueOf(m))); } } // CRTApplication