Tag Archives: Yuri Matiyasevich

Ulam Spiral

Standard

Some of you may know what Ulam’s spiral is (I am not describing what it is because the present Wikipedia entry is awesome, though I mentioned it earlier also). When I first read about it, I thought that it is just a coincidence and is a useless observation. But a few days ago while reading an article by Yuri Matiyasevich, I came to know about the importance of this observation. (Though just now I realised that Wikipedia article describes is clearly, so in this post I just want to re-write that idea.)

It’s an open problem in number theory to find a non-linear, non-constant polynomial which can take prime values infinitely many times. There are some conjectures about the conditions to be satisfied by such polynomials but very little progress has been made in this direction. This is a place where Ulam’s spiral raises some hope. In Ulam spiral, the prime numbers tend to create longish chain formations along the diagonals. And the numbers on some diagonals represent the values of some quadratic polynomial with integer coefficients.

ulam_spiral_by_splatbang-d5b0yfj

Ulam spiral consists of the numbers between 1 and 400, in a square spiral. All the prime numbers are highlighted. ( Ulam Spiral by SplatBang)

Surprisingly, this pattern continues for large numbers. A point to be noted is that this pattern is a feature of spirals not necessarily begin with 1. For examples, the values of the polynomial x^2+x+41 form a diagonal pattern on a spiral beginning with 41.

 

Advertisements

Numbers and Logic

Standard

I am a big fan of number theory. I find the answer to Hilbert’s Tenth Problem fascinating. I was introduced to this problem, a couple of years ago, via the documentary titled : “Julia Robinson and Hilbert’s Tenth Problem“, here is the trailer:

 

You can read more about it here. Also for the sake of completeness, let me state Hilbert’s Tenth Problem:

Does there exist an algorithm to determine whether a given Diophantine equation has a solution in rational integers?

In 1970, Yuri Matiyasevich completed the solution of this problem by using the concept of Turing Machine. This short video provides a nice overview about Turing Machines in general

The answer to Hilbert’s Tenth Problem problem is

No such algorithm exists.

This interplay of number theory and logic is really interesting, isn’t it? But I can’t discuss solution of Hilbert’s Tenth Problem here, since I have never read it. But there is nice overview at Wikipedia.

I will rather discuss a puzzle from Boris A. Kordemsky’s book which illustrates the idea of this interplay.

Ask a friend to pick a number from 1 through 1000. After asking him/her ten questions that can be answered yes or no, you tell him/her the number. What kind of question?

The key to the solution is that 2 to the tenth power is 1024 (that is, over 1000). With each question you knock out half the remaining numbers, and after ten questions only the thought number is left.

I welcome you to think of a number and write the corresponding yes/no questions as a comment below.