Project Euler 30: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits

Project Euler Problem 30 is an easy problem once you figure out the secret. The problem reads

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

I definitely want to pursue a brute force strategy in C#, but we need an upper bound if we don’t want to continue in eternity. So finding the upper bound is the secret to solving this problem. The rest is straight forward.

So lets determine the upper bound. We need to find a number x95 which gives us an x digit number. We can do this by hand. Since 95 = 59049, we need at least 5 digits. 595 = 295245, so with 5 digits we can make a 6 digit number. 6*95 = 354294. So 355000 seems like a reasonable upper bound to use. We could probably tighten is even further if we wanted. Continue reading →

Posted by Kristian in Project Euler, 14 comments

Project Euler 29: How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Problem 29 of Project Euler reads

Consider all integer combinations of ab for 2 <= a <= 5 and 2 <= b <= 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 <= a <= 100 and 2 <= b <= 100?

It is fairly trivial to realise that the solution is somewhere below 99*99 = 9801, using combinatorics. Based on the amount of possible combinations it should also be fairly easy to implement a brute force solution in C#. That is the first solution we will elaborate on, but I have a pen and paper method as well, where we will use logic to deduce the solution. Continue reading →

Posted by Kristian in Project Euler, 18 comments

History of Numbers: The story of 1

I have found a 1 hour video on the history of the numbers. The video is created by the ex-Monty Python member Terry Jones and was created for the BBC in 2005. I think it is a very humoruos way to introduce some mathematical history, even though I can’t verify the correctness of the history.

It has been aired on television in many countries but I haven’t been able to find it on the web right now.

It gives me something to think about. Even though it seems simple to figure out the number 0, and even though much of the basic mathematics today seems simple, it has been incredibly difficult to invent. One examples is the numbers, we take them for granted today, but seeing in the video how difficult it was to invent a system without limitations to the size of the number you want to write says a lot about how far we have come in mathematics today.

Story of 1The video is available through sources like amazon as well, but only region 1, which means if you are a non us-citizen you may have problems viewing it. The image on the left is linked directly to the Amazon page where you can purchase it and let me earn commission.

On last thing I would like to mention is that several people, especially math teachers on the internet praises the video as being a good tool, so if you are in school maybe give your teacher a hint for something fun to watch and be inspired by.

Enjoy

Posted by Kristian in Other, 0 comments

Project Euler 28: What is the sum of both diagonals in a 1001 by 1001 spiral?

Problem 28 of Project Euler reads

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

I am pretty sure it is possible to brute force a solution for this problem, but the thought of having to construct the spiral, so let instead of that let us attack it from a more analytical approach and search for a function of the ring number. This is done in two steps, first we will derive a formula where the calculation for the n’th ring depends on the n-1’th ring. And after that we will derive a formula which is independent on the previous ring. Continue reading →

Posted by Kristian in Project Euler, 35 comments

Project Euler 27: Find a quadratic formula that produces the maximum number of primes for consecutive values of n

We are back to saying something about primes in Problem 27 of Project Euler. So you may already now want to go back to the solution to Problem 10 for an efficient implementation of Sieve of Eratosthenes since we are likely to need that. The problem reads

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n² – 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

 

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

For me this one reeks of brute force, since it is obvious that we can run through all possible values of a and b. Yes that is 4.000.000 solutions we need to check, but it should be possible. Continue reading →

Posted by Kristian in Project Euler, 34 comments

Course in Linear Algebra by Gilbert Strang

Within the field of mathematics I handle every day linear algebra plays a vital role. Linear algebra is a field of mathematics that studies vectors and vector spaces. On common use of linear algebra is to solve a set of linear equations. Personally I learned it in university using a book by David C. Lay called Linear Algebra and Its Applications. It is a perfectly good book, and I can recommend it if you want to have a book on the topic.

The reason why I bring up the topic, is that I rediscovered a video version a MIT course in linear algebra taught by Gilbert Strang. I found the videos when I first studied to my exam in linear algebra. I think he teaches it in a very understandable manner.  All of the videos can be found at Academic Earth. However, I think that the videos there are poor quality, so I have compiled a list of the videos representing the course in a better quality. Continue reading →

Posted by Kristian in Math, 6 comments

Project Euler 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle

Problem 26 of Project Euler reads

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 =
0.5
1/3 =
0.(3)
1/4 = 0.25
1/5
= 0.2
1/6
= 0.1(6)
1/7
= 0.(142857)
1/8
= 0.125
1/9
= 0.(1)
1/10
= 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

How can be possibly approach this problem. Just doing a division and then analysing the double we get out of it is not likely to give us enough digits to find the solution. Usually when the number representation lacks we can use the BigInteger class, but for once that wont help us. However, I found one possible approach. Instead of actually calculating the fraction, we analyse the remainder on each position. It has the advantage that we work with integers rather than fractions.

Continue reading →

Posted by Kristian in Project Euler, 43 comments

Project Euler 25: What is the first term in the Fibonacci sequence to contain 1000 digits?

Back to the big numbers again in Problem 25 of Project Euler. The problem reads

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12 is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

With the BigInteger class this is rather easy to brute force. So a brute force solution is one of the two solutions I will show you. The other solution is one you can use with a calculator, or if you are good at mental arithmetic, you can do it with pen and paper.

Continue reading →

Posted by Kristian in Project Euler, 20 comments

Project Euler 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Problem 24 of Project Euler is about permutations, which is in the field of combinatorics. The posed question is as follows

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

There is a clever way to solve it, and a brute force solution. Since the brute force algorithm still requires some thought on how to generate permutation, I will cover both methods in this post. Continue reading →

Posted by Kristian in Project Euler, 38 comments

Project Euler 23: Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Problem 23 of Project Euler is about factorisation of a number once again, and has a rather long description. So let me give that to you right away

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

I have only found one effective approach for this problem in C#, there might be more but I haven’t found them. My approach can be summaries in three steps

  1. Find all abundant numbers
  2. Create and mark all number which can be created as the sum of two abundant numbers
  3. Sum up all non-marked numbers

Continue reading →

Posted by Kristian in Project Euler, 23 comments
This site uses cookies.