--11
function is_prime(n)

	if n % 2 == 0 and n ~= 2 then return false end
	ss = floor(sqrt(n))
	if ss * ss  == n then return false end
	local i  = 3
	while i <= ss do
		if n % i == 0 then return false end
		i = i + 2
	end
	return true
end
--12
function gcd(a,b)
	local c = a % b
	if c  == 0 then	return b else return gcd(b, c) end
end

--13
function relative_prime(a,b)
	return gcd(a,b) == 1
end

--14
function phi(n)

	local c = 0
	if is_prime(n) then return n-1
	else
		for i = 1, n do
			if relative_prime(i,n) then
				c = c + 1
			end
		end
	end
	return c
end

function get_primes(n)
	local primes = {}
	ss = math.floor(math.sqrt(n))
	for i =2, n do
		primes[i] = true
	end
	for i = 2, n do
		if primes[i] then
			for j = i*i, n, i do
				primes[j] = nil
			end
		end
	end
	return primes
end

--15
function prime_factors(n)

	local primes = get_primes(n)
	local factors = {}

	local function factor(n)
		if primes[n] then
			table.insert(factors,n)
			return
		else
			for i,v in pairs(primes) do
				if n % i  == 0 then
					table.insert(factors,i)
					return factor(n/i)
				end
			end
		end
	end

	factor(n)

	return factors
end

--16
function unique_prime_factors(n)
	local count = 0
	local factors = prime_factors(n)
	local uniques = {}
	local duplicates = {}
	local dup = 1

	for i = 1, #factors do
		local f = factors[i]
		local next = factors[i+1]

		if next == f then
			dup = dup + 1
		else
			table.insert(uniques,f)
			table.insert(duplicates,dup)
			dup = 1
		end
	end

	return uniques,duplicates
end

--17
function phi_2(n)
	local pow = math.pow
	p,k = unique_prime_factors(n)
	local sum = 1
	for i=1,#p do
		sum = sum * (p[i] - 1)*pow(p[i],(k[i] - 1))
	end
	return sum
end

print(phi(10090))
print(phi_2(10090))


--18
function gen(n)
	return get_primes(n)
end
--19
function goldbach(n)
	primes = get_primes(n)

	for i,v in pairs(primes) do
		if primes[i] and primes[n-i] then
			return i,n-i
		end
	end
	return false
end
for i=4, 1000,2 do
	if not goldbach(i) then print("not able "..i) end
end

function f(a, x, x0)
	if x == 0 then
		return x0
	end
	return f(a,x-1)/4 * (5 - a*f(a,x-1,x0)^3)
end