Arithmetic

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

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

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 reads

Let r be the remainder when (a-1)n + (a+1)n is divided by a2.

For example, if a = 7 and n = 3, then r = 42: 63 + 83 = 728  42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that rmax= 42.

For 3 ≤ a ≤ 1000, find ∑ rmax.

Continue reading →

Posted by Kristian in Project Euler, 6 comments
Project Euler 97: Find the last ten digits of the non-Mersenne prime: 28433 × 2^7830457 + 1

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

I am almost embarrassed to make a post about problem 97 of Project Euler which reads

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1.

Find the last ten digits of this prime number.

Continue reading →

Posted by Kristian in Project Euler, 3 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
McNugget numbers – The Answer

McNugget numbers – The Answer

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.

McNuggetsThe McNugget numbers are fairly well described on the Internet and both Wolfram and WikiPedia describes the problem. Continue reading →

Posted by Kristian in Math, 2 comments
Project Euler 49: Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other

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

Problem 49 of Project Euler asks us to find three numbers with the following properties

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

What 12-digit number do you form by concatenating the three terms in this sequence?

When I first read the description I misread the description and interpreted it as I had to find a sequence which was 3330 apart. So I solved that problem and arrived with a correct solution. However, I realise this was not what was meant with the problem.  So the solution I will present here is one that looks for any three number sequence with equal distance among two neighbouring terms and having properties (i) and (ii). Continue reading →

Posted by Kristian in Project Euler, 28 comments
McNugget numbers – The Question

McNugget numbers – The Question

This post is about McNugget numbers and a small mental math exercise I gave my self this week while driving on the high way.

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

While waiting in the line I was watching the prices for the many delicious offerings…. And I saw they had McDonald’s Chicken McNuggets in the four quantities 4,6,9 and 20. That’s when I realised that I had bumped into the curious little phenomenon called McNugget numbers at some point and decided I wanted to think this through my self. Continue reading →

Posted by Kristian in Math, 3 comments
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

Problem 48 of Project Euler has the nice and simple description

The series, 11 + 22 + 33 + … + 1010 = 10405071317.

Find 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 →

Posted by Kristian in Project Euler, 14 comments

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?

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 reads

If 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?

Continue reading →

Posted by Kristian in Project Euler, 5 comments