Wednesday, July 18, 2007

Programming for number theory problems

As I previously mentioned, I am reading A Friendly Introduction to Number Theory by Joseph H. Silverman. I want to highly recommend this book. It was recommended to me by Michael Kaplan from the Math Circle and he is right, this book is very accessible. I am reading chapters 1, 2, and 3 currently.

There are lots of problems that can highlight using the computer to make conjectures.

Some of my posts earlier showed that Excel most likely has an issue with large numbers and that was making me have false leads and results. I'm going to be looking at the following problem using C#.NET or perhaps Java.

This is exercise 1.4 from the book on page 11.
It is generally believed that infinitely many primes have the form N^2 + 1, although no one knows for sure.
(A) Do you think that there are infinitely many primes of the form:
(N^2)-1?
(N^2)-2?
(N^2)-3?
(N^2)-4?
(N^2)-a?

Which values of a do you think give infinitely many primes of the form (N^2)-a?

So, I'm going to move away from excel as I ran into problems. And I'm going to re-look at Conjectures about 3^n-1 and 3^n-2^n using the same problem.

For these problems, I'm just going to get the data output to a file and look at it.

Another problem from the book is 1.1 on page 11.
The first two numbers that are both squares and triangles are 1 and 36. Find the next one and, if possible, the one after that. Can you figure out an efficient way to find traingular-square numbers? Do you think there are infinitly many?

Here is some background to understand this problem:
Square numbers are (1,4,8,...) :
1^2 = 1
2^2 = 4
3^2 = 8
....

Traingular numbers are (1,3,6,10,...)
1
1+2 = 3
1+2+3 = 6
1+2+3+4 = 10

triangular numbers get their name from the design:
1 =
.

3 =
.
. .

6 =
.
. .
. . .

and if you understnd the pattern, you can see that the next row would be 4 dots

Well, for this problem, I am also going to write a computer program. However, this one will compare two lists that I will create. I try to create a list of 1000 triangular numbers and 1000 square numbers. Then I will compare them.

SO, this brings up some computer science questions.
1) What algorithm is the most efficient for comparing two lists of 1000 numbers each?
2) What data structure is the best to hold these lists in java or C#.NET?
3) What language is best for this sort of a thing? C#, java, python, maple?

I will be thinking about these things over the next week and I'll report back. If anyone has any ideas or comments, please post!