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 #64: Odd period square roots
  4. Discussions

Project Euler #64: Odd period square roots

Sort by

recency

|

13 Discussions

|

  • sathish126
     + 0 comments

    python3 code 100points/-

    import math

def perf_arc(n):
    root = int(math.sqrt(n))
    if root * root == n:
        return 0
    
    a = 1
    listaint = [root]
    den = n - root * root
    lista_inv_frac = [(math.sqrt(n) + root) / den]
    per = 0
    
    while True:
        part_int = int(lista_inv_frac[-1])
        root = (den * part_int) // a - root
        a = den // a
        den = n - root * root
        invfrac = a * (math.sqrt(n) + root) / den
        listaint.append(part_int)
        lista_inv_frac.append(invfrac)
        per += 1
        
        if invfrac == lista_inv_frac[0]:
            return per

def main():
    n = int(input())
    cnt_odd = 0
    
    for k in range(2, n + 1):
        if perf_arc(k) % 2 == 1:
            cnt_odd += 1
    
    print(cnt_odd)

if __name__ == "__main__":
    main()

  • umairg404
     + 0 comments

    Here 100/- Points Solution in C#

    using System;
using System.Collections.Generic;

namespace PerfectSquareFractions
{
    class Program
    {
        static int PerfArc(int n)
        {
            int root = (int)Math.Sqrt(n);
            if (root * root == n)
            {
                return 0;
            }
            int a = 1;
            List<int> listaint = new List<int> { root };
            int den = n - root * root;
            List<double> lista_inv_frac = new List<double> { (Math.Sqrt(n) + root) / den };
            int per = 0;
            while (true)
            {
                int part_int = (int)lista_inv_frac[lista_inv_frac.Count - 1];
                root = (den * part_int) / a - root;
                a = den / a;
                den = n - root * root;
                double invfrac = a * (Math.Sqrt(n) + root) / den;
                listaint.Add(part_int);
                lista_inv_frac.Add(invfrac);
                per++;
                if (invfrac == lista_inv_frac[0])
                {
                    return per;
                }
            }
        }

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int cntodd = 0;
            for (int k = 2; k <= n; k++)
            {
                if (PerfArc(k) % 2 == 1)
                {
                    cntodd++;
                }
            }

            Console.WriteLine(cntodd);
        }
    }
}

  • rafael_rjsm
     + 0 comments

    In my opinion this is Project Euler's most beautiful problem.

    Odd period square roots

    https://github.com/rafaeldjsm/Matematica/blob/main/ProjectEuler_64__square_roots.ipynb

  • arora05saksham
     + 0 comments

    Java hashmap

    phew, so glad it did not throw TLE; thought it might though, for N = 30000.

    This link was quite helpful in understanding how the conversions are to be done. https://math.stackexchange.com/questions/265690/continued-fraction-of-a-square-root

    Okay, so we already know the answer before N=14, so start with odd period count = 4. For every number, find it's nearest square root. That's the number you'll subtract (and add) in the first conversion (as shown in the problem statement). Also, if the number is a perfect square, we'll skip that.

    Now, we pass the number, and it's nearest square root to the function: convert. I'll first explain what are the variables; a is the natural number in the series expansion (i.e., in the example of sqrt(23), 'a' would be 4, 1, 3, 1, 8). And how do we calculate that? for instance, let's take the 2nd expansion of sqrt(23).

    1 + 1/(7/(sqrt(23)-3))

    If you calculate (int) 7/(sqrt(23)-3), it'll be 3, which is 'a' for the next expansion.

    right is the number which you see as the right number in the numerator in every expansion. This can be calculated by first calculating 'a', multiplying 'a' with 'den' and subtracting the previous right value. and num and den are the numerator and denominator respectively.

    Now as we can see 1 comes two times, so we cannot just call off the series when a number comes again. we need a more concrete way, to figure out when the series repeat. So we'll try to form a unique signature for every expansion in the series. this can be done by storing all => a, right and den as a string along with the index at which they occured, so that we can calculate the period with that. This is done using a HashMap unique At any iteration, if the unique signature repeats, that means our search is ended. We find the period, and check if that's odd or not, and then continue for the next number.

    Also, after every iteration the rationalised fraction needs to be in its simplest form, i.e., 7/14 -> 1/2. for, that, i take the Greatest Common Divisor and divide the denominator with it. Source for the gcd function: https://www.baeldung.com/java-greatest-common-divisor

    import java.util.*;

public class Solution {
    Map<String, Integer> unique;
    int odds = 4;
    private void driver(int num){
        for(int i=14; i<num; i++){
            unique = new HashMap<>();
            double sq = Math.sqrt(i);
            if(sq == (int) sq) continue;
            convert(i, (int) sq);
        }
        System.out.println(odds);
    }

    private void convert(int n, int right){
        int den = 1, a = right, index = 0, num = 1;
        String uniq = a + " " + right + " " + den;
        unique.put(uniq, index++);
        while(true) {
            den = n - right*right;
            int gcd = gcd(num, den);
            den /= gcd;
            a = (int) (num / (Math.sqrt(n) - right));
            right = den * a - right;
            uniq = a + " " + right + " " + den;
            if(unique.containsKey(uniq)){
                if((index - unique.get(uniq)) % 2 == 1) odds++;
                return;
            }
            else unique.put(uniq, index++);
            num = den;
        }
    }

    private int gcd(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        int n;
        for (n = 0; ((a | b) & 1) == 0; n++) {
            a >>= 1;
            b >>= 1;
        }
        while ((a & 1) == 0)
            a >>= 1;
        do {
            while ((b & 1) == 0)
                b >>= 1;
            if (a > b) {
                int temp = a;
                a = b;
                b = temp;
            }
            b = (b - a);
        } while (b != 0);
        return a << n;
    }
    
    public static void main(String[] args) {
        new Solution().driver(new Scanner(System.in).nextInt());
    }
}

  • priyanshu_706811
     + 0 comments

    Two test caser are running other showing time problem can anyone fix it

    import math
def getPeriod(x):
    root=int(math.sqrt(x))
    if(root*root==x):
        return 0
    a=root
    num=0
    den=1
    per=0
    while(a!=2*root):
        num=den*a-num
        den=(x-num**2)/den
        a=(root+num)/den
        per+=1
    return per
last=int(input())
numOdd=0
for i in range(2,last):
    per=getPeriod(i)
    if(per%2==1):
        numOdd+=1
print(math.ceil(numOdd)+1)