Prime Numbers

Mathematics that includes prime numbers are quite tough for me. They have unique kind of property that we all are aware of (i.e, the number is divisible by only two distinct numbers being one and itself).


To test a number to be prime or not, has a very basic approach:
1. Find all divisors of the number.
2. If it is 1 and number itself (excluding 1) then its a prime number.


So a nested task is how to get all the divisors. And a very basic approach is:
1. 1 is a divisor
2. for i in 2 to Number if i divides Number, i is a divisor.


A little better approach could be
1. 1 is a divisor
2. Number is a divisor
3. for i in 2 to Number/2 if i divides Number, i is a divisor.
(This approach works since a divisor(apart from number) will not be greater than half of the number)


Another good approach to me is
1. 1 is a divisor
2. Number is a divisor
3. from i = 2 to Sqrt(Number) if i divides Number, i is a divisor and (Number/i) is also a divisor.


Back to prime Numbers!! What if we need to keep generating prime numbers (mind it!... there is no such wonder in maths/computer that has generated all the primes yet!.. obviously they are infinite and everyday a new prime is discovered). Ok!...Lets have an upper bound. Its like generate all prime numbers upto 100
Oh! thats easy... any naive approach could get it.
Naive approach:
1. if number is less than 2 => NOT PRIME
2. if number is 2 => PRIME
3. if number is divisible by 2 => NOT PRIME (special case already handled)
4. for i in 3 to UPPER_BOUND (100 here), if number is divisible by i => NOT PRIME
5. loop in step 4 completed, ok! its a prime number!!


Step 4 in naive approach can be optimized when increment of i is set by 2 instead of 1 (since number is definately not even)


How can we further optimize Step 4, no need to go upto UPPER_BOUND.
We can go till UPPER_BOUND/2
And in similar way we can further optimize by iterating upto Sqrt(UPPER_BOUND)
(Similar explaination with divisor algo)


Are we ok!... Not satisfied.. true, even this approach fails when UPPER_BOUND gets into category of 'large numbers' something like 10^7


How about memoization?... doesn't help much, you cannot pre compute anything that helps to check if a number is prime or not.


There google googles down another fantastic approach, a totally different perception and so far the quickest approach to generate list of primes and it is called
*drum beats*... tada...
"Sieve of Eratosthenes"
directly pasted from wiki:


"To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
Initially, let p equal 2, the first prime number.
Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.
When the algorithm terminates, all the numbers in the list that are not marked are prime"


Boom!
This is fast...
Here is a sample private method in java to do the same

private static void generateSieve(){
System.out.println("generating sieve");
int MAX = 1000000;
boolean[] primeSieve = new boolean[MAX+2];
int MAXplus2 = MAX+2;
for (int i=0; i
primeSieve[i]=true;
for (int i=2; i<=MAXplus2/2; i++){
if (primeSieve[i]){
for (int j=(2*i); j
primeSieve[j]=false;
}
}
}
System.out.println("DONE");
}

time for prime time..
-ZeeK

Java Unique Exception Extractor Utility

During development of a java application, the greatest problem is runtime Exceptions that occur in background. These background RuntimeExceptions are generally important to fix the code. Some of them are SQLException, NullPointerException, RuntimeUserRuntimeException, ClassCastException, IndexOutOfBoundException etc. These exception are hard to be caught during construction and are generally logged in background (It may even get unnoticed, if something went wrong in a thread which is not main thread).
Java logging frameworks used in standard java application development, somehow makes the log quite verbose. Each and every step/flow fired in application gets logged (For instance, current value of x = someDynamicAppValue.
A developer is interested in only exceptions that is useful for them.

Please find link to one such utility that I created recently which helps an analyst to just collect unique stack traces from the logs and rest of the logs need not be scanned. The utility was tested with >500MB of txt java logs, and it did it job within 3 minutes.

https://sourceforge.net/projects/uniqxceptnxtrct/files/

Suggestion / Bugs / Feedback will be highly appreciated.

More on Integer Partition

I posted (searched and posted) a standard way to partition number few weeks back...  (as a part of euler project).. The one liner problem was to find number of ways to split an integer as sum of other Positive integers. (http://zeektech.blogspot.com/2010/08/project-euler-76-ways-can-one-hundred.html)

I recently got similar challenge (seems to be famous problem again).. which deals with Integer partition but restricted integers to be used.

Problem: Find Ways to Split $N into $0.01, $0.05, $0.10, $0.25
Here is the solution: (obviously it again uses DP)
import java.io.*;
public class coin_changes{
public static int[] d = {1, 5, 10, 25};
public static int[][] table;
public static void main(String[] args) throws Exception{
table = new int[10000][4];
for (int i=0; i<10000; i++)
   for (int j=0; j<4; j++)
     table[i][j]=-1;
DataInputStream dis = new DataInputStream(new FileInputStream(new File(args[0])));
String a = dis.readLine();
while (a != null){
System.out.println(recF(Integer.parseInt(a),3));
a = dis.readLine();
}
}
public static int recF(int i, int j){
       if (j < 0 || i < 0)
          return 0;
       if (i == 0) {
          return 1;
        }
      if (table[i][j]!=-1)
             return table[i][j];
      else
             table[i][j]=recF(i, j-1) + recF(i-d[j], j);
      return table[i][j];
      //return recF(i, j-1) + recF(i-d[j], j);
 }
}


The code above does the same work...with memoization... The memoization (google it for details) is a way to store previous computation. The table here stores the value of previously computed recursion, hence less function calls.

The array produced finally is similar to array produced in previous post, with a slight modification.

PS: Each line of input file (passed in argument) contains value of "N" for which ways has to be counted

Happy Coding!!

Project Euler 98:

This is getting interesintg... Project Euler is taking all my brains out now.. every question seems simple when solved. but how to start
Problem:
http://projecteuler.net/index.php?section=problems&id=98

My approach checks for all the perfect squares first and then checks to anagrams... Here is the solution... 

        int maxmaxmaxmax=0;
        String input = (new DataInputStream(new FileInputStream(new File("words.txt")))).readLine();
        StringTokenizer st = new StringTokenizer(input, ",");
        ArrayList list = new ArrayList();   
        while (st.hasMoreTokens()) {
            list.add(st.nextToken().replace("\"", ""));
        }
        long now = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            char[] word1 = list.get(i).toCharArray();
            Arrays.sort(word1);
            for (int j = 0; j < list.size(); j++) {
                if (i == j)
                    continue;
                char[] word2 = list.get(j).toCharArray();
                if (word1.length != word2.length)
                    continue;
                Arrays.sort(word2);
                boolean isAnagram = true;
                for (int k = 0; k < word1.length; k++) {
                    if (word1[k] != word2[k]) {
                        isAnagram = false;
                        break;
                    }
                }
                if (!isAnagram)    continue;

                boolean isPalindrome = true;
                for (int m = 0; m < word1.length; m++) {
                    if (list.get(i).charAt(m) != list.get(j).charAt(
                            word1.length - m - 1)) {
                        isPalindrome = false;
                        break;
                    }
                }
                if (isPalindrome) break;
                int max = (int) Math.floor((Math.pow(10, word1.length) - 1));
                int min = (int) Math.ceil(Math.pow(10,(word1.length - 1)));
                for (int number = min; number < max; number++) {
                    if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) { // perfect
                        String squareNumber = ""+number;
                        int[] square = new int[word1.length];
                        for (int m=0; m
                            square[m] = Integer.parseInt(""+squareNumber.charAt(m));
                        HashMap tempMapping = new HashMap();
                        int[] digits = new int[10];
                        int[] disWord = new int[26];
                        for (int m=0; m<10; m++){
                            digits[m]=0;
                        }
                        for (int m=0; m
                            tempMapping.put(""+list.get(i).charAt(m),square[m]);
                            digits[square[m]] = 1;
                            disWord[(int)list.get(i).charAt(m)-65] = 1;
                        }
                        int countDistinctDigit=0;
                        int countDistinctLetter=0;
                        for (int m=0; m<10; m++)
                            if (digits[m]==1)
                                countDistinctDigit++;
                        for (int m=0; m<26; m++)
                            if (disWord[m]==1)
                                countDistinctLetter++;
                       
                        if (countDistinctDigit != countDistinctLetter) continue;
                        String tempValue="";
                        for (int m=0; m
                            tempValue+=(tempMapping.get(""+list.get(j).charAt(m)));
                        }
                        if (tempValue.charAt(0)=='0')
                            continue;
                        int number2 = Integer.parseInt(tempValue);
                        if (Math.sqrt(number2) - Math.floor(Math.sqrt(number2)) == 0) { //YAPS
                            int tempMax=(number>number2)?number:number2;
                            if (tempMax>maxmaxmaxmax){
                                System.out.println(list.get(i)+"-"+number+" vs "+list.get(j)+"-"+number2+" has max = "+tempMax+"(ans) its sqrt ="+Math.sqrt(tempMax));
                            }
                            maxmaxmaxmax=(tempMax>maxmaxmaxmax)?tempMax:maxmaxmaxmax;
                        }   
                    }
                }
            }
        }
        System.out.println("Total Time Taken = "+(System.currentTimeMillis() - now)/1000 +" sec");
   

My Personal Square Root

It was really a fun to revise how to actually calculate square roots on paper!..
Following is my attempt, it works fine, but I am sure there are faster methods.

public static String squareRoot(int number, int decimal_precision){
String answer="";
String pairedNumber = ""+number;
int precision=1;

if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0)
return ""+Math.sqrt(number);

int initialGuess = (int) Math.sqrt(number);
answer+=(""+initialGuess+".");

if ((""+number).length() % 2 != 0)
pairedNumber="0"+pairedNumber;

for (int i=0; i<3*decimal_precision; i++)
pairedNumber=pairedNumber+"0";

String remainder = ""+(number - (initialGuess*initialGuess));
String factor = ""+(2*initialGuess);

while (precision <= decimal_precision){
//System.out.println("remainder="+remainder);
String dropPair = remainder+pairedNumber.substring(2*precision+2, 2*precision+4);
//System.out.println("drop : "+dropPair);
//System.out.println("factor :"+factor);
for (int i=0; i<=9; i++){
String newFactor = factor+i;
// System.out.println("new factor chk = "+newFactor);
BigInteger a = new BigInteger(newFactor).multiply(BigInteger.valueOf(i));
BigInteger b = new BigInteger(dropPair);
BigInteger c = (new BigInteger(newFactor).add(BigInteger.ONE)).multiply(BigInteger.valueOf(i+1));
//System.out.println(a+" "+b+" "+c);
if (a.compareTo(b) == -1 && b.compareTo(c) == -1)
//if (Integer.parseInt(newFactor)*i <= Integer.parseInt(dropPair) && Integer.parseInt(dropPair) < Integer.parseInt(newFactor)*(i+1))
{ //System.out.println("Found new factor : "+newFactor +" with i="+i);
answer=answer+i;
factor = ""+(new BigInteger(newFactor).add(BigInteger.valueOf(i)));
//factor = ""+(Integer.parseInt(newFactor)+i);
remainder = ""+(new BigInteger(dropPair).subtract(a));
//remainder=""+(Integer.parseInt(dropPair) - (Integer.parseInt(newFactor)*i));
break;
}
}
precision++;
// System.out.println("answer="+answer);
}


return answer;
}

Sample I/O:
System.out.println(squareRoot(2, 100));
1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727

Project Euler # 76: ways can one hundred be written as a sum

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?


int n = 100;
int[][] a = new int[n + 1][n + 1];
int i, j, k;
for (i = 0; i < a.length; i++) {
a[i][0] = 0;
a[0][i] = 1;
}
for (i = 1; i < a.length; i++) {
a[i][1] = 1;
for (j = 2; j < a[0].length; j++) {
k = i - j;
if (k < 0)
a[i][j] = a[i][j - 1];
else
a[i][j] = a[i][j - 1] + a[k][j];
}
}
i--;
int answer = a[i][i - 1];

BIG FACTORIAL!!!!!!! Java Code :)

public static void main(String[] args) throws IOException {
long start = System.currentTimeMillis();

int[] answerArray = new int[10000];
answerArray[0] = 1;

int maxAnswerDigit = 1;
int FACTORIAL_OF = 1000;
for (int n = 1; n <= FACTORIAL_OF; n++) {
for (int digit = 0; digit < maxAnswerDigit; digit++)
answerArray[digit] = answerArray[digit] * n;

for (int digit = 0; digit < maxAnswerDigit; digit++) {
if (answerArray[digit] > 9) {
answerArray[digit + 1] += answerArray[digit] / 10;
answerArray[digit] = answerArray[digit] % 10;
if (digit + 1 == maxAnswerDigit)
maxAnswerDigit++;

}
}
}
for (int i = maxAnswerDigit - 1; i >= 0; i--) {
System.out.print(answerArray[i]);
sum += answerArray[i];
}
System.out.println("\nSum=" + sum);

System.out.println("answered in "
+ (System.currentTimeMillis() - start) / 1000.0 + " sec.");

}

=================
Bloody hell 1000! =
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Sum of its digit =10539
answered in 0.062 sec