Posts Tagged with "Modulo"

Problem146

Project Euler 146: Investigating a Prime Pattern

Saturday, April 27, 2013

4 Comments

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...
problem134

Project Euler 134: Prime pair connection

Saturday, February 2, 2013

5 Comments

With a little help from Wikipedia I found Problem 134 of Project Euler rather easy to solve. Well it was easy after solving some issues I had with integer overflows and several other bugs. But anyway, the problem readsIn fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.Find ΣS for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.Based on the problem description it is rather easy to formulate this as linear congruence and then all we need to do, is to figure out how to solve that.

Continue reading...
problem133

Project Euler 133: Repunit nonfactors

Saturday, January 26, 2013

4 Comments

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...
Problem132

Project Euler 132: Large repunit factors

Saturday, January 19, 2013

4 Comments

In problem 132 of Project Euler we are going back to working with repunits in a problem that readsFind the sum of the first forty prime factors of the repuint R(109).This is a pretty large number, and having to actually do trial division would be a pain and take quite a while, even though we have BigInteger class which is certainly a help here.

Continue reading...
problem129

Project Euler 130: Finding composite values, n, for which n−1 is divisible by the length of the smallest repunits that divide it.

Saturday, January 5, 2013

2 Comments

Problem 130 of Project Euler is a continuation of problem 129, so if you have already solved that this one should be pretty easy. It readsFind the sum of the first twenty-five composite values of n for which GCD(n, 10) = 1 and n - 1 is divisible by A(n).If you have already solved Problem 129 as we have, this one can be solved pretty easily. We already have a function that will give us A(n), so we can just brute force our way through the problem calculating check if n-1 is divisible by A(n) and n is not a prime.

Continue reading...
problem129

Project Euler 129: Investigating minimal repunits that divide by n.

Saturday, December 29, 2012

6 Comments

Problem 129 of Project Euler readsA 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.Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible byn, and let A(n) be the least such value of kFind the least value of n for which A(n) first exceeds one-million.This problem can be solved by applying the principles of long division so we avoid having to multiply extremely large numbers

Continue reading...
problem123

Project Euler 123: Determining the remainder when (pn − 1)^n + (pn + 1)^n is divided by pn^2

Saturday, November 17, 2012

6 Comments

Problem 123 of Project Euler readsLet pn be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder when (pn-1)n + (pn+1)n is divided by pn2.Find the least value of n for which the remainder first exceeds 1010.A nice and short problem description which will also have a nice and short solution post since we solved Problem 120 which is very similar to this problem.

Continue reading...
problem120

Project Euler 120: Finding the maximum remainder when (a − 1)^n + (a + 1)^n is divided by a^2

Saturday, October 27, 2012

1 Comment

Problem 120 of Project Euler is back in the very mathy part of the questions. Or at least the part where I have been able to find a pretty mathy solution for the problem. It readsLet r be the remainder when (a-1)n + (a+1)n is divided by a2. For 3 ≤ a ≤ 1000, find ∑ rmax.If we wanted to brute force this, we would have to investigate all values of a, as well as a whole lot of values of n for each a. So likely it would be a rather big problem space to search through. So let us look at the polynomial expression on the left (a-1)n + (a+1)n.

Continue reading...
uva10127header

UVa 10127: Ones

Wednesday, May 16, 2012

3 Comments

Problem 10127 at UVa Online Judge, Ones, is a neat little problem. We are given an integer and are asked to find its smallest multiple that consists only of ones.We start off by coming up with a simple brute-force solution which, unfortunately, doesn't even work. With some clever observations and some thinking in reverse-mode, we manage create a good solution that works. We also see the interesting results of an attempt I made to make an even faster solution, which unfortunately turned out to be slower.

Continue reading...
uva10229header

UVa 10229: Modular Fibonacci

Wednesday, May 9, 2012

3 Comments

In problem 10229 at UVa Online Judge, Modular Fibonacci, our task is to calculate huge Fibonacci numbers, modulo some given integer.We analyse different methods of computing Fibonacci numbers, but they are either too slow or aren't applicable in our situation. We end up developing a fast solution that makes use of Fibonacci numbers in matrix form and exponentiation by squaring.

Continue reading...