Mathematics:

The probability that at least two people share their birthday in a room of 23 people approximately 50%

This is a pretty famous combinatorial problem, mainly because it is so counter intuitive.

Classic Combinatorial Method:

If we were to use the classic combinatorial method to solve this problem, we would start by finding the probability that none of the n people share their birthday. The probability is,


Now, the probability that at least two people share their birthday is,

 

After some cancellation, the result is,



Monte Carlo Method: 

First, create several "rooms" with n number of people. Randomly generate their birthday. For simplicity purposes, generating random integer from 1-365 is a good approach. Finally count the number of "rooms" where at least two people shared their birthday. The Monte Carlo Method estimates,

    

The result is (not always),


Java:

import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Random;
import org.jscience.mathematics.number.Real;

public class BirthdayProbability {
 public static void main(String[] args) {
  // 365 days
  print(new Probability(10, 1024));
  print(new Probability(10, 2097152));
  print(new Probability(23, 1024));
  print(new Probability(23, 2097152));
  print(new Probability(300, 1024));
  print(new Probability(300, 2097152));
  // leap year
  print(new Probability(10, 1024, 366));
  print(new Probability(10, 2097152, 366));
  print(new Probability(23, 1024, 366));
  print(new Probability(23, 2097152, 366));
  print(new Probability(300, 1024, 366));
  print(new Probability(300, 2097152, 366));
 }

 public static long time() {
  return new Date().getTime();
 }

 public static Real probabilityClassic(int numOfPeople, int numOfDays) {
  Real.setExactPrecision(100);
  Real temp = Real.valueOf(1);
  for (int i = 1; i <= numOfPeople; i++)
  {
   temp = temp.times(numOfDays - numOfPeople + i);
  }
  return Real.valueOf(100).times(Real.valueOf(1).minus(temp.divide(Real.valueOf(numOfDays).pow(numOfPeople))));
 }

 public static double probabilityMonteCarlo(int numOfPeople, int numOfRooms, int numOfDays) {
  int randomnumber = 0, count = 0;
  Random random = new Random();
  ArrayList<Integer> arraylist;
  HashSet<Integer> hashset;
  for (int run = 1; run <= numOfRooms; run++)
  {
   arraylist = new ArrayList<Integer>();
   hashset = new HashSet<Integer>();
   for (int i = 0; i < numOfPeople; i++)
   {
    randomnumber = random.nextInt(numOfDays) + 1;
    // amortized constant time
    arraylist.add(randomnumber);
    // constant time
    hashset.add(randomnumber);
    if (arraylist.size() != hashset.size())
    {
     count++;
     break;
    }
   }
  }
  return ((double) count) / ((double) numOfRooms) * 100;
 }

 public static void print(Probability Probability) {
  long startMCM, startCCM;
  System.out.println(Probability.toString());
  startCCM = time();
  System.out.println("Probability based on Classic Combinatorial Method: " + probabilityClassic(Probability.getnumberOfPeople(), Probability.getnumberOfDays()) + "\nExecution Time: " + (time() - startCCM) / 1e3 + " secs.\n");
  startMCM = time();
  System.out.println("Probability based on Monte Carlo Method: " + probabilityMonteCarlo(Probability.getnumberOfPeople(), Probability.getnumberOfRooms(), Probability.getnumberOfDays()) + "\nExecution Time: " + (time() - startMCM) / 1e3 + " secs.\n");
  System.out.println("**************************\n\n");
 }
}



public class Probability {
 private int numberOfDays;
 private int numberOfPeople;
 private int numberOfRooms;

 public Probability(int numberOfPeople, int numberOfRooms) {
  this.numberOfPeople = numberOfPeople;
  this.numberOfRooms = numberOfRooms;
  this.numberOfDays = 365;
 }
 
 public Probability(int numberOfPeople, int numberOfRooms, int numberOfDays) {
  this.numberOfPeople = numberOfPeople;
  this.numberOfRooms = numberOfRooms;
  this.numberOfDays = numberOfDays;
 }

 public int getnumberOfPeople() {
  return numberOfPeople;
 }

 public int getnumberOfRooms() {
  return numberOfRooms;
 }

 public int getnumberOfDays() {
  return numberOfDays;
 }
 
 public String toString(){
  return "Number of People: "+numberOfPeople+"\nNumber of Days: "+numberOfDays+"\nNumber of Rooms: "+numberOfRooms+"\n";
 }
 
}



Number of People: 10
Number of Days: 365
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 11.6948177711077651869164770415495838768342667298982714059990945201552009201848139128614995295730927
Execution Time: 0.063 secs.

Probability based on Monte Carlo Method: 11.9140625
Execution Time: 0.025 secs.

**************************


Number of People: 10
Number of Days: 365
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 11.6948177711077651869164770415495838768342667298982714059990945201552009201848139128614995295730927
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 11.704587936401367
Execution Time: 1.445 secs.

**************************


Number of People: 23
Number of Days: 365
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 50.72972343239854072254172283370325002359718452929878099019740020018841839181277159923316805370532012
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 51.3671875
Execution Time: 0.004 secs.

**************************


Number of People: 23
Number of Days: 365
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 50.72972343239854072254172283370325002359718452929878099019740020018841839181277159923316805370532012
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 50.70667266845703
Execution Time: 3.014 secs.

**************************


Number of People: 300
Number of Days: 365
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 99.9999999999999999999999999999999999999999999999999999999999999999999999999999999375466755293758512381129978461284734548583347684249819000883774880640819313421049375212650378828337
Execution Time: 0.02 secs.

Probability based on Monte Carlo Method: 100.0
Execution Time: 0.002 secs.

**************************


Number of People: 300
Number of Days: 365
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 99.9999999999999999999999999999999999999999999999999999999999999999999999999999999375466755293758512381129978461284734548583347684249819000883774880640819313421049375212650378828337
Execution Time: 0.008 secs.

Probability based on Monte Carlo Method: 100.0
Execution Time: 4.246 secs.

**************************


Number of People: 10
Number of Days: 366
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 11.6645411803999900086835739583084814093115540505256706115485640589964528406979927411348744338253793
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 12.890625
Execution Time: 0.001 secs.

**************************


Number of People: 10
Number of Days: 366
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 11.6645411803999900086835739583084814093115540505256706115485640589964528406979927411348744338253793
Execution Time: 0.0 secs.

Probability based on Monte Carlo Method: 11.67612075805664
Execution Time: 1.296 secs.

**************************


Number of People: 23
Number of Days: 366
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 50.63230118194599075847570192608255953114267617437643013841590630887057713930353071663127356519578656
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 52.34375
Execution Time: 0.001 secs.

**************************


Number of People: 23
Number of Days: 366
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 50.63230118194599075847570192608255953114267617437643013841590630887057713930353071663127356519578656
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 50.653934478759766
Execution Time: 3.121 secs.

**************************


Number of People: 300
Number of Days: 366
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 99.999999999999999999999999999999999999999999999999999999999999999999999999999999847585449413476628793612104938729586908196369901220689544986844445385366856828346677128124471484063
Execution Time: 0.008 secs.

Probability based on Monte Carlo Method: 100.0
Execution Time: 0.003 secs.

**************************


Number of People: 300
Number of Days: 366
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 99.999999999999999999999999999999999999999999999999999999999999999999999999999999847585449413476628793612104938729586908196369901220689544986844445385366856828346677128124471484063
Execution Time: 0.006 secs.

Probability based on Monte Carlo Method: 100.0
Execution Time: 4.314 secs.

**************************

Couple of observations:

It gets really interesting when n is a large number (less than 366). For example, when n is 300 like in the last part of the result, the probability is very large. It is so large that if we really put 300 random people in a room, we will "always" find at least a couple who share birthdays. Therefore, Monte Carlo is not really useful in these extreme situations. Also, the library jscience is brilliant when it comes to precision. Before coming across this library, I had to settle with a different approach since Java could not handle calculations like . For example, the Birthday probability for n = 300 would be represented by,



Not real exciting.

However now, the probability that java returns is,
99.9999999999999999999999999999999999999999999999999999999999999999
9999999999999984758544941347662879361210493872958690819636990122068
9544986844445385366856828346677128124471484063

CRAZY.
When designing an interface for an app or a website, the hex values for colors are needed. I just wanted a tool that allowed me to play around with hex values and see the result color. The main purpose for coding this was to experiment with WebView in Android. It also felt like a fun little 2-3 hours why-not-just-do-it project.
The three Slide bars correspond to Red, Green and Blue values respectively. First of all, a html script with background color information based on SlideBar inputs is generated. The Web View then uses the generated html script to build a html web-page.
Users can also use the EditText and Submit button to input hex values. Initially, I had not planned on putting this functionality. I later decided to add it because several people were giving bad ratings to similar app in the appstore for missing it. Also, it was a fairly simple addition.






Option 1: Slide the SeekBars to get required values. 

For example, when Red SeekBar is changed:


public void onProgressChanged(SeekBar arg0, int arg1, boolean arg2) {

 String red = Integer.toHexString(arg1);
 if (red.length() == 1) {
  red = "0" + red;
 }

 String green = Integer.toHexString(greenSeekBar.getProgress());
 if (green.length() == 1) {
  green = "0" + green;
 }

 String blue = Integer.toHexString(blueSeekBar.getProgress());
 if (blue.length() == 1) {
  blue = "0" + blue;
 }

 color = "<!DOCTYPE html><html><body bgcolor=" + red + green + blue + "></body></html>";

 htmlDisplay.loadData(color, "text/html", null);
 result.setText("#" + red + green + blue); 
}

Option 2: Use the EditText to enter the value. 

This option will change the SeekBars position to input values. Once that happens, request has been deduced to act similarly as Option 1.


String Input = input.getText().toString() + "";
if ((Input.length() == 6) && (Input.matches("[0-9A-Fa-f]+"))) {
 redSeekBar.setProgress(Integer.parseInt(Input.substring(0, 2), 16));
 greenSeekBar.setProgress(Integer.parseInt(Input.substring(2, 4), 16));
 blueSeekBar.setProgress(Integer.parseInt(Input.substring(4, 6), 16));
} else {
 input.setText("ERROR!");
}


After reading Uncle Petros and Goldbach's Conjecture, I wanted to write a program that would break an even number into two primes. However, I also decided to add functionalities like prime tests and my favourite functionality of all time - Real Random Generator (here: Real Random Prime Generator).

Part one: Primality Test



Depending on the size of the input string, two algorithms were implemented:


try {
 long inputhere = Long.parseLong(input);
 if (isPrime(inputhere)) {

 } else {

 }
}

catch (NumberFormatException ee) {
 if (probablePrime(input)) {

 } else {

 }
}

If the input string can be parsed into a long type, the following method was used:


boolean isPrime(long n) {
 if (n < 2)
  return false;
 if (n == 2 || n == 3)
  return true;
 if (n % 2 == 0 || n % 3 == 0)
  return false;
 long sqrtN = (long) Math.sqrt(n) + 1;
 for (long i = 6L; i <= sqrtN; i += 6) {
  if (n % (i - 1) == 0 || n % (i + 1) == 0)
   return false;
 }
 return true;
}

If not, the input was cast into a BigInteger type and the following method was used:


boolean probablePrime(String input) {
 return new BigInteger(input).isProbablePrime(10);
}

This way. the app can take care of any input size.

Part two: Goldbach's prime pair

 



  According to the famous Goldbach's Conjecture, Every even integer greater than 2 can be expressed as the sum of two primes. This part of the app allows the users to break an even number into two primes. If the input is less than or equal to 50000, it will also list all distinct sum of two prime that make up the number. Using Sieve of Eratosthenes and looping through n/2 number of primes before the input, if prime+x=input, where x is another prime was satisfied, a pair (prime, x) would satisfy Goldbach's conjecture.

Part three: Random Prime Generator


This part of the app allows users to generate random primes. Prime number less than a million was stored in a String array. Then the index of the array was randomly generated. If the user's device has an active internet connection, the user can choose to generate a real random prime number. The index for the real random prime number was imported from Random.org's integer generator.


public int realRandom() throws Exception {
 String sendto = "http://www.random.org/integers/?num=1&min=0&max=78497&col=1&base=10&format=plain&rnd=new";
 URL url = new URL(sendto);
 BufferedReader in = new BufferedReader(new InputStreamReader(url.openStream()));
 return (Integer.parseInt(in.readLine()));
}


After missing couple of English Premier League Games due to the time difference between what I was used to and Nepal, I thought it would be wise to create an app that kept track of all Premier League fixtures in Nepal time.  

Step 1: Extracting, Parsing and Storing

Since I wanted the fixtures to be available offline, I had to find a way to extract and store the data. After trying several implementations, I decided to use a csv file that I found online. I used CSVReader to parse through the csv file and added required html tags to change everything into web pages.The plan was to use WebView in android to display the fixtures.

For example, the follwing java code prints a full webpage for the month of October.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Calendar;

import au.com.bytecode.opencsv.CSVReader;

public class exceltohtml {
 public static void main(String[] args) throws FileNotFoundException {
  CSVReader reader = new CSVReader(new FileReader("file.csv"), '\t');
  String month = "Dec";
  String[] nextLine;
  String a = "";
  boolean test = true;

  String html = "<!DOCTYPE html><html>";
  try {
   while ((nextLine = reader.readNext()) != null) {
    if (nextLine[0].contains(month)) {
     if (!a.equals(nextLine[0])) {
      html = html + "<p></p></table><h2><b>" + nextLine[0] + "</b></h2><table cellpadding=\\\"5\\\" cellspacing=\\\"3\\\"><tbody><tr> <td><b>Fixtures</b></td><td><b>Kick-off</b></td></tr>";
     }
     
     html = html + "<tr><td>" + nextLine[2] + " vs " + nextLine[3] + "</td><td>" + nextLine[4] + "</td></tr>";
     a = nextLine[0];
    }

   }
   System.out.print(html + "</tbody></table></html>");
   
   

  } catch (IOException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }

 }
} 

Step 2: Rest of the app






Feature#1:

Allows users to select their default team. The default team name was stored in a SharedPreference variable. With a simple if/else implementation, the user gets a custom wallpaper. Also, their team name in fixtures page is typefaced bold and underlines.  

To store:
1
PreferenceManager.getDefaultSharedPreferences(getApplicationContext()).edit().putString("default_team", selected).commit();

To retrieve:
1
String team = PreferenceManager.getDefaultSharedPreferences(getApplicationContext()).getString("default_team", "--");

Feature#2:

Generates current month fixtures by default.
1
2
Calendar cal = Calendar.getInstance();
int thismonth = cal.get(Calendar.MONTH);