Transcript The Collatz Conjecture Problem: A Distributed Computing Approach

Exploring the Collatz Conjecture:
A Distributed Computing Approach
Student Name: Desmond McPhillips
Student ID: 13806604
Project Supervisor: Dr. Piyush Ojha
Course: BSc Hons Computing Science
Date: Dec 2007.
Overview
• Introduction:
What is the Collatz Conjecture?
•
•
•
•
•
•
Literature Review
Aims and Objectives
Requirements analysis and specification
Initial Design
Implementation Strategy
Project Management
Introduction
Mathematical Conjecture:
An Mathematical proposition which is speculated to be true but has not been
proved.
• The Collatz Conjecture is one such proposition.
• First proposed by Lothar Collatz in 1937
• The conjecture has eluded and intrigued mathematicians
• Prize fund established to reward the first person(s) to solve
the problem.
Introduction
• Easy to state:
The conjecture itself is easy to state: the following iterations of any positive
integer will always end in the Xn = 4, Xn+1 = 2, Xn+2 = 1, Xn+3 = 4 cycle:
Xi + 1 = ½ Xi if Xi is even
Xi + 1 = 3 Xi + 1 if Xi is odd
Example: initial X = 6;
3,10,5,16,8,4,2,1= 8 iterations
Important Numbers: 3, 16 and 8
(These are the statistics gathered, useful for mathematicians)
Literature Review
Work on the conjecture has been an on-going process with the
majority of the breakthroughs coming quite recently.
• Oliveira e Silva – May 2007, verified the range up to 2^58 1.
• Eric Roosendaal -- June 2007, verified the range up to 2^59 2.
• Both used computational, distributed approach.
1. http://www.ieeta.pt/~tos/3x+1.html
2.http://www.ericr.nl/wondrous/index.html
Aims and Objectives
The proposed project is quite similar to the approaches taken above,
an application to compute mass ranges of values and verify the
conjecture.
• Why re-invent the wheel?
• Key Differences:
Operating System Independence
Automatic Distribution
Graphical Interface
Aims and Objectives
Operating System Independence:
The established approaches have been dependant on the operating system in
which they were first developed.
• Proposed project:
Windows
Unix
Mac OS
With a greater range of operating systems supported, the application can gain
wider user contribution.
Aims and Objectives
Automatic Distribution:
• No importance to Silva.
• Roosendaal’s was restrictive.
The proposed project is to make the block acquisition an automatic process.
Once a client has completed a range of number and verified it, the client is
then supplied with another range to verify.
Aims and Objectives
Graphical Interface:
The proposed project will include a graphical interface to make the process
more meaningful to the client, especially if the application is used when
the system is idle and can be used as a screensaver.
Requirements analysis and
specification
To make this possible, certain aspects need to be addressed,
such as:
• Server application
Shall store information about clients (identifier, hardware/system
environments).
Shall store this information in a back end database (MySQL).
Shall assign ranges for computation/verification by clients.
Shall aggregate statistical data from computations returned by clients
Requirements analysis and
specification
• Client application:
Shall verify the conjecture on the ranges assigned to it and gather the
statistical data.
Shall be OS Independent .
Shall run when the clients machine is idle (possibly as a screensaver).
Shall report to the server on completion and request a new range to work
on.
Initial Design
Below is a prototype of the client side application interface:
Implementation Strategy
• Development Language:
Ideal language given the time constraints and requirements would be
Java – JNI can be implemented to offset any computational
overhead.
• Prototype:
Complete, see prototype GUI.
• Incremental development:
A series of beta releases on a 6-8 week basis before the final release in
April 2008.
Implementation Strategy
• Testing:
Due to the nature of the application, access to a wide range of
computers is needed to fulfil a test condition; Wombat Financial
Software will be able to satisfy this requirement with access to their
mass computer network and servers.
Project Management
Since I have decided upon Incremental development, I have
outlined my release goals:
• Beta release one: 17th Dec 2007
• Beta release two: 4th Feb 2008
• Beta release three: 24th March 2008
• Final release and project report: April 2008
Summary
•
•
•
•
Computational exploration on the Collatz Conjecture.
Distributed approach to the problem.
Improve on the current approaches.
Gather statistical information – can be used to aid
mathematical proof.
• All aspects completed: April 2008
• Any Questions.. ?