Prime factorisation

Project Euler 146: Investigating a Prime Pattern

Project Euler 146: Investigating a Prime Pattern

In Problem 146 of Project Euler we are working with primes again, and some quite big ones even. The problem reads

The smallest positive integer n for which the numbers n2+1, n2+3, n2+7, n2+9, n2+13, and n2+27 are consecutive primes is 10. The sum of all such integers n below one-million is 1242490.

What is the sum of all such integers n below 150 million?

At first I thought I could just make a sieve up to 150 million and then check if the numbers were contained in that. However, rereading the problem I realized I was completely wrong. So in a pure brute force solution we would need to check 150 million values of n and up to 13 numbers for each, since we both need to check that the given numbers are prime. But also that the odd numbers inbetween are not prime. So potentially we have to check 1950 million numbers for primality, which is a moderately expensive operation. Continue reading →

Posted by Kristian in Project Euler, 7 comments
Project Euler 133: Repunit nonfactors

Project Euler 133: Repunit nonfactors

Problem 133 of Project Euler is a continuation of Problem 132 and Problem 129 in which we are supposed to find the some prime numbers which are not factors of R(10n) for any n. In fact the problem reads

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Let us consider repunits of the form R(10n).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10n) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10n).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).

Continue reading →

Posted by Kristian in Project Euler, 6 comments
Project Euler 110: Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.

Project Euler 110: Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.

Problem 110 of Project Euler is a continuation of Problem 108 except that we need a solution approach which is much more efficient. The problem reads

In the following equation xy, and n are positive integers.

It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred.

What is the least value of n for which the number of distinct solutions exceeds four million?

NOTE: This problem is a much more difficult version of problem 108 and as it is well beyond the limitations of a brute force approach it requires a clever implementation.

Continue reading →

Posted by Kristian in Project Euler, 3 comments
Project Euler 108: Solving the Diophantine equation 1/x + 1/y = 1/n.

Project Euler 108: Solving the Diophantine equation 1/x + 1/y = 1/n.

Let us jump right into Problem 108 of Project Euler which reads

In the following equation xy, and n are positive integers.

For n = 4 there are exactly three distinct solutions:

What is the least value of n for which the number of distinct solutions exceeds one-thousand?

NOTE: This problem is an easier version of problem 110; it is strongly advised that you solve this one first.

Continue reading →

Posted by Kristian in Project Euler, 8 comments
Project Euler 95: Find the smallest member of the longest amicable chain with no element exceeding one million.

Project Euler 95: Find the smallest member of the longest amicable chain with no element exceeding one million.

Even though we are still below 5000 people who have solved Problem 95 of Project Euler this problem it proved to be a relatively easy problem to solve. The main challenge was to find a method to get the speed of the solution to reasonable level. The problem reads

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

Continue reading →

Posted by Kristian in Project Euler, 5 comments
UVa 294: Divisors

UVa 294: Divisors

In UVa 294, Divisors, we are asked to find the number with the maximum number of divisors in a given range. Counting number of divisors is a classic problem, and there exists a fast and simple way to do it. We start off with a straight-forward, but slow, implementation and progressively optimize it until it’s fast enough. We don’t stop there, though, but we end with a much faster implementation by noticing that divisor count is related to prime factorization.

Read the problem description here or here. Continue reading →

Posted by Bjarki Ágúst in UVa Online Judge, 8 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
Project Euler 47: Find the first four consecutive integers to have four distinct primes factors.

Project Euler 47: Find the first four consecutive integers to have four distinct primes factors.

One of the big topics in number theory – Prime factorization – is once again the topic of a Project Euler problem. Problem 47 reads

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 x 7
15 = 3 x 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² x 7 x 23
645 = 3 x 5 x 43
646 = 2 x 17 x 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

Continue reading →

Posted by Kristian in Project Euler, 19 comments