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

Sort by

recency

|

12 Discussions

|

  • urossevkusic
     + 0 comments

    Python 3 solution, using the fact that the continued fraction of e has a pattern of 2 1 1 4 1 1 6 11, ..., from index 2:

    N = int(input())

from math import e

n0, n1 = 1, 2
t = 1

for i in range(1, N):
    n0, n1 = n1, n0 + t*n1
    t = 1 if (i - 1) % 3 != 0 else ((i - 1) // 3 + 1) * 2
    
print(sum(map(int, str(n1))))

  • nkosi9976
     + 0 comments

    python solution

    from math import isqrt

num, den, two = 1, 1, 2

def sum_of_digits(n):
    s = 0
    while n:
        s, n = s + n % 10, n // 10
    return s

def reciprocal():
    global num, den
    num, den = den, num

def add_number_to_fraction(x):
    global num
    num = den * x + num

g = int(input())
if g == 1:
    print(2)
elif g == 2:
    print(3)
else:
    given = g
    three = 3
    num = (given // three) * two
    a = num - two
    if given % three == 1:
        num += 1
    elif given % three == 2:
        num = num * 2 + 1
        den = 2
    given -= given % three
    reciprocal()
    while given > 3:
        if given % three != 1:
            add_number_to_fraction(1)
        else:
            add_number_to_fraction(a)
            a -= two
        reciprocal()
        given -= 1
    add_number_to_fraction(1)
    reciprocal()
    add_number_to_fraction(2)
    print(sum_of_digits(num))

  • 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 ^__^

  • preeti_yadav_cs1
     + 0 comments

    easiest one, read out https://en.wikipedia.org/wiki/Continued_fraction Hope you will find an interseting sequence :)

  • 18ucc061
     + 0 comments

    numerator of 1000th convergent of e is 215043704928079275546350787635650473761037041054859471165269502507479923032839714356724383714831841317366238276604523416281523473735321526891502403788816357622379442531491479026711305726965718338010987910057233389226490407411089485760896902310261221862678564406652752374955049717966691207750626672828237587801856684747486631597540991685830010525355010719203587499740078562960236843126355248620564746559167769326909433896876227967966175044435184104070710491139996424638579352260315417440334385948582209795598793930287323042471339820970546936086378376760534212782350052379307682063245509120325519354493739145354196963988176021541799313848844519348782087171841449631173955150527331688172773011269564741846170156748881775468801141386665111250188282655381313977369237039915405910733421356869262135558938824245060650524874574094964353159517730092429834471126538079994918145838803922920707615406623257756931

    But my program gives different value,I don't know why? I used BigInteger and equals method to check.