Euler’s totient function

The MathBlog tools collection updated

The MathBlog tools collection updated

Just wanted to make a bit of advertisement for the tool section of the website which have been updated and new tools added.

Bjarki has been busy and developed several new tools which might come in handy for you when trying to see if a hypothesis could lead to a solution for the problem you are sitting with.

Updated tools

First of all the Prime factorization tool has been updated.  So now it gives you a little more than just the factorization. It gives you the number of distinct factors, the number of divisors and not least the value of Euler’s totient function. Yep that’s right, so head over and check it out. Continue reading →

Posted by Kristian in Other, 2 comments
Project Euler 72: How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000

Project Euler 72: How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000

I don’t think it is a coincidence that this exact problem comes right now as we shall see in the solution of the problem. Problem 72 of Project Euler reads

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

The first thing to note is that in here HCF is the same as the greatest common divisor or GCD as I usually use. The second thing to note is that we are probably looking for a very large number, but let us take a look at the problem. Continue reading →

Posted by Kristian in Project Euler, 15 comments
Project Euler 70: Investigate values of n for which φ(n) is a permutation of n.

Project Euler 70: Investigate values of n for which φ(n) is a permutation of n.

For this problem I have taken a bit of a lazy approach with the coding and not emptied the search space, but just searched where we are most likely to find a solution. However, there are several tricks we can use when we try to find a solution. However, before babbling on, here is the problem we want to solve

Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

Looks familiar? Well, the phi function is the same function as we looked at previously. Continue reading →

Posted by Kristian in Project Euler, 12 comments
Project Euler 69: Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

Project Euler 69: Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

We are changing topics again to a more classical number theory problem with Problem 69 of Project Euler. The problem is about factoring and reads

Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

n Relatively Prime φ(n) n/φ(n)
2 1 1 2
3 1,2 2 1.5
4 1,3 2 2
5 1,2,3,4 4 1.25
6 1,5 2 3
7 1,2,3,4,5,6 6 1.1666…
8 1,3,5,7 4 2
9 1,2,4,5,7,8 6 1.5
10 1,3,7,9 4 2.5

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

Continue reading →

Posted by Kristian in Project Euler, 19 comments