# Arithmetic

## HackerRank: Handshake

Time to shake hands with a lot of people in the next HackerRank challenge called Handshake. The problem reads

At the annual meeting of Board of Directors of Acme Inc, every one starts shaking hands with everyone else in the room. Given the fact that any two persons shake hand exactly once, Can you tell the total count of handshakes?

Input Format
The first line contains the number of test cases T, T lines follow.
Each line then contains an integer N, the total number of Board of Directors of Acme.

Output Format

Print the number of handshakes for each test-case in a new line.

Posted by Kristian in HackerRank, 3 comments

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

Posted by Kristian in Project Euler, 6 comments

## UVa 10055: Hashmat the brave warrior

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 by calculating the difference between the number of Hashmat’s soldiers and the number of his opponent’s soldiers. Continue reading →

Posted by Bjarki Ágúst in UVa Online Judge, 18 comments

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

Posted by Kristian in Project Euler, 4 comments

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

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 →

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

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

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.

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

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