CareerCup

import java.util.ArrayList;
import java.util.Scanner;

public class Question2 {
static int count;

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

System.out.println("Enter No to check");

int num = Integer.parseInt(s.next());

ArrayList<Double> al = new ArrayList();

for (int x = 1; x <= num; x++) {

for (int y = 1; y <= num; y++) {

if (y > x) {
double result = (double) x / y;

if (al.contains(result)) {

} else {
al.add(result);
System.out.println(x + "/" + y);

count++;
}

}
}

}
System.out.println(count);
}
}

def count(n) :
    counter = 0
    k = 2
    while(k <= n) :
        counter += euler_brute(k)
        k += 1
    return counter

def gcd(p,q) :
    if q == 0 :
        return p
    else :
        return gcd(q, p%q)

def euler_brute(l) :
    phi = 0
    for j in range(1, l+1) :
        if gcd(j,l) == 1 :
           phi += 1
    return phi
#test
print(count(5))

import java.util.ArrayList;
import java.util.Scanner;
public class Question2 {
static int count;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Enter No to check");
int num = Integer.parseInt(s.next());
ArrayList<Double> al = new ArrayList();
for (int x = 1; x <= num; x++) {
for (int y = 1; y <= num; y++) {
if (y > x) {
double result = (double) x / y;
if (al.contains(result)) {
} else {
al.add(result);
System.out.println(x + "/" + y);
count++;
}
}
}

}
System.out.println(count);
}
}

import java.util.ArrayList;
import java.util.Scanner;

public class Question2 {
static int count;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Enter No to check");
int num = Integer.parseInt(s.next());
ArrayList<Double> al = new ArrayList();
for (int x = 1; x <= num; x++) {
for (int y = 1; y <= num; y++) {
if (y > x) {
double result = (double) x / y;
if (al.contains(result)) {
} else {
al.add(result);
System.out.println(x + "/" + y);
count++;
}
}
}}
System.out.println(count);
}}

import java.util.ArrayList;import java.util.Scanner;public class Question2{static int count;public static void main(String[] args){Scanner s = new Scanner(System.in);System.out.println("Enter No to check");int num = Integer.parseInt(s.next());ArrayList<Double> al = new ArrayList();for (int x = 1; x <= num; x++) {for (int y = 1; y <= num; y++) {if (y > x) {double result = (double) x / y;if (al.contains(result)) {} else { al.add(result);System.out.println(x + "/" + y);count++;}}}}System.out.println(count);}}

1.So basically the solution could be the recursive function, which takes N as argument, and then makes this N a divisior of a fraction. And then inside, there would be a while loop. And every repetition of the while loop would represent one fraction from 1/N to N-1/N {if N = 4 then 1/4;2/4;3/4}. During every repetition of while loop we check if the fraction is reducable. If its not reducable we increase the counter by one. Counter will track every valid fraction that we need to count. After while loop we return another call to our function with N reduced by one. The base case of recursion would occur when N == 1. In that case we return the counter. So for example if N = 4, then every repetition of while loop represent 1/4, 2/4, 3/4.

EDIT:<s> (But in cases when N is an odd number we don't need to run while loop because every fraction in that case would not be reducable, so in this case we would just increment our counter by current N -1. For example if N = 5 then 1/5, 2/5, 3/5, and 4/5 are all not reducable so we don't need to check that and just increment counter by N-1.)</s>.Unfortunately i was wrong in this one. The fraction is irreducible only if divisor is a prime number not odd number:(

2. To check if fraction is reducable we would need to check if Greatest Common Divisor of Dividend and Divisor of our fraction is bigger than 1. If it's bigger than a fraction is reducable and we do not count it.

3. In my code Greatest Common Divisior function is named NWD(int a, int b), divident of a fraction = l, and divisor = m.

public static int countFractions(int n, int counter)
    {
	if(n < 1)return -1; //error
        if(n == 1)return counter;
        int l = 1;//dividend
        int m = n;//divisor
            while(l < m)
            {
                if(!isReducable(l++, m))counter++;
            }
        return countFractions(n - 1, counter);
    }

	private static boolean isReducable(int l, int m)
    {
        return (NWD(m,l) > 1);
    }
	//NWD function is Just Greatest Common Divisor
	private static int NWD(int a, int b)
    {
        if(b == 0)
        {
            return a;
        }else
        {
            return NWD(b, a % b);
        }
    }

A fraction p/q is irreducible and smaller equal 1 if gcd(p,q)=1 and p < q.
Hence the number of irreducible functions of the form i/j where i < j equals phi(j)
where phi is the Euler's totient function, that is summing phi(j) over j= 2,..,n
(n being the input number) we get the desired result.
So:
1. First get prime numbers smaller or equal than input number n via Eratostene's sieve and store them in an array O(nlog(log(n))).

2. For every i=2,...,n compute Euler's totient function phi(i) via the product formula using the array of primes obtained in the previous step to find the prime factors of i.

3. Finally sum all phi(i).

from random import  randint
import time

def count_irr(n) :
    primes = eratostene(n)
    nr = 0
    for i in range (2, n+1) :
        k = 2
        phi_i = i
        check = i
        #distinc_primes = []
        while k <= i :
           if primes[k-2] and i%k == 0 :
                phi_i = phi_i*(1-1/k)
                check = int(i/k)
        #        distinc_primes.append(k)
           elif primes[k-2] and k > check:
               break
           k += 1
        nr += phi_i
    return int(nr)



def eratostene(n):
    num = [True]*(n-1)
    i = 2
    while(i*i <= n):
        if num[i-2] == True :
            j = i*i-2
            while( j < n-1 ):
                num[j] = False
                j = j + i
        i += 1
    return num

#test with 12 random integers between 1 and 1000
a = []
for i in range(1, 13) :
    a.append(randint(1, 1000))

c = []

start_time = time.time()
for k in a :
        x = count_irr(k)
        c.append(x)
t_0 = (-start_time + time.time())

# Typical execution time is below 0.5seconds
print('Execution time is %s seconds' % t_0)

for i in range(0, len(a)) :
        print('n= %s and nr_irr_frac=%s' % (a[i], c[i]))

Unless I am missing something. Solution is very simple with O(n^2) runtime

def countUniqueFraction(n):
    
    ufraction = set()
    count = 0
    for i in range(1,n+1):
        for j in range(i+1, n+1):        
            ufraction.add(i/j)
    
    return len(ufraction)

The key here is that for non reduce-able fraction the gcd(greatest common divisor) of the numerator and denominator must be 1 or in other words they must be co-prime.

int gcd(int a,int b){
	if(b==0)
		return a;
	return gcd(b,a%b);
}
bool isNonReduceableFraction(int numerator,int denominator){
	if(gcd(numerator,denominator)==1)
		return true;
	return false;
}

int getNumberofReducibleFractions(int n){
		HashSet<Double> fractionSet = new HashSet<Double>();
		
		if(n<=0){
			return 0;
		}
		
		for(double i = 1; i<=n; i++){
			double j = i;
			while(j<=n){
				double d = (double) (i/j);
				if(d < 1.0){
					fractionSet.add(d);
				}
				j++;
				
			}
			
		}
		return fractionSet.size();
	}

int getNumberofReducibleFractions(int n){
		HashSet<Double> fractionSet = new HashSet<Double>();
		
		if(n<=0){
			return 0;
		}
		
		for(double i = 1; i<=n; i++){
			double j = i;
			while(j<=n){
				double d = (double) (i/j);
				if(d < 1.0){
					fractionSet.add(d);
				}
				j++;
				
			}
			
		}
		return fractionSet.size();

}

import java.util.ArrayList;

public class Test {
public static void main(String[] args) {
int n = 4, count = 0;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
//System.out.println(i+"/"+j);
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
temp.add(dou);
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}

// 1/1, 1/2,1/3,1/4,2/2,2/3,2/4,3/3,3/4,4/4

import java.util.ArrayList;

public class Test {
public static void main(String[] args) {
int n = 4, count = 0;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
//System.out.println(i+"/"+j);
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
temp.add(dou);
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}

// 1/1, 1/2,1/3,1/4,2/2,2/3,2/4,3/3,3/4,4/4

import java.util.ArrayList;
import java.util.Scanner;

public class Test {
public static void main(String[] args) {
int n, count = 0;

Scanner s = new Scanner(System.in);
System.out.println("Please Enter Fraction Nunber to check");
n = Integer.parseInt(s.next());
s.close();
//n = 4;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
temp.add(dou);
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}

// 1/1, 1/2,1/3,1/4,2/2,2/3,2/4,3/3,3/4,4/4

Which one is correct code

import java.util.ArrayList;
import java.util.Scanner;

public class Test {
public static void main(String[] args) {
int n, count = 0;

Scanner s = new Scanner(System.in);
System.out.println("Please Enter Fraction Nunber to check");
n = Integer.parseInt(s.next());
s.close();
//n = 4;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
temp.add(dou);
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}

import java.util.ArrayList;
import java.util.Scanner;

public class Test {
public static void main(String[] args) {
int n, count = 0;

Scanner s = new Scanner(System.in);
System.out.println("Please Enter Fraction Nunber to check");
n = Integer.parseInt(s.next());
s.close();
//n = 4;
ArrayList<Double> temp = new ArrayList<>();
Double dou;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
dou = ((double)i / (double)j);
if (dou != 1) {
if (!temp.contains(dou)) {
temp.add(dou);
System.out.println(i+"/"+j);
count++;
}
}
}
}
System.out.println(count);
}
}