MATHS BITE: Sierpinski Number

A Sierpinski number is an odd natural number k such that {\displaystyle k\times 2^{n}+1} is not prime for all natural numbers n. In 1960, Sierpinski proved that there are infinitely many odd integers k with this property, but failed to give an example. Numbers in such a set with odd k and k < 2^n are called Proth numbers.

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909,….

-List of some known Sierpinski Numbers

Sierpinski Problem

The Sierpinski problem asks what the smallest Sierpinski number is. In 1967, Sierpinski and Selfridge conjectured that 78557 is the smallest Sierpinski number. To show this is true, we need to show that all the odd numbers smaller than 78557 are not Sierpinski numbers, i.e. for every odd k below 78557 there is a positive interger n such that {\displaystyle k\times 2^{n}+1} is prime. There are only five numbers which have not been eliminated:

k = 21181, 22699, 24737, 55459, and 67607

Numberphile Video

Find out more here. M x

Advertisements

Waring’s Problem

Statement:

Take any whole number k that is greater than or equal to 2.  Show that there is some number s (that is allowed to depend on k) so that every positive whole number is a sum of s kth powers.

Proof

This problem was first solved by David Hilbert, and was then later proved by G.H. Hardy and John Littlewood in a different way. In this case, the second proof actually gave a lot more insight to the problem. To solve Waring’s problem as it has been stated you don’t need to give an s, you only need to show that one exists.  Finding the smallest s that works is a much more challenging (although arguably more interesting) problem. Using the, now named, Hardy-Littlewood circle method, Hardy and Littlewood wrote down an expression that approximated the number of ways to write N as a sum of s kth powers:

latex.png

The proof of Waring’s problem comes from that fact that since this must be positive and also be a whole number, there must be some way to write N as a sum of s kth powers.

Click here for more.

M x

(Sorry for missing a post last week, my university work is getting a bit hectic so posts may be more sporadic!)

How to Solve It

In 1945, Hungarian mathematician George Pólya wrote an extremely successful book called How to Solve It, which sold over one million copies and has been translated into 17 languages. In this book, Pólya identifies the four basic principles of problem solving.

1. Understand the Problem

Firstly, you must understand the problem you are tackling.  Although this may seem like common sense, it is often overlooked; the amount of times I’ve been staring at a problem for hours because I haven’t fully understood what it is asking! Consider asking the following questions:

  • What is the unknown? What are the data? What is the condition?
  • What are you asked to find or show?
  • Can you restate the problem in your own words?
  • Do you understand all the words used in stating the problem?

For some areas in maths, such as mechanics, drawing a labelled figure can often be extremely helpful to visualise what is going on.

Resultado de imagem para free body diagram
Example of Diagram

2. Devise a Plan

There are many different suitable ways to solve a problem, as mentioned by Pólya. However, it is important to choose an appropriate strategy, which is a skill learnt by solving many problems. Some strategies include:

  • Guess and check
  • Use symmetry
  • Consider special cases
  • Solve an equation or use a formula
  • Look for a pattern
  • Solve a simpler problem
  • Work backwards
  • Eliminate possibilities

When choosing a strategy, it may help to consider whether you have solved a related problem already or whether you can think of a familiar problem that has the same or similar unknown.


3. Carry out the Plan

Once you have devised the plan, this step is simple if you already have the necessary skills, often only required care and patience -try to avoid silly mistakes!

Persist with the plan that you have chosen, only discarding it after multiple failed attempts. Then, return to step 2.

4. Look back

Pólya highlights how a lot can be gained from looking back and reflecting on the work you have done, asking yourself what worked and what didn’t. This way you can implement strategies that were successful for future problems that are similar.


Read more here.

M x

VIDEO: Napkin Ring Problem

If you were to core a sphere (remove a cylinder from it), you are left with a shape that looks like a napkin ring. This is a “bizarre” shape, as if you have two napkin rings with the same height, they will have the same volume regardless of the size of the initial spheres that they came from. How do you prove this?

Here’s a few hints to try and solve it yourself before watching the Vsauce video below which reveals the answer:

  • There are a few variables that need to be found: the height of the napkin ring, the radius of the starting sphere and the radius of the cylinder. Using these variables you can find a volume equation.
  • You don’t need to find the volume of the whole napkin ring in one go. This is because, as the two napkin rings have to be the same height, it’s enough to show that any slice of the napkin rings has to have the same area. If every pair of slices has the same area, then the napkin rings have the same volume.

Solution:

M x

Kakeya Needle Problem

The Kakeya needle problem asks whether there is a minimum area of a region in the plane in which a line segment of width 1 can be freely rotated through 360°, where translation of the segment is allowed.

This question was first posed for convex regions in 1917 by mathematician Sōichi Kakeya. It was shown by Gyula Pál that the minimum area for convex regions is achieved by an equilateral triangle of height 1 and area 1/√3.

Kakeya suggested that the minimum area, without the convexity restriction, would be a three-pointed deltoid shape. However, this is false.

Needle rotating inside a deltoid | Source: Wikipedia

Besicovitch Sets

Besicovitch was able to show that there is no lower bound >0 for the area of a region in which a needle of unit length can be turned around. The proof of this relies on the construction of what is now known as a Besicovitch set, which is a set of measure zero in the plane which contains a unit line segment in every direction.

One can construct a set in which a unit line segment can be rotated continuously through 180 degrees from a Besicovitch set consisting of Perron trees.

Kakeya Needle Set constructed from Perron trees | Source: Wikipedia

However, although there are Kakeya needle sets of arbitrarily small positive measure and Besicovich sets of measure 0, there are no Kakeya needle sets of measure 0.

Video: Numberphile

M x

The Josephus Problem

The Josephus Problem is a problem in computer science based on a counting-out game. The problem is named after Flavius Josephus, a Jewish-Roman historian from the 1st century, who tells the story like this:

“A company of 40 soldiers, along with Josephus himself, were trapped in a cave by Roman soldiers during the Siege of Yodfat in 67 A.D. The Jewish soldiers chose to die rather than surrender, so they devised a system to kill off each other until only one person remained. (That last person would be the only one required to die by their own hand.)

All 41 people stood in a circle. The first soldier killed the man to his left, the next surviving soldier killed the man to his left, and so on. Josephus was among the last two men standing, “whether we must say it happened so by chance, or whether by the providence of God,” and he convinced the other survivor to surrender rather than die.”

This story gives rise to an interesting maths problem: If you’re in a similar situation to Josephus, how do you know where to stand so you will be the last man standing?

M x

The Halting Problem

To understand the process of computation, regardless of the technology available, we need to reduce it to its most basic elements. One way to model computation is to consider an input, operated on by a program which produces some output.

In 1936, Alan Turing constructed such a model and considered the question of determining whether a program will finish running or will continue to run forever i.e. halt. This is known as the Halting Problem.

Let us suppose that we write a program, let’s call it HALT, that, given another program and its associated input, can determine whether running that program with the input will halt or not. This can be represented in the following way:

\[  \mbox{\textbf{HALT}(program,input)}=\left\{  \begin{tabular}{l}\mbox{Output YES, if the program does halt on the input,}

\\ \mbox{Output NO, otherwise. } 

\end{tabular}  \]

Note that we do not have to consider how this program works, it is merely sufficient to assume that there does exist such a program. Now, consider a new program, call it OPPOSITE which does the opposite of halt. In other words, it analyses programs running with themselves as the input, acting in the following way:

\[  \mbox{\textbf{OPPOSITE}(program)}=\left\{  \begin{tabular}{l}\mbox{Halt, if \textbf{HALT}(program, program) returns NO, }

\\ \mbox{Loop forever, otherwise. } 

\end{tabular}  \]

Now, what happens when we run OPPOSITE on itself?

If OPPOSITE(opposite) halts, then it must loop forever, but if it loops forever then it must halt. Hence, there is a contradiction, highlighting how the program HALT cannot exist.

This was an incredible result. Firstly, in this proof a computer and a program were mathematically defined, paving the way to the creation of the Turing Machines. Furthermore, Turing had found a program whose existence is logically impossible, and showed that knowing whether a program halts on some input is undecidable.

“It is one of the first examples of a decision problem.”

I have included a video by Computerphile which I think describes the problem and proof very well:

M x