Saturday, January 22, 2011

Discrete connections (part I)


As you probably expected, all the previous subjects (Fibonacci sequence, golden ratio and fractals) are the pieces of a larger puzzle: a set of mathematical tools describing the nature of numbers. Their connection comes from a rather unexpected place: the greatest common divisor (the largest number dividing both numbers) algorithm as described by Euclid.
The algorithm states that in order to compute the gcd of two natural numbers m and n it suffices to compute the quotient q and remainder r from their integer division, and if r is non-zero repeat the procedure for n and r. The last non-zero remainder obtained in this manner, or n if no such remainder existed, is the gcd.
The subject of the Euclid's algorithm was intensively studied throughout the history of mathematics, one of the most interesting results (involving also Fibonacci numbers) being Lamé's theorem describing the number of steps it takes to compute the gcd for a given pair or numbers a and b.
The novel (to be read independent, since I consider that most of the time we reinvent the math) approach considers a rather unexplored characteristic of the algorithm, that of the summation of the remainders.
Thus let us define the euclidean summation, euclidean summation peak and euclidean summation positional peak by the following:
[; \tau_{1}(m,n) = m\mod n + \tau_{1}(n, m\mod n) ;]
[; \tau_{2}(n)=\max\{\tau_{1}(n,k)| 0\le k \le n\};]
[; \tau_{3}(n) = \max \{k|0 \le k \le n \; and \; \tau_{1}(n,k)=\tau_2(n) \} ;]
where mod is the extended modulus operator of two natural numbers, i.e. the remainder of their integer division, if the divisor is non-zero and zero otherwise.
The purpose of this blog-based article is to conjecture (and maybe someday prove) the fractal nature of the sum of remainders, fully describe a strong candidate for it and some tools to describe the common properties of the two.
Hope you'll find it interesting enough to stop by every now and then for updates.

No comments:

Post a Comment