MathBlog
A man's journey through the wonderful world of Math and ProgrammingPosts Tagged with "Prime factorisation"
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 [...]
Continue reading...
Project Euler 133: Repunit nonfactors
Saturday, January 26, 2013
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 readsFind the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).I have found two methods for solving this. Both build upon the same principle which I will present first...
Continue reading...
Project Euler 110: Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.
Saturday, August 18, 2012
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 readsIn the following equation x, y, and n are positive integers.1/x + 1/y = 1/n 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?So what happens if we just run the same code as in problem 108? Well first of all we would get in problems with the capacity of the variables, but we could just change it to BigInteger and then run it. I tried, and gave up after a while. So I changed the solution approach...
Continue reading...Project Euler 108: Solving the Diophantine equation 1/x + 1/y = 1/n.
Saturday, August 4, 2012
Let us jump right into Problem 108 of Project Euler which readsIn the following equation x, y, and n are positive integers.1/x + 1/y = 1/n What is the least value of n for which the number of distinct solutions exceeds one-thousand?We could possibly brute force, but my guess is that it would take a rather long time to do so. So instead I started fiddling around with the equation to get some insight into the problem.
Continue reading...
Project Euler 95: Find the smallest member of the longest amicable chain with no element exceeding one million.
Saturday, May 5, 2012
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 readsFind the smallest member of the longest amicable chain with no element exceeding one million.I managed to make two solutions which differs in the way they calculate the sum of factors. Otherwise they are the same. The first solution relies on a function to return the sum of factors when needed. This method I will cover first.
Continue reading...UVa 294: Divisors
Wednesday, April 25, 2012
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.
Continue reading...
Project Euler 72: How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000
Saturday, November 26, 2011
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 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...
Project Euler 70: Investigate values of n for which φ(n) is a permutation of n.
Saturday, November 12, 2011
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 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...Project Euler 69: Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
Saturday, November 5, 2011
We are changing topics again to a more classical number theory problem with Problem 69 of Project Euler. The problem is about factoring and readsEuler'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. Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.My first thought was to reuse some of the old problems which dealt with factoring. Problem 12 was a pretty good candidate for this. However before I got that far I realised two things.
Continue reading...
Project Euler 47: Find the first four consecutive integers to have four distinct primes factors.
Saturday, June 11, 2011
e of the big topics in number theory - Prime factorization - is once again the topic of a Project Euler problem. Problem 47 readsFind the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?I would love to say that I have found some clever way to approach this problem, but the fact is that I haven't. The only solution I have found is to brute force it.
Continue reading...- Taking a break
- Project Euler 146: Investigating a Prime Pattern
- Project Euler 145: How many reversible numbers are there below one-billion?
- UVa Online Judge New Platform
- Project Euler 144: Investigating multiple reflections of a laser beam.
- Project Euler 143: Investigating the Torricelli point of a triangle
- Project Euler 142: Perfect Square Collection
- Project Euler 141:Investigating progressive numbers, n, which are also square.
- Project Euler 140: Modified Fibonacci golden nuggets
- Project Euler 139: Pythagorean tiles
- reiden4: what a great and simple solution.. I got it right but it took me a while by using strings and adding its length.. I have never thought of this soluti...
- Son-Huy TRAN: I found that if 1 + a + b is prime, so : 1 + a + b > 1 => a + b > 0Because b is prime so b > 0, so if a < 0 : |a| < |b|So ...
- Jevon Jaconi: late arrival to the party and now it ends; that's my luck - j/k - have a good one and look forward to reading it again soon!;...
- Jean-Marie Hachey: Hi Kristian,Thank you very much for all the work done on your blog. Impressive production. Highly appreciated.Jeg takker dem meget, Merci b...
- S.Ged: Why all of numbers coming at most 1 time ?...
- Bjarki Ágúst: This is one of my favorite problems. I solved it very similarly. Given [latex]p_1[/latex] and [latex]p_2[/latex], I wanted to find an integer [latex]x...
Saturday, April 27, 2013
2 Comments