Posts Tagged with "Arithmetic"

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

Saturday, October 27, 2012


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

UVa 10055: Hashmat the brave warrior

Thursday, July 5, 2012


In problem 10055 at the UVa online judge, we are asked to help Hashmat, the brave warrior, to decide whether he should fight against his opponents. We do that be calculating the difference between the number of Hashmat's soldiers and the number of his opponent's soldiers.The problem is an easy one, but has still eluded many. After little work we end up with an almost one-line solution.

Continue reading...

UVa 10783: Odd Sum

Wednesday, June 13, 2012


Problem 10783 at the UVa Online Judge, also known as Odd Sum, asks us to compute the sum of odd numbers in a given range. The problem is easy, but fun, and can be solved in a similar way to the first Project Euler problem. We start off by creating a straight-forward solution which unfortunately works due to small test cases. We do one minor optimization and then finally finish with a neat closed-form solution.

Continue reading...

Project Euler 97: Find the last ten digits of the non-Mersenne prime: 28433 × 2^7830457 + 1

Saturday, May 19, 2012


I am almost embarrassed to make a post about problem 97 of Project Euler which readsHowever, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 2843327830457+1. Find the last ten digits of this prime number.I decided to use the BigInteger class for solving this, so I didn't have to care about numerical issues. The only other insight that was needed was to use the ModPow method which takes the modulo along with the power instead of doing those seperatly.

Continue reading...
Project Euler 71: Listing reduced proper fractions in ascending order of size.

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...
McNugget numbers

McNugget numbers – The Answer

Sunday, June 26, 2011


Last Sunday I posted a question I had asked my self about McNugget numbers with a promise that I would actually post an answer to the problem as well. So here we go.The McNugget numbers are fairly well described on the Internet and both Wolfram and WikiPedia describes the problem.

Continue reading...

Project Euler 49: Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other

Saturday, June 25, 2011


Problem 49 of Project Euler asks us to find three numbers with the following propertiesThe arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another. There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.Avid readers of the blog knows how fond of prime number lists by now, so I took that approach instead. I took the following approach.Generate a list of primes below between 1000 and 10000. Take two primes i and j with i < jand calculate k = j + (j-i). Check if k< 10000 and check if k is a prime, if not go to 2. Check if i and j are permutations of each other and check if i and k are permutations of each other. If not go to 2. Found the triple, so exit.

Continue reading...
McNugget numbers

McNugget numbers – The Question

Sunday, June 19, 2011


This post is about McNugget numbers and a small mental math exercise I gave my self this week while driving on the high way.To start with the beginning of the story. I was driving for quite a while this Friday - actually for the better part of 4 hours. Which I in many ways consider a waste of time and energy, but I had to for several reasons. At one point I stopped at McDonald's to get a cup of coffee and stretch my legs.

Continue reading...
Project Euler 48: Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000

Project Euler 48: Find the last ten digits of 1^1 + 2^2 + … + 1000^1000

Saturday, June 18, 2011


Problem 48 of Project Euler has the nice and simple descriptionFind the last ten digits of the series, 11 + 22 + 33 + ... + 10001000.When I first saw the problem, I thought I knew it would be trivial to solve with BigInteger. However, it turns out that the solution lacks performance, so I have derived another solution as well based on the properties of the modulo operator.

Continue reading...

Project Euler 39: If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

Tuesday, May 3, 2011


Even though the title nor the description of Problem 39 of Project Euler mentions Pythagorean Triplets, this is the topic we are revisiting. The problem description readsIf p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.{20,48,52}, {24,45,51}, {30,40,50}For which value of p ≤ 1000, is the number of solutions maximised?The answer is certainly not p = 1000 which I can state so boldly since we in Problem 9 was given the fact that there only exists 1 triplet with that property.I have found three different approaches to solving this problem. We can brute force it, we can take an arithmetic approach where we rewrite the equations so we only have to work two parameters and check if an equation has an integer solution, and last but not least we can reuse all the work we derived in solving Problem 9 yielding a very efficient solution to the problem.

Continue reading...
This site uses cookies.