Sequences

HackerRank: Handshake

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.

Continue reading →

Posted by Kristian in HackerRank, 3 comments
Project Euler 137: Fibonacci golden nuggets

Project Euler 137: Fibonacci golden nuggets

I think that Problem 137 of Project Euler is a really fantastic problem since it has so many facets of how it can be solved. I will go through a one of them, and then link to a few other. The problem reads

Consider the infinite polynomial series AF(x) = xF1 + x2F2 + x3F3 + …, where Fk is the kth term in the Fibonacci sequence: 1, 1, 2, 3, 5, 8, … ; that is, Fk = Fk-1 + Fk-2, F1 = 1 and F2 = 1.

For this problem we shall be interested in values of x for which AF(x) is a positive integer.

Surprisingly AF(1/2)  =  (1/2).1 + (1/2)2.1 + (1/2)3.2 + (1/2)4.3 + (1/2)5.5 + …
   =  1/2 + 1/4 + 2/8 + 3/16 + 5/32 + …
   =  2

The corresponding values of x for the first five natural numbers are shown below.

x AF(x)
√2-1 1
1/2 2
(√13-2)/3 3
(√89-5)/8 4
(√34-3)/5 5

We shall call AF(x) a golden nugget if x is rational, because they become increasingly rarer; for example, the 10th golden nugget is 74049690.

Find the 15th golden nugget.

Continue reading →

Posted by Kristian in Project Euler, 7 comments
Project Euler 73: How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Project Euler 73: How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Problem 73 of Project Euler is the third problem in a row which treats ordering proper fractions. The problem description 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 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

Note: The upper limit has been changed recently.

Continue reading →

Posted by Kristian in Project Euler, 12 comments
Project Euler 57: Investigate the expansion of the continued fraction for the square root of two.

Project Euler 57: Investigate the expansion of the continued fraction for the square root of two.

I found Problem 57 of Project Euler to be a rather interesting problem, with more than one solution. The problem description reads

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

First thing I will present is a brute force solution, which for all practical purposes are fast enough. The second solution is a closed form approximation to the problem, so it can be solved as fast as you can punch the calculator. Continue reading →

Posted by Kristian in Project Euler, 15 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