Project Euler

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Answer: 233168

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … Find the sum of all the even-valued terms in the sequence which do not exceed four million.
Answer: 4613732

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
Answer: 6857

Problem 80

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all. The square root of two is 1.41421356237309504880…, and the digital sum of the first one hundred decimal digits is 475. For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.
Answer: 40886

package problem80;
 
import java.math.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        MathContext mc = new MathContext(200);
        long res = 0;
        for(int n = 1; n <= 100; ++n){
            BigDecimal a = new BigDecimal(n);
            BigDecimal b = bigSqrt(a, mc);
            String s = b.toEngineeringString();
            String t = s.substring(s.indexOf(".") + 1);
            if(t.startsWith("0000000000000")) continue;
            String digits = "";
            digits += s.substring(0, s.indexOf("."));
            digits += t.substring(0, 100 - digits.length());
            long tmp = 0;
            for(int i = 0; i < digits.length(); ++i){
                String td = "";
                td += digits.charAt(i);
                tmp += Long.parseLong(td);
            }
            res += tmp;
        }
        System.out.println(res);
    }
 
    public static BigDecimal bigSqrt(BigDecimal squarD, MathContext rootMC) {
        BigDecimal TWO = new BigDecimal(2);
        double SQRT_10 = 3.162277660168379332;
 
        int sign = squarD.signum();
        if(sign == -1) throw new ArithmeticException("\nSquare root of a negative number: " + squarD);
        else if(sign == 0)
          return squarD.round(rootMC);
 
        int prec = rootMC.getPrecision();
        if(prec == 0) throw new IllegalArgumentException("\nMost roots won't have infinite precision = 0");
 
        int BITS = 62;                           
        int nInit = 16;                            
        MathContext nMC = new MathContext(18, RoundingMode.HALF_DOWN);
 
        BigDecimal x = null, e = null;              
        BigDecimal v = null, g = null;             
 
        BigInteger bi = squarD.unscaledValue();
        int biLen = bi.bitLength();
        int shift = Math.max(0, biLen - BITS + (biLen%2 == 0 ? 0 : 1));
        bi = bi.shiftRight(shift);
 
        double root = Math.sqrt(bi.doubleValue());
        BigDecimal halfBack = new BigDecimal(BigInteger.ONE.shiftLeft(shift/2));
 
        int scale = squarD.scale();
        if(scale % 2 == 1) root *= SQRT_10;
        scale = (int)Math.floor(scale/2.);
 
        x = new BigDecimal(root, nMC);
        x = x.multiply(halfBack, nMC);
 
        if(scale != 0) x = x.movePointLeft(scale);
 
        if(prec < nInit) return x.round(rootMC);        
 
        v = BigDecimal.ONE.divide(TWO.multiply(x), nMC);
 
        ArrayList nPrecs = new ArrayList();
 
        assert nInit > 3 : "Never ending loop!";
 
        for(int m = prec + 1; m > nInit; m = m/2 + (m > 100 ? 1 : 2)) nPrecs.add(m);
 
        for(int i = nPrecs.size()-1; i > -1; i--) {
            nMC = new MathContext(Integer.parseInt(nPrecs.get(i).toString()), (i%2 == 1) ? RoundingMode.HALF_UP : 
                                                        RoundingMode.HALF_DOWN);
            e = squarD.subtract(x.multiply(x, nMC), nMC);
            if(i != 0) x = x.add(e.multiply(v, nMC));
            else 
            {
                x = x.add(e.multiply(v, rootMC), rootMC);               
                break;
            }
            g = BigDecimal.ONE.subtract(TWO.multiply(x).multiply(v, nMC));
            v = v.add(g.multiply(v, nMC));
        }
 
        return x; 
   }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License