Baby Steps: The Basics

1. Elementary Number Theory

1.1. Arithmetic Tables

Generating addition tables modulo {n}

Example: {(\mathbb{Z}_7,+)}

\displaystyle \begin{array}{c c c c c c c} 0 & 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 2 & 3 & 4 & 5 & 6 & 0\\ 2 & 3 & 4 & 5 & 6 & 0 & 1 \\ 3 & 4 & 5 & 6 & 0 & 1 & 2 \\ 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ 5 & 6 & 0 & 1 & 2 & 3 & 4\\ 6 & 0 & 1 & 2 & 3 & 4 & 5\\\end{array}

{\mathbb{Z}} forms a group under addition ({\mathbb{Z}},+).

For a set with a defined operation, the Group axioms are: Closure and existence of identity and inverse. {n\mathbb{Z}} is a subset of {\mathbb{Z}} (all elements multiplied by n). The subset {n\mathbb{Z}} is a subgroup: closed under addition, associative; additive inverse, and identity belong to {n\mathbb{Z}}. The group of integers modulo n  denoted \mathbb{Z}/n\mathbb{Z}  also form a group under addition.

Monoids exclude the requirement of the existence of inverse, so {\mathbb{N}} is a submonoid of {\mathbb{Z}}. A coset of a subgroup is a translation of the subgroup by an element of the group. The subsets {\{n\mathbb{Z}+1,\cdots,n\mathbb{Z}+(n-1)\}}, i.e all the residue classes modulo n are cosets of the subgroup {n\mathbb{Z}}

Multiplication table modulo{7}

\displaystyle [\begin{array}{c c c c c c c} 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 & 4 & 5 & 6\\ 0 & 2 & 4 & 6 & 1 & 3 & 5\\ 0 & 3 & 6 & 2 & 5 & 1 & 4\\ 0 & 4 & 1 & 5 & 2 & 6 & 3\\ 0 & 5 & 3 & 1 & 6 & 4 & 2 \\ 0 & 6 & 5 & 4 & 3 & 2 & 1\end{array}

C++ code

#include<iostream.h>
#include<stdio.h>
#include<math.h>

void addition_table()
{
int k,a;
cout<<"Enter X to generate (Z_X,+)"<<endl;
cin>>k; cout<<"\n";
for(int i=0;i<k;i++)
        {
        cout<<endl;

        for(int j=0;j<k;j++)
                {
                        a=(i+j)%k; // a=(i*j)%k; for multiplication table
                        cout<<a<<'\t';
                }
        }

}

1.2. Division Algorithm

Given two inputs, any integer {a} and a positive integer {b} it is needed to find two integers {q} and {0\leq r< b} such that {a = bq+r}. It is clear that if {b>a} then {q=0} and {r=a}. If {b<a} then the formal proof follows from the well-rdering principle (every nonempty set in {\mathbb{N}}) has a least element by constructing the set {k=\{ a-bq: k\in\mathbb{N}\}} SInce we’ve constrained k and it is non empty therefore it must have a least element which we call {r}. In other words, we choose {q} such that {a-bq} is the smallest possiple positive integer (or zero). So

\displaystyle a-b(q+1)<0\leq a-bq

\displaystyle \Rightarrow 0\leq r=a-bq<b

The Euclidean algorithm to find the gcd of two numbers is a consequence of the fact that {b = aq+r}, then {d=} gcd{(a,b)=} gcd{(a,r)}. As {r = b-aq} then all common divisors of {a} and {b} are also divisors of {r}, i.e {r|d}. Also, as {d|b} and {b = aq+r} so {d|r}. Two positive integers that divide each other are equal.

Following is an implementation of the Euclidean Algorithm. Negative integeres would cause it to go in an infinite loop so I’ve added some lines.


include&lt;iostream.h&gt;

int euclidean(int a, int b)
{
int a,b;
a = a&gt;0 ? a : -a;
b = b&gt;0 ? b : -b;
do{
a = a&gt;b &amp;&amp; a!=b ? a-b : a;
b = b&gt;a &amp;&amp; b!=a ? b-a : b;
cout&lt;&lt;&quot;{&quot;&lt;&lt;a&lt;&lt;&quot;,&quot;&lt;&lt;b&lt;&lt;&quot;}-&gt;&quot;;
}while(a!=b);
cout&lt;&lt;&quot;\n GCD=&quot;&lt;&lt;a&lt;&lt;endl;
}

Output
root [5] euclidean(343423,6268768)

{343423,5925345}->{343423,5581922}->{343423,5238499}->{343423,4895076}->{343423,4551653}-> {343423,4208230}->{343423,3864807}->{343423,3521384}->{343423,3177961}->{343423,2834538}-> {343423,2491115}->{343423,2147692}->{343423,1804269}->{343423,1460846}->{343423,1117423}-> {343423,774000}->{343423,430577}->{343423,87154}->{256269,87154}->{169115,87154}-> {81961,5193}->{76768,5193}->{71575,5193}->{66382,5193}->{61189,5193}->{55996,5193}-> {50803,5193}->{45610,5193}->{40417,5193}->{35224,5193}->{30031,5193}->{24838,5193}-> {19645,5193}->{14452,5193}->{9259,5193}->{4066,1127}->{2939,1127}->{1812,1127}-> {685,442}->{243,199}->{44,155}->{44,111}->{44,67}->{44,23}->{21,2}->{19,2}->{17,2}-> {15,2}->{13,2}->{11,2}->{9,2}->{7,2}->{5,2}->{3,2}->{1,1}-> GCD=1

The GCD of two numbers is also their smallest integral linear combination.

This is fairly straighforward. Consider {3=gcd(57,36)}, i.e {3|57} and {3|36} so {3|57x+36y} As {3} is the greatest number which can divide the expression, i.e leave an integer, for arbitrary {x,y\in\mathbb{Z}} the above property follows.

More formally, it can be proved using the well ordering principle. Consider the set of all positive integers {D=\{ ax+by:ax+by>0 \}} By the well ordering principle {D} has a least element {d}. Any common divisor {a} and {b} is also a divisor of {d}. It would be sufficient to show that {d} also divides {a} and {b}. Let the remainder on dividing {a} be {r}, i.e

\displaystyle a = dq+r \; ; 0\leq r<d

But then

\displaystyle r = a(1-qx) + b(-qy) \; \mbox{i.e} \; r\in D

Which cannot be as {d} is the least element and hence {r=0}

The set of numbers {S =\{ ax+by|x,y\in \mathbb{Z}\} } form a subgroup of {(\mathbb{Z},+)}. It staisfies all the group axioms. From the above I know that {S} has a least element, {d=}gcd{(a,b)}. Every multiple of {d} is {S}, as {nd = a(nx)+b(ny)} {\forall n\in Z}. Since {d|a} and {d|b} therefore {d} divides all elements of {S}, i.e every member of {S} is a multiple of this number. The subgroup {S} of {(\mathbb{Z},+)} that is generated by non zero integers {a} and {b} is generated by the single number {d}. (If any number {c} in the subgroup such that {c\neq dq} and {c=dq+r} for {0\leq r<d} then {r = c-dq} must be in the subgroup by defintiion, but is lesser than {d} arriving at a contradiction.) \linebreak

Example: we know that {2x+3y = 1} has integer solutions, while for example, {2x+3y=0} has none. If {2a+3b=1} and {2c+3d = 1} then {2(a-c) = 3(d-b)}. As {d-b} must be even, we can write {a=c+3t} and {b=d-2t}. Take one pair of solutions, {c=5} and {d=-3} the other solutions have the form {x=5+3t} and {y =-3-2t }. There are others possible. \linebreak

Example: All consecutive fibbonaci numbers are coprime. {gcd(a_{n+1},a_n) = gcd(a_{n+1}-a_n,a_n) = gcd(a_{n-1},a_n)=\cdots gcd(1,1)} Thus, their gcd is {1}. Proved. \linebreak

In general, the subgroup {\{ax+by+cz+\cdots | x,y,z\cdots \in \mathbb{Z}\}} is a cyclic group generated by the single element gcd{(a,b,c,\cdots)}

1.3. Generating number system using the division algorithm

Theorem 1 Let {b\geq 2,\in\mathbb{Z}} Then every positive integer {N} can be expressed uniquely in the form {N=a_kb^k+a_{k-1}b^{k-1}+ \cdots +a_1 b+a_0 } where {0\leq a_0,a_1,\cdots,a_k<b} and {a_k\neq 0}

Proof:Any number {N} can be written as

\displaystyle N = q_0 b +a_0

with {q\geq 0} and {0\leq a_0 <b}

\displaystyle q_0 = bq_1 +a_1

\displaystyle q_1 = bq_2 +a_2

\displaystyle \cdots

\displaystyle q_{k-1} = 0b + a_{k}

As {N>q_0>q_1>\cdots} and all {q}‘s are positive integers, this sequence will terminate. On substituting

\displaystyle N=q_0 b +a_0 = ( bq_1 +a_1) b +a_0 =( b(bq_2 +a_2)+a_1) b +a_0

\displaystyle = q_{k-1}b^k + a_{k-1}b^{k-1}+\cdots+ a_1b + a_0

\displaystyle = a_kb^k + a_{k-1}b^{k-1}+\cdots+ a_1b + a_0

It can be easily be proved that this is unique. \Box

1.4. Continued Fractions from the division algorithm

 

1.5. Prime Factorization

Fundamental theorem of arithemtic: every integer greater than can be expressed as product of powers of primes. This factorization is unique up to a permutation.

If a number n is composite, atleast on of its prime factors is \leq\lfloor \sqrt{n} \rfloor For example any composite number less than 101 would have either 2,3 or 5 as one of its prime factors. This considerably reduces the number of operations in a brute force method to find primes called the Sieve of Eratosthenes.

See: Primality Testing

1.6. Congruences and Modular Arithmetic

 

1.7. Well Ordering Principle and induction

To be honest, I am still of doubt that the formal process of writing proofs might not be as fruitful for me. It requires me to lose a bit of my intuition and then regain it with a solid understanding of the underlying machinery. With a bit of scepticism, this is a section on the very basics.

\texbf{Well Ordering Principle} \fbox{Every non empty set of positive integers has a least element}

There is no positive integer between {0} and {1}. Suppose {S=\{n\in\mathbb{Z}|0<n<1\}} is a nonempty set, so by the well ordering principle it should have a least element. Let {l} be the least element, but then {0<l^2<l<1} so we arrive at a contradiction.

There is no positive integer between {a} and {a+1}. Let {a<n<a+1} then {0<n-a<1} implying there is an integer between {0} and {1}.

An extension of the WOP to non negative integers can be made using “proof by cases”.

\displaystyle \begin{array}{|c| c c c|}\hline & g^{0} & g^{1} & g^{2}\\\hline g^{0} & g^{0} & g^{1} & g^{2}\\ g^{1} & g^{1} & g^{2} & g^{0}\\ g^{2} & g^{2} & g^{0} & g^{1} \\\hline \end{array}

Day 2 Problem 2. Today has been a semi productive day and I am excited to get back to other reading as soon as Im done with this. The problem seems simple enough, and at the face of it, I can tell I can do a brute force and a recursion. Hmm. Although I am tempted to move straight to making a recursion code, I think Ill make the brute force one just for the heck of it. euler2.cpp

#include<iostream>
using namespace std;

int fiblast(int a[]);
int main()
{
        int s=2,k=0,a[3]={1,2,0};

while(k<4000000){
        if(k%2==0) s+=k;
        k=fiblast(a);
}
cout<<s<<endl;
return 0;
}

int fiblast(int a[]){
a[2]=a[0]+a[1];
a[0]=a[1];
a[1]=a[2];
return a[1];
}



Done. Now to think if a recursive solution can exist. Hmm. First, I cannot help but think how deplorably inefficient my earlier program is. Why the hell am I passing bulky arrays to a function which is going to be called many many times? I feel I can do a better job with three variables in the main function itself. Ok. Try 2 at brute force, basically the same algorithm but a better implementation.


#include<iostream>
using namespace std;

int main()
{
int a1=1,a2=2,a3=0;
while(a2<3009){
        if (a2 % 2==0)a3+=a2;
        a2=a1+a2;
        a1=a2-a1;
if(a2%2==0)cout<<"a2="<<a2<<endl;
}return 0;
}

Perfect. Well… in the sense of improvement, atleast. Now. Time to find a better solution. Hmm. After making some of the sequence, an obvious pattern is emerging. Starting from {2} ever {3^{rd}} number is even. This is so because the sum of odd and even is odd, and the sum of two odds is even. First let me just write the program, I will analyze the recursion itself later to see if there is a closed form, though I should expect one as it is a linear recursion

\displaystyle T_n=T_{n-1}+T_{n-2}

with {T_1 =1} and {T_2=2}

#include<iostream>
using namespace std;

int fib(int z);
int main(){
int s=0,k=0,l=1;
for(int i=2;k<4000000;i+=3)
{s+=k;k=fib(i);}
cout<<s<<endl;
return 0;}

int fib(int i){
if(i==1) return 1;
if(i==2) return 2;
return fib(i-1)+fib(i-2);
}

Well. That’s done.Though I am not sure yet if this is a better solution than the earlier one. I remember a recursive function creates a copy of itself and stores it in memory each time its called. Hmm. Ill make the comparision after I’m done with the closed form as it has begun to bug me and this has taken more time than I expected.

Note to self: Start Euler problems early morning before starting work.

The most efficient code for this problem would be to make the computer do just one computation by figuring out the closed form yourself.

im looking for a closed form for

\displaystyle  S=\sum_{k=1}^{T_{3k-1} < 4M} T_{3k-1} \ \ \ \ \ (1)

Where {T_k} is the k’th Fibbonaci number. {T_0=1}, {T_1=1} being the base cases.This sum should wait. Take the general sum S_n = T_0+ &T_1+ T_2 +\cdots + T_n
S_{n-1} =\qquad &T_0 + T_1+\cdots +T_{n-1}

On adding the above two equations, we get the recursion for the sums:

S_n+S_{n-1} &= T_0 + (T_2+T_3+\cdots + T_{n+1}) = S_{n+1} – T_1
S_n+S_{n-1} &= S_{n+1} – 1

So this is the recursion relation that needs to reduced to a close form. This is, as the Fibonaci terms, a second order recurrence. How should I have seen that earlier? Hmm. Ahh, of course, uptil now there is no reference to any particular sequence, so I can deduce that the sum of terms defined by a second order recurrence will have second order recursive defintions themselves.

My first attack would be to use generating functions:

\displaystyle  S(x) = \sum_{n=0}^\infty S_n x^n \ \ \ \ \ (2)

In some domain x where the power series is convergent.

S(x) &= S_0+S_1 x+\sum_{n=2}^\infty S_{n+1} x^n – \sum_{n=2}^\infty S_{n-1} x^n -\sum_{n=2}^\infty x^n
&= S_0+S_1 x+\frac{1}{x}\sum_{n=2}^\infty S_{n+1} x^{n+1} – x\sum_{n=2}^\infty S_{n-1} x^{n-1} -\sum_{n=2}^\infty x^n
&= S_0+S_1 x+\frac{1}{x}(S(x) – S_0 – S_1 x -S_2 x^2) – x(S(x) – S_0 ) -\frac{x^2}{1-x}

Using the values {S_0=1}, {S_1=2} and {S_2=4} the above reduces to

\displaystyle  S(x)=\frac{1}{(1-x)(1-x-x^2)} \ \ \ \ \ (3)

The amount of cancelling that took place to reduce to the simpler form from the formidable looking (9) suggests there could have been a simpler way. From the generating function of the fibbonaci sequence: G(x) &=\sum_{n=0}^\infty T_n x^n
&=\sum_{n=0}^\infty (S_n-S_{n-1}) x^n
&=S(x)-xS(x)

\displaystyle  S(x)=\frac{G(x)}{1-x} \ \ \ \ \ (4)

So, I could have got the generating function {S(x)} from direcly computing {G(x)}. Well, I’ve calculated {S(x)} so I verify that

\displaystyle  G(x)=\frac{1}{1-x-x^2} \ \ \ \ \ (5)

Now time to finally get the closed form from this generating function.

S(x) &=-\frac{1}{1-x}+\frac{x+2}{1-x-x^2}
&=-\frac{1}{1-x}+\frac{(x+2)}{\alpha-\beta}\left(\frac{1}{x-\alpha}-\frac{1}{x-\beta}\right) Now I think convergence issue has to be addressed, because the expansion of {1\over (x-\alpha)} would depend on the value of {\alpha}. If {\alpha} has a magnitude less than the max value of {x} then the power series would be in inverse powers of x. Ah, that is just silly of me! {x} is just a spectator in my scheme. I already know that {S(x)} has a power series expansion in powers of x not in inverse powers. So domain is the excluded interval {x\in (-\alpha,\alpha)}

\displaystyle  S(x) = (-1-x-x^2-x^3+\cdots) + \frac{(x+2)}{\beta-\alpha}\left( (\beta^{-1}-\alpha^{-1})s + (\beta^{-2}-\alpha^{-2})x^2 +\cdots	\right) \ \ \ \ \ (6)

\displaystyle  S_n = \frac{2}{\beta-\alpha}(\beta^{-n}-\alpha^{-n})+\frac{\beta^{-(n-1)}-\alpha^{-(n-1)}}{\beta-\alpha} \ \ \ \ \ (7)

But I just realize that all this is useless overworking in the face of the obvious solution staring at me now. The roots of the generating function for the fibbonaci sequence are {\alpha = -\frac{\sqrt{5}+1}{2}} and {\beta = \frac{\sqrt{5}11}{2}} and the from this, the closed form for the fibbonacis I get is

\displaystyle  T_n=\frac{1}{\sqrt{5}}\left( \frac{1}{\beta^{n+1}}-\frac{1}{\alpha^{n+1}} \right) \ \ \ \ \ (8)

I just need the sequence, {T_2+T_5+\cdots +T_n}

So this finally gives me

\displaystyle  S = \frac{1}{\sqrt{5}}\left( \frac{1-\beta^{-3k}}{\beta^3-1} -\frac{1-\alpha^{-3k}}{\alpha^3-1} \right) \ \ \ \ \ (9)

Now I need to find the {k^{th}} to truncate this summation at the limit, in this case 4 million. To take the general case where the limit is specified to be {L} the solution to {T_{3k-1}\leq L}

\displaystyle  k\leq \frac{\log\sqrt{5}L}{3 (\log\alpha -\log\beta) }\Rightarrow k=\lfloor \frac{\log \sqrt{5}L}{3 (\log\alpha -\log\beta) }\rfloor \ \ \ \ \ (10)

Finally, I’m done with the analysis. I plug in Eqn (23) into Eqn (22) and then translate the following formula to code.

Diversions: project Euler

I’ve set the stage to enetertain myself doing some programming over the next few days. Call it a method of procrastination, I could have better things to do. Like begin analyzining offline data looking for photons coming from {\pi^0} decay (what is that??)

I have Ubuntu 11.04 which I installed yesterday. It comes with g++ and python by default. Im an old c++ user, so this comes as a relief. Though I would like to learn python, and in particular, Haskell, so I installed that as well. I have high hopes with haskell as I am quiet impressed with its functional programming paradigm. I feel this is quiet close to the requirements of physicists and mathematicians, though I’d have to know more to form an opinion about it.

As with this Latex document (which will be converted to HTML and put up on my blog thanks to Luca Travesan’s Python Script) I am doing all my editing in vim. So its a convenient thing, I browse the web, where I am looking for text-heavy content anyway, on lynx. It might seem surprising but all the little queries I have about linux n00bs and syntax problems are handled and asnwered pretty well on a text based browser. Heck, I can even check gmail, though I havent found a way of updating wordpress from that. Hmm. Interesting.

So the thing that is nice about all this is that I can work without any meaningless distractions, advertisements, images etc. Now time to get started.

Problem 1: This was was easy, I did a simple brute force technique and got the answer. Euler1.cpp:

#include <iostream>
using namespace std;

int main()
{
int s=0,i;
for(i=1;i<1000;i++)
        if(i%3==0 || i%5==0)
                s=s+i;
cout<<s<<endl;
return 0;
}

Now Im thinking if there is a way of making this more efficient. Surely, 148k+ have solved this problem and more than half of them must have a conscience that prevents them from sleeping at night with this excuse of a solution. Well, it is a solution in all its dignity, no denying that, but let’s see….

I can reduce the number of iterations by introducing a closed formula for additions by multiples of 3, 5 etc, then iterating and subtracting from the sum, all the common numbers which got added twice. I can remove that iteration step as well by introducing a closed formula for numbers that are common multiples of 3 and five, in short, multiples of fifteen. So the basic algorithm is this, add multiples of 3 , add multiples of 5, subtract multiples of 15.

So looking for \displaystyle (3+6+9 \cdots+999)+(5+10+15+\cdots+995)-(15+30+45+\cdots + 990)

euler1a.cpp

#include <iostream>
using namespace std;
int main() {
int k=1000, j=k/3,l=k/5,m=k/15;
 k=3*(j*(j+1)/2)+5*(l*(l-1)/2)-15*(m*(m+1)/2);
 cout<<k<<endl;
return 0; }

I am not in the habit of using int main() and return, and prefer to use void main() whenever I can, but for some reason the compiler gives an error that I cannot debug from the ubuntu forums. Ill give this problem a rest for now.

That being done, let me try to implement this in Haskell. For now, I dont know what I hope to accomplish except to learn Haskell’s syntax.This was a basic problem which could be done without performing iterations, atleast that is what I’ve done to the best of my knowledge. I know there are a plethora of solutions to these problems out there, but I think that I’ll make a 5 question rule. That I would not compare my solutions to those by others until I have solved five further problems in this project. If I stick to my timeline this should mean I should post a comparision five days later. Hmm.

As a final thought, to make this problem more general:

Sum all multiples of {m} and {n} from {1} to {k}

The simple case would be when both {m} and {n} are co-prime, i.e they have no prime factors common, then the sum would be as above:

\displaystyle  S=\lfloor\frac{k}{n} \rfloor \left( \lfloor\frac{k}{n} \rfloor+1\right) +\lfloor\frac{k}{m} \rfloor \left( \lfloor\frac{k}{m} \rfloor+1\right)-\lfloor\frac{k}{mn} \rfloor \left( \lfloor\frac{k}{mn} \rfloor+1\right) \ \ \ \ \ (1)

In the general case, when {m} and {n} can be any two numbers with some prime factors common, say {\{p_1,\cdots ,p_k\}} then we just replace {mn} by {p_1p_2\cdots p_k}.

Now, there’s a lot of fuss Ive made about this problem. I am quiet pleased myself in the this one hour of working. Here’s a couple of things I hoped to accomplish and did, many of them occured while I was working:

  • Installed ubuntu
  • Would there be a cool way to work just in terminal so I dont have to touch the mouse and be interrupted? I dicovered vim editor and lynx. The early drawback has been the painful navigation structure. But I trust that it’ll pay off in the future. For the moment I’m a bit squeaky with the basics and havent been able to commit the nagivation keys to memory. Ill be learning more as I use it more.
  • Ran a succesful C++ program without error after a long time.
  • Installed haskell and ran my first succesful Haskell program
  • Set up a blog and downloaded a cool script that smiply converts latex documents to html. It would have been cooler though if wordpress had mathjax or mathml enabled as the script converts all the mathematical formulas into jpeg images. Blogspot does have this facility, but I do not use blogspot for a variety of reasons.

Well, that’s it for the day. Got my feet wet. Ill be doing one problem from project euler each day from now on. Once Im finished uploading this on the web I’ll get to finish Chapter One of Concrete Mathematics by Knuth and Gang. Have to do the exercises, and the second chapter, on sums, seems quiet interesting. Hopefully Ill be done with most of it today.

PS: I would link to codepad as a good online compiler to quickly check any code you see posted online for verification.