Modulo

HackerRank: Connecting Towns

HackerRank: Connecting Towns

Welcome to the Shire… Well at least welcome to Middle Earth, we don’t actually need to travel through the shire in the next HackerRank problem with Connecting Towns. The problem reads

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T1) to Rivendell (Tn).

But there are towns T2,T3,T4…Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Note
Gandalf has to pass all the towns Ti for i=1 to n-1 in numerical order to reach Tn.
For each Ti , Ti+1 there are only Ni distinct routes Gandalf can take.

Input Format
The first line contains an integer T, T test-cases follow.
Each test-case has 2 lines. The first line contains an integer N (the number of towns).
The second line contains N – 1 space separated integers where the ith integer denotes the number of routes, Ni, from the town Ti to Ti+1

Output Format
Total number of routes from T1 to Tn modulo 1234567
http://en.wikipedia.org/wiki/Modular_arithmetic

Solving the math of Connecting Towns

There are two things we need to get our heads around. There is the first part which is how many paths there are, and then there is the second part of the modulo.

The former problem of the paths is rather simple as it is a simple combinatorics problem and the total number of paths are just the product of the paths of each leg of the journey

The problem of the modulo operator can be treated in different ways. Since we are using Python as implementation language we can completely ignore it, as it can handle arbitrarily large integers. However, we can also solve it as we have done for Project Euler problem 48.

In general we have the formula

Which means that for every time we multiply with the next set of paths we can also take the modulo, which means we will keep the total size of the integer down significantly.  If it actually matters in Python I don’t know.

Implementing Connecting towns in Python

Let us implement the one with modulo arithmetic. However since we know that both a and b in the previous formula will be smaller than the modulo. Therefore a%c = a and b%c= b, so we only need to take modulo of the result during the iterations. Therefore the function we need to implement is

def connectingTowns(n, routes):
    paths = 1
    for i in routes:
        paths = (paths * i) % 1234567
    return paths

and that should solve the problem.

Posted by Kristian in HackerRank, 0 comments
Project Euler 146: Investigating a Prime Pattern

Project Euler 146: Investigating a Prime Pattern

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 I thought I could just make a sieve up to 150 million and then check if the numbers were contained in that. However, rereading the problem I realized I was completely wrong. So in a pure brute force solution we would need to check 150 million values of n and up to 13 numbers for each, since we both need to check that the given numbers are prime. But also that the odd numbers inbetween are not prime. So potentially we have to check 1950 million numbers for primality, which is a moderately expensive operation. Continue reading →

Posted by Kristian in Project Euler, 7 comments
Project Euler 134: Prime pair connection

Project Euler 134: Prime pair connection

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 reads

Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.

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

Continue reading →

Posted by Kristian in Project Euler, 5 comments
Project Euler 133: Repunit nonfactors

Project Euler 133: Repunit nonfactors

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 reads

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

Let us consider repunits of the form R(10n).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10n) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10n).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).

Continue reading →

Posted by Kristian in Project Euler, 6 comments
Project Euler 132: Large repunit factors

Project Euler 132: Large repunit factors

In problem 132 of Project Euler we are going back to working with repunits in a problem that reads

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k.

For example, R(10) = 1111111111 = 11 x 41 x 271 x 9091, and the sum of these prime factors is 9414.

Find the sum of the first forty prime factors of R(109).

Continue reading →

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

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

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 reads

A 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 by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

You are given that for all primes, p > 5, that p – 1 is divisible by A(p). For example, when p = 41, A(41) = 5, and 40 is divisible by 5.

However, there are rare composite values for which this is also true; the first five examples being 91, 259, 451, 481, and 703.

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

Continue reading →

Posted by Kristian in Project Euler, 3 comments
Project Euler 129: Investigating minimal repunits that divide by n.

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

Problem 129 of Project Euler reads

A 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 k; for example, A(7) = 6 and A(41) = 5.

The least value of n for which A(n) first exceeds ten is 17.

Find the least value of n for which A(n) first exceeds one-million.

Continue reading →

Posted by Kristian in Project Euler, 7 comments
Project Euler 123: Determining the remainder when (pn − 1)^n + (pn + 1)^n is divided by pn^2

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

Problem 123 of Project Euler reads

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

For example, when n = 3, p3 = 5, and 43 + 63 = 280 ≡ 5 mod 25.

The least value of n for which the remainder first exceeds 109 is 7037.

Find the least value of n for which the remainder first exceeds 1010.

Continue reading →

Posted by Kristian in Project Euler, 7 comments
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
UVa 10127: Ones

UVa 10127: Ones

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. More specifically, we are asked for the number of ones in that multiple.

Interpretation

We are given an integer that is neither divisible by nor . We have to find the smallest multiple of that consists entirely of ones. For example, when , is the smallest multiple of that consists only of ones. For this problem, we only need the digit count of that multiple, which in the case of is (because  has digits). Continue reading →

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