Prime numbers

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 77: What is the first value which can be written as the sum of primes in over five thousand different ways?

Project Euler 77: What is the first value which can be written as the sum of primes in over five thousand different ways?

In problem 77 of Project Euler we are asked the following question

 

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

Continue reading →

Posted by Kristian in Project Euler, 6 comments
Project Euler 70: Investigate values of n for which φ(n) is a permutation of n.

Project Euler 70: Investigate values of n for which φ(n) is a permutation of n.

For this problem I have taken a bit of a lazy approach with the coding and not emptied the search space, but just searched where we are most likely to find a solution. However, there are several tricks we can use when we try to find a solution. However, before babbling on, here is the problem we want to solve

Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

Looks familiar? Well, the phi function is the same function as we looked at previously. Continue reading →

Posted by Kristian in Project Euler, 12 comments
This week’s links

This week’s links

I have a few links for you this week that I have chewed through and found interesting. First I found a few papers that I think are really nice recreational mathematics

A paper titled The Prime Facts: From Euclid to AKS which is going through different aspects of prime numbers and not least their importance in public key encryption. Something which the society relies heavily on today. Continue reading →

Posted by Kristian in Other, 0 comments
Project Euler 60: Find a set of five primes for which any two primes concatenate to produce another prime.

Project Euler 60: Find a set of five primes for which any two primes concatenate to produce another prime.

This problem caused me quite a lot of trouble, and from what I gather afterwards no one seems to have found a really nice solution for this. The problem reads

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

I found two ways to approach this a brute force method and a method involving intersecting sets. After a bit of optimization they are about the same speed. Continue reading →

Posted by Kristian in Project Euler, 17 comments
Project Euler 58: Investigate the number of primes that lie on the diagonals of the spiral grid

Project Euler 58: Investigate the number of primes that lie on the diagonals of the spiral grid

In Problem 58 of Project Euler we are revisiting the spiral we worked on in Problem 28. I have since then learned that it is called an Ulam spiral after the Polish born American mathematician Stanislaw Ulam. The problem reads:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13  62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Continue reading →

Posted by Kristian in Project Euler, 9 comments
Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics

Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics

I have just finished reading Prime Obsession by John Derbyshire. A casual math book  which I will pass my thoughts and recommendations about this book in this post.


Prime Obsession is a book about the history surrounding Bernhard Riemann and the Riemann Hypothesis. A hypothesis, which is more than 150 years, and still haven’t been neither proved nor falsified. The Riemann Hypothesis tells us a lot about the Riemann zeta function and how it is linked to the distribution of  primes. This link is the turning point for the whole book.

When I first encountered the book I did not like the writing style of John Derbyshire to be honest. It was in a very conversational tone. But as I progressed through the book I partly forgot about the writing style. More importantly; the content was so great that the writing style for unimportant to me.

The book covers two aspects of the Riemann hypothesis. The even chapters (oh, the author is a mathematician after all – so why not) gives the reader a historical account about European mathematics. They cover many things from a few generations before Riemann all the way to today. I loved these chapters which introduced me to a lot of the persons naming the famous theorems that we are using today such as Gauss, Euler and of course Riemann himself.

The remaining chapters (the odd ones) covers a wide range of mathematical topics. The culmination is the explanation of the Riemann hypothesis and how the non trivial zeros of the zeta function links to the distribution of the primes. Most of the chapters were written in what I would consider being an accessible way which gives a fine introduction to the mathematical topics. It is by no means a textbook that will give you the deeper understanding of the subjects it touches, but it gives you an introduction and tells you what the idea of the subject is.

The only part I didn’t grasp was a chapter on field theory, I thought it lacked something. However, it wasn’t that essential for the main result I think. The main result was a bit complicated to understand as well, but reading the last two odd chapters again helped a lot. I wont say I understand the Riemann hypothesis in the mathematical sense, but I have a conceptual idea of what it does. So this book delivered exactly what it promised to do. Besides that it also inspired me to continue the wonderful journey through mathematics.

If you haven’t read it yet, this is an obvious choice for an item on the wish list.

Posted by Kristian in Other, 2 comments
Project Euler 51: Find the smallest prime which, by changing the same part of the number, can form eight different primes

Project Euler 51: Find the smallest prime which, by changing the same part of the number, can form eight different primes

When I worked on this problem I realised that I value two things about code – speed and simplicity. I always try to obtain both but in this case I had to sacrifice the simplicity in order to gain speed as we shall see. But before we dive into the code lets look at Problem 51 which is the problem description for the first problem on the second page of Project Euler. It reads

By replacing the 1st digit of *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

This problem can be solved in multiple ways.  You could run your way through all primes and check if each one is part of a family or you could do a bit of analysis on the problem to narrow down the problem you have to solve by code. I have chosen the latter. Continue reading →

Posted by Kristian in Project Euler, 21 comments
Project Euler 50: Which prime, below one-million, can be written as the sum of the most consecutive primes?

Project Euler 50: Which prime, below one-million, can be written as the sum of the most consecutive primes?

We have now reached the bottom of the first page of the Project Euler problems. Problem 50 is all about primes as we are supposed to use primes to generate a new prime. The problem reads

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Unless we do something to avoid it we would have a lot of numbers to search through. Continue reading →

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