Collatz Conjecture

The challenge: Implement an an algorithm that simulates all numbers reaching the collatz conjecture using Dynamic Programming.

Take any positive integer n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

https://www.wikiwand.com/en/Collatz_conjecture

``````class Node {
public:
Node(int val, int w) : connected_to(val), weight(w) {
next = nullptr;
}
int connected_to;
int weight; // weight of edge
Node *next;
};

public:
front = end = nullptr;
}

void insert(int vertex, int weight) {
Node *newNode = new Node(vertex, weight);

if (isEmpty()) {
front = end = newNode;
}
else {
end->next = newNode;
end = newNode;
}
}

void traverse() {
Node *temp = front;
while (temp != nullptr) {
cout << temp->connected_to << " -> ";
temp = temp->next;
}
cout << endl;
}

// tranversing linked list to see if element exists
bool exists(int number) {
Node *temp = front;
while (temp != nullptr) {
if (number == temp->connected_to) {
return true;
}
temp = temp->next;
}
return false;
}

private:
Node *front, *end;

bool isEmpty() {
return front == nullptr;
}
};

// simulating friend network
class Graph {
public:
Graph(bool dir) : directed(dir), n_verticies(0), n_edges(0) {
}

// error checking
if (numberExists(number)) {
cout << "number already exists" << endl;
return;
}

// create new vertex
graph.insert({ { number },{ newnumber } });
++n_verticies;
}

void removenumber(int number) {
// error checking
if (!numberExists(number) || graph.empty()) {
cout << "number does not exist" << endl;
return;
}

// removing a number will remove all connections
delete graph.find(number)->second;
graph.erase(number);
--n_verticies;
}

void connectnumber(int source, int dest) {
// error checking
if (!numberExists(dest) || !numberExists(source)) {
cout << "number(s) does not exists" << endl;
return;
}

if (graph.find(source)->second->exists(dest)) {
cout << "number A is already friends with number B" << endl;
return;
}

const int weight = 1;
graph.find(source)->second->insert(dest, weight);
++n_edges;
}

// check if number exists in the graph
bool findNumber(int number) {
if (graph.empty()) return false;
// side note: This graph traversal is very slow
// because we look at a visited node more than once

// need to do a full graph traversal
// I want to be able to tranverse in descending order
// because then ill save time looking down the tree.
// for each number in graph

for (std::map<int, LinkedList_edges*>::reverse_iterator iter = graph.rbegin(); iter != graph.rend(); ++iter) {
// first check all the the graph node itself
if (iter->first == number) return true;

// then check all its connections to see if the number exists in the graph
if (iter->second->exists(number)) {
return true;
}
}

// exhausted all search
return false;
}

void traverse() {
for (auto& i : graph) {
cout << i.first << ": ";
graph.find(i.first)->second->traverse();
}
}

int getNumVert() { return n_verticies; }
int getNumEdges() { return n_edges; }

private:
bool directed;
int n_verticies, n_edges;

// changed from unordered->map, because
// when I iterate, I want to be able to
// start from the largest number, and
// iterate down the graph

bool numberExists(int number) {
if (graph.find(number) == graph.end()) {
return false;
}
return true;
}
};

int main()
{
Graph *number_network = new Graph(true);

vector<int> sequence;

// building the collatz graph
for (int i = 2; i < 5000; i++) {
// if the number exists in the network, then
// we dont have to look further down the tree
// otherwise we take that number, and follow the conjecture

int newNum = i;
int newNumCopy = newNum;
bool found = number_network->findNumber(newNum);
cout << "New Sequence: " << endl << endl;
while (!found && newNum != 1) {
cout << "Searching for number: " << newNum << endl;
sequence.push_back(newNum);
//pause();
if (newNum % 2 == 0)
newNum /= 2;
else
newNum = (3 * newNum) + 1;

found = number_network->findNumber(newNum);
}
sequence.push_back(newNum);

// once newNum has proved to converge to 1, then
// we can insert it's 'sequence' into the graph network

// the number may have also been found, which we then must
// insert the sequence of numbers that have not been found
// and connect that sequence the number that has been found

// in both cases, the algorithm is the same

cout << newNumCopy << " has converged to " << newNum << endl;
//pause();
int src, dest;
src = sequence.at(0);
cout << "adding " << src << " to network" << endl;

for (int i = 0; i < sequence.size() - 1; i++) {
src = sequence.at(i);
dest = sequence.at(i + 1);

cout << "adding " << dest << " to network" << endl;
number_network->connectnumber(src, dest);
cout << "connecting " << src << " -> " << dest << " to network" << endl;
// 1 2
// 1 -> 2
// 1 -> 2 3
// 1 -> 2 -> 3
}
sequence.clear();
// look at the next number
}
}``````

Last updated