MathBlog
A man's journey through the wonderful world of Math and ProgrammingPosts Tagged with "Prime Generation"
Project Euler 111: Search for 10-digit primes containing the maximum number of repeated digits.
So in Problem 111 of Project Euler we are back at dealing with prime numbers. And rather large ones of them. But before going into details, here is the problem descriptionWe shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.Find the sum of all S(10, d).I rather quickly realized that there must be two solution approaches to this problem. Either we generate all the primes in the range and start finding the right ones. Or we can generate numbers with repeated digits and check if they are primes.I started out with the first approach, by trying to generate primes up to 10.000.000.000, but I ran into problems with my sieve as we have to index more than can be stored in an integer. So either I could rewrite the sieve or I could look into the other approach.
Continue reading...
Project Euler 58: Investigate the number of primes that lie on the diagonals of the spiral grid
Saturday, August 27, 2011
In Problem 58 of Project Euler we are revisiting the spiral we worked on in Problem 28. I have since then learned that it is called an Ulam spiral after the Polish born American mathematician Stanislaw Ulam. The problem reads:What is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?In problem 28 we sought and found a closed form solution to finding the sum of the diagonals. In this problem we need to investigate each corner of the spiral. So we need to generate each corner an check it. I have found no other way than brute force to create the corners and check them. I found no pattern in the primes except that they never occurs in the lower right diagonal. The numbers there are always perfect squares due to the nature of the spiral.
Continue reading...Project Euler 46: What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
Saturday, June 4, 2011
Problem 46 of Project Euler readsWhat is the smallest odd composite that cannot be written as the sum of a prime and twice a square? I haven't found ways to solve this except for brute force, but I have found three slightly different approaches brute forcing the problem.
Continue reading...Project Euler 35: How many circular primes are there below one million?
Saturday, April 9, 2011
In problem 35 of Project Euler we are back to primes., this time it is circular primes that we are focusing on. Before looking more at circular primes lets look at the problem description which reads How many circular primes are there below one million? At first I thought circular primes were any permutation of the prime, but then 791 would be in the example as well, so I realised that it is primes that you can rotate such that any rotation is also a prime. I must admit that I don't think I have found a very nice solution, but it runs fast enough to satisfy me. It is a brute force algorithm where we search every prime below 1.000.000 to see if it can be rotated.
Continue reading...Sum of all Primes below 2000000 – Problem 10
Sunday, November 21, 2010
Problem 10 is all about primes, just like probem 7. The problem is Find the sum of all the primes below two million.I take three different approaches to the solution, and focus on Sieve of Eratosthenes, which I will present the source code for an optimized version of.
Continue reading...Project Euler – Problem 7
Wednesday, November 3, 2010
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.What is the 10001st prime number?We could solve this by brute force checking all the numbers, or we could reuse part of the solution to problem 5, where we generated a list of primes using trial division with already found prime numbers.
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, August 25, 2012
1 Comment