magic-fractions

A Magic Fraction for N is one that has the following properties:
It is a proper fraction (The value is < 1)
It cannot be reduced further (The GCD of the numerator and the denominator is 1)
The product of the numerator and the denominator is factorial of N. i.e. if a/b is the fraction, then a*b = N!

Examples of Magic Fractions are:

1/2      [ gcd(1,2) = 1 and 1*2=2! ]

2/3      [ gcd(2,3) = 1 and 2*3=3! ]

3/8      [ gcd(3,8) = 1 and 3*8=4! ]

2/12  for example, is not a magic fraction, as even though 2*12=4!, gcd(2,12) != 1

And Magic fractions for number 3 are: 2/3 and 1/6 (since both of them satisfy the above criteria, are of the form a/b where a*b = 3!)

Now given a number N, you need to print the total number of magic fractions that exist, for all numbers between 1 and N (include magic fractions for N, too).

Note:
The number N will be in the range [1, 500]. (1 and 500 inclusive)
You'll have to read the input from STDIN, and print the output to STDOUT

Examples:

1)

Input: 1

Output: 0

Explanation: There is no fraction < 1 whose numerator * denominator = 1!

2)

Input: 3

Output: 3

Explanation: 0 for 1 + 1 for 2 [1/2] + 2 for 3 [1/6, 2/3]

3)

Input: 5

Output: 9 

SAMPLE INPUT
8

SAMPLE OUTPUT
29

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
'''
Created on 27-Oct-2014

@author: gautam
'''
import fractions
if __name__ == '__main__':
	primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499]
	N = int(input())
	c = 0
	ans = [0]*(N+1)
	if N > 1:
	    ans[2] = 1
	    for i in range(3,N+1):
	    	if i in primes:
	    		ans[i] = ans[i-1]*2
	    	else:
	    		ans[i] = ans[i-1]
	print(sum(ans))
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import math



N = eval(input())

if(N==1):
	print(0)
elif N==2:
	print(1)
else:	
	count = 1
	prev = 1
	for i in range(3, N+1):
		prime = True
		for j in range(2,int(math.sqrt(i))+1):
			if i%j==0:
				prime = False
				break
		if prime:
			prev = prev*2
		count += prev

	print(count)


t=int(input())
count=1
#print t
if t<2:
	count=0
	
prev=1
for j in range(3,t+1):
	#print t
	prime=True
	#print j
	num=j
	i=2
	while i*i<=j:
		#print j
		if(num%i==0):
			prime=False
			break
		i=i+1
	if (prime):
		prev=prev*2
		#print prev
	count=count+prev
		
	
 
print(count)


import math
n=eval(input())
fact_cnt=0
cnt=0
prime_list= [2, 3, 5, 7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]

	
for i in range(2,n+1):
	for num in prime_list:
		if i%num==0:
		prime_list.remove(num)
		fact_cnt+=1
	cnt+=pow(2,fact_cnt-1)
print(cnt)
	



def isprime(n):
	x=int(pow(n,0.5))
	flag=0
	for i in range(2,x+1):
		if n%i==0:
			flag=1
			return 0
	return 1
a=[0]*505
a[0]=0
a[1]=0
a[2]=1
cnt=1
for i in range(3,505):
	if isprime(i):
		cnt=cnt*2
		a[i]=a[i-1]+cnt
	else:
		a[i]=a[i-1]+cnt
n=eval(input())
print(a[n])


t=int(input())
count=1
#print t
if t<2:
	count=0
	
prev=1
for j in range(3,t+1):
	#print t
	prime=True
	#print j
	num=j
	i=2
	while i*i<=j:
		#print j
		if(num%i==0):
			prime=False
			break
		i=i+1
	if (prime):
		prev=prev*2
		#print prev
	count=count+prev
		
	
print(count)


n=int(input())
#taking input and doing the things. requires.
def trial_division(n, bound=None):
	if n == 1: return 1
	for p in [2, 3, 5]:
		if n%p == 0: return p
	if bound == None: bound = n
	dif = [6, 4, 2, 4, 2, 4, 6, 2]
	m = 7; i = 1
	while m <= bound and m*m <= n:
		if n%m == 0:
			return m
		m += dif[i%8]
		i += 1
	return n
#having factors of the number
def factor(n):
	if n in [-1, 0, 1]: return []
	if n < 0: n = -n
	F = []
	#checking whether there are co primes or not.
	while n != 1:
		p = trial_division(n)
		e = 1
		n /= p
		while n%p == 0:
			e += 1; n /= p
		F.append((p,e))
	F.sort()
	return F

ans=0
f=[]
num=1

#calculating the total number of factors.
for i in range(2,n+1):
#2^n - 1 where n is primes.
	num*=i
	temp = len(factor(num))
	ans+=pow(2,temp-1)
print(ans)


import math

prime = []
#dic = {}
table = {}

numb = []
den = []
num = []


def sort(n):
	global den
	global num
	
	if n == len(numb): 
		#print den
		#print num, "\n \n"
		if add(num) < add(den): 
			return 1
		else:
			return 0

	
	ex = 0
	
	den.append(numb[n])
	ex += sort(n+1)
	
	den.remove(numb[n])
	
	num.append(numb[n])
	ex += sort(n+1)
	
	num.remove(numb[n])
	
	#put nth in either
	return ex

def add(arr):
	sum = 0
	for n in arr:
		sum += pow(n, table[current][n])
	return sum

def tablize(n):
	dic = {}
	for i in range(2, n+1):
		
		
		if i in prime:
			curr = n
			dic[i] = 0
			while curr > i:
				curr = int(curr/i) 				#Check if floored
				dic[i] += curr
		
	table[n] = dic		

	return dic



def factorize(n):
	if n in prime:
		return {n:1}
	fact = {}
	for j in range(2, int(n/2)+1):
		if n%j == 0:
			if j in prime:
				fact[j] = 1
				temp = factorize(n/j)
				
				for x in list(temp.keys()):
					if x in fact:
						fact[x] = fact[x] + temp[x]
					else:
						fact[x] = temp[x]
				break
				
	return fact
	
	
def merge(g, t):
	for n in list(t.keys()):
		g[n] = g[n] + t[n]
'''	
def merge(t):
	global dic
	for n in t.keys():
		dic[n] = dic[n] + t[n]
'''		
def primes(n):
	global prime
	flag = False
	for i in range(5, n+1):
		for j in range(2, int(math.sqrt(i))+1):
			if i%j == 0:
				flag = True
				break
			
		if flag == True:
			flag = False	
			continue
		prime.append(i)
def ans(n):
	if n == 1:
		return 0
	
	ans = 1
	prev = 1
	for i in range(3, n+1):
		if i in prime:
			prev = prev*2
		ans += prev
	return ans
prime = [2, 3]
N = int(input())
primes(N)

total = ans(N)
#for i in range(2, N+1):
#	tablize(i)
#	numb = table[i].keys()
#	current = i
#	total += sort(0)




print(total)

#print table[N]


#for i in table[n].keys():


t=int(input())
count=1
#print t
if t<2:
	count=0
	
prev=1
for j in range(3,t+1):
	#print t
	prime=True
	#print j
	num=j
	i=2
	while i*i<=j:
		#print j
		if(num%i==0):
			prime=False
			break
		i=i+1
	if (prime):
		prev=prev*2
		#print prev
	count=count+prev
		
	

print(count)
				
				


def prime(n):
	x=int(n**0.5)
	for i in range(2,x+1):
		if n%i==0:
			return False
	return True
n=eval(input())
sum=0
count=0
for i in range(2,n+1):
	if prime(i)==True:
		count=count+1
		sum=sum+2**(count-1)
	else:
		sum=sum+2**(count-1)
print(sum)


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499]

def magicfraction(n) :
	if (n<=1) :
		return 0
	if (n == 2) :
		return 1
	if (n == 3) :
		return 3
	if (n == 4) :
		return 5
	if (n >= 5) :
		total = 0
		prev = 2
		evens = 0
		for i in range(5, n+1) :
			if (i in primes) :
				prev += 1
			total += 2**prev
			if (prev%2 == 0) :
				evens += 1
		total = total/2
		#if (evens >0) :
		#	total += (2**(2*evens - 1))
		
		return total+5
n = eval(input())
print(magicfraction(n))


n=eval(input())
def div(x):
	if x == 1: return 1
	if x%2==0:	return 2
	if x%3==0:	return 3
	if x%5==0:	return 5
	
	d = [6, 4, 2, 4, 2, 4, 6, 2]
	mx = 7
	i = 1
	while mx*mx <= x and mx <= x:
		if x%mx == 0:
			return mx
		mx += d[i%8]
		i += 1
	return x

def fac(n):
	if n<=1 and n>=-1: return []
	if n < 0: n = -n
	ret = []
	while n != 1:
		d = div(n)
		e = 0
		while n%d == 0:
			e += 1; n /= d
		ret.append((d,e))
	ret.sort()
	return ret

ans=0
num=1

for i in range(2,n+1):
	num*=i
	ans += pow(2,len(fac(num))-1)
print(ans)


n=int(input())
def trial_division(n, bound=None):
	if n == 1: return 1
	for p in [2, 3, 5]:
		if n%p == 0: return p
	if bound == None: bound = n
	dif = [6, 4, 2, 4, 2, 4, 6, 2]
	m = 7; i = 1
	while m <= bound and m*m <= n:
		if n%m == 0:
			return m
		m += dif[i%8]
		i += 1
	return n

def factor(n):
	if n in [-1, 0, 1]: return []
	if n < 0: n = -n
	F = []
	while n != 1:
		p = trial_division(n)
		e = 1
		n /= p
		while n%p == 0:
			e += 1; n /= p
		F.append((p,e))
	F.sort()
	return F

ans=0
f=[]
num=1

for i in range(2,n+1):
	num*=i
	temp = len(factor(num))
	ans+=pow(2,temp-1)
print(ans)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def checkprime(a):
	for i in range(2,a):
		if(a%i==0):
			return False
	return True
numb=int(input());
adder=1
res=1
if(numb<=2):
	res=numb-1
else:
	for j in range(3,numb+1):
		if(checkprime(j)==True):
			adder=adder*2
		res=res+adder
print(res)
		
	
		


def isprime(n):
	x=int(pow(n,0.5))
	flag=0
	for i in range(2,x+1):
		if n%i==0:
			flag=1
			return 0
	return 1
a=[0]*505
a[0]=0
a[1]=0
a[2]=1
cnt=1
for i in range(3,505):
	if isprime(i):
		cnt=cnt*2
		a[i]=a[i-1]+cnt
	else:
		a[i]=a[i-1]+cnt
n=eval(input())
print(a[n])


def isprime(p):
	c=0
	for i in range(p):
		if i!=0 and i!=1:
			if p%i==0:
				return 0;
	return 1;
a=[]
c=0
for i in range(501):
	if i==0:
		a.append(0)
	elif i==1:
		a.append(0)
	else:
		if isprime(i)==1:
			c=c+1
		a.append(a[i-1]+pow(2,c-1))
n=int(input())
print(a[n]);
	


def check_prime(number):
	count=0
	for i in range(number):
		if i!=0 and i!=1:
			if number%i==0:
				return 0;
	return 1;
a=[]
count=0
for j in range(501):
	if j==0:
		a.append(0)
	elif j==1:
		a.append(0)
	else:
		if check_prime(j)==1:
			count=count+1
		a.append(a[j-1]+pow(2,count-1))
n=int(input())
print(a[n]);
	


import math
primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499]
n=int(input())
sum,j=0,0
prev=0
if n==1: print(0)
else:
	for i in range(1,n+1):
		if primes[j]>i:
			sum+=prev
		else:
			j=j+1
			prev=pow(2,j-1)
			sum+=prev
		#print "adding ",prev,"to",sum
	print(sum)


ar=[]
for i in range(1009):
	ar.append(0)
for i in range(2,1000):
	if ar[i]==0:
		j=i
		while j*i<=1000:
			ar[i*j]=1
			j += 1
pre=[]
a=0
for i in range(1000):
	pre.append(0)
for i in range(2,700):
	if ar[i]==0: a += 1
	pre[i]=pre[i-1]
	pre[i] += 2**(a-1)
n=eval(input())
print(pre[n])


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def isprime(n):
	x=int(pow(n,0.5))
	flag=0
	for i in range(2,x+1):
		if n%i==0:
			flag=1
			return 0
	return 1
a=[0]*505
a[0]=0
a[1]=0
a[2]=1
cnt=1
for i in range(3,505):
	if isprime(i):
		cnt=cnt*2
		a[i]=a[i-1]+cnt
	else:
		a[i]=a[i-1]+cnt
n=eval(input())
print(a[n])