We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #65: Convergents of e
  4. Discussions

Project Euler #65: Convergents of e

  • arora05saksham
     + 1 comment

    Java BigInteger

    Observed patterns how the fraction changes from the required convergent to back to 3rd convergent.

    I handle the 1st and 2nd convergents explicitly. I represent the fraction using two variables num and den which stand for numerator and denominator.

    First, I find out which multiple of 2 in the series is the closest to the required convergent. for example, if the required convergent is 10, then I make the fraction ready for calculation from '6' in the series. The variable a denotes the next multiple of 2 coming up in the series. for example, the fraction i prepared for convergent 10 was built using '6', but the next multiple of 2 in the series will be 4, so I assign a as '4'. I also made two functions, one: to "add an upcoming number" (whether 'a' or 1) to the fraction and two: to find the "reciprocal" of the fraction and then dividing the reciprocal by 1. (swapping num and den) The rest is pretty much self explanatory

    This was my code when I thought long would be enough:

    long num, den=1;
private void driver(){
    int given = new Scanner(System.in).nextInt();
    if(given==1){
        System.out.println(2);
        return;
    }
    else if(given==2){
        System.out.println(3);
        return;
    }
    num = (given/3)*2;
    long a = num-2;
    if(given%3==1){
        num++;
    }else if(given%3==2){
        num = 2*num + 1;
        den = 2;
    }
    given -= given%3;
    reciprocal();
    while(given>3){
        if(given%3!=1)
            addNumberToFraction(1);
        else {
            addNumberToFraction(a);
            a -= 2;
        }
        reciprocal();
        given--;
    }
    addNumberToFraction(1);
    reciprocal();
    addNumberToFraction(2);
    System.out.println(sumOfDigits(num));
}

private long sumOfDigits(long num) {
    long sum = 0;
    while(num>0){
        sum += num%10;
        num /= 10;
    }
    return sum;
}

private void reciprocal(){
    long t = num;
    num = den;
    den = t;
}

private void addNumberToFraction(long x){
    num = den*x + num;
}

  public static void main(String[] args) {
        new Question65().driver();
    }

    But obviously that did not work out as the numbers go way crazy! Then i converted the above same logic into BigInteger. Here it is:

    static BigInteger num, den = BigInteger.ONE, two = BigInteger.valueOf(2);

public static void main(String[] args) {
    int g = new Scanner(System.in).nextInt();
    if(g==1){
        System.out.println(2);
        return;
    }
    else if(g==2){
        System.out.println(3);
        return;
    }
    BigInteger given = new BigInteger(g+"");
    BigInteger three = BigInteger.valueOf(3);
    num = (given.divide(three)).multiply(two);
    BigInteger a = num.subtract(two);
    if (given.mod(three).equals(BigInteger.ONE)) {
        num = num.add(BigInteger.ONE);
    } else if (given.mod(three).equals(two)) {
        num = num.multiply(two).add(BigInteger.ONE);
        den = two;
    }
    given = given.subtract(given.mod(three));
    reciprocal();
    while (given.compareTo(three) > 0) {
        if (!given.mod(three).equals(BigInteger.ONE))
            addNumberToFraction(BigInteger.ONE);
        else {
            addNumberToFraction(a);
            a = a.subtract(two);
        }
        reciprocal();
        given = given.subtract(BigInteger.ONE);
    }
    addNumberToFraction(BigInteger.ONE);
    reciprocal();
    addNumberToFraction(two);
    System.out.println(sumOfDigits(num));
}

private static BigInteger sumOfDigits(BigInteger num) {
    BigInteger sum = BigInteger.ZERO;
    while (num.compareTo(BigInteger.ZERO) > 0) {
        sum = sum.add(num.mod(BigInteger.TEN));
        num = num.divide(BigInteger.TEN);
    }
    return sum;
}

private static void reciprocal() {
    BigInteger t = num;
    num = den;
    den = t;
}

private static void addNumberToFraction(BigInteger x) {
    num = den.multiply(x).add(num);
}

    Drop any queries in the comments, thanks ^__^