Introduction
Following the divine proportion, the Wythoff series is a numerical sequence employed in a player's navigation within combinatorial game theory. It was christened in honor of Willem Abraham Wythoff, who devised a sequence rooted in Fibonacci numbers that exhibit intriguing connections with the golden ratio. This piece will delve into the Wythoff series and provide a tutorial on the C++ script that produces it.
Problem Statement:
The Wythoff sequence comprises of a pair of intertwined sequences referred to as the lower and upper Wythoff sequences, identified as:
A(n) = floor(n * φ)
B(n) = A(n) + n
Where φ (phi) is equal to (1 + sqrt(5)) / 2, representing the golden ratio.
Our objective is to produce and exhibit the initial N elements of the Wythoff sequence through C++.
Mathematical Background:
The Wythoff sequence is intricately connected to the golden ratio, which guarantees the numbers are evenly spread out to prevent clustering. The sequences can be described as follows:
- The Lower Wythoff sequence: A(n) = floor(n * φ)
- The Upper Wythoff sequence: B(n) = A(n) + n
These series are vital in strategic games such as Wythoff’s game and Nim.
Example 1:
Let's consider a C++ code to produce and exhibit the initial N elements of the Wythoff sequence.
Example
#include <iostream>
#include <cmath>
using namespace std;
const double PHI = (1 + sqrt(5)) / 2; // Golden ratio
// Function to generate and display the Wythoff sequence
void generateWythoffSequence(int N) {
cout << "Wythoff sequence (first " << N << " terms):" << endl;
cout << "Lower Sequence: ";
for (int i = 1; i <= N; i++) {
cout << (int)floor(i * PHI) << " ";
}
cout << "\nUpper Sequence: ";
for (int i = 1; i <= N; i++) {
cout << (int)floor(i * PHI) + i << " ";
}
cout << endl;
}
int main() {
int N;
cout << "Enter the number of terms: ";
cin >> N;
generateWythoffSequence(N);
return 0;
}
Output:
Output
Enter the number of terms: 10
Wythoff sequence (first 10 terms):
Lower Sequence: 1 3 4 6 8 9 11 12 14 16
Upper Sequence: 2 5 7 10 13 15 18 20 23 26
Explanation of the Code:
- Set the value for PHI: We calculate φ by doing (1 + sqrt(5)) / 2 beforehand.
- Generate the sequences in a for loop: Compute lower sequence with floor(n PHI) and upper sequence with floor(n PHI)+n.
- The user inputs a value for N and the program returns the first N elements of both sequences in succession.
Example 2:
Let's consider a different instance to demonstrate the Wythoff Sequence in the C++ programming language.
Example
#include <iostream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <fstream>
#include <stdexcept>
#include <algorithm>
using namespace std;
const double PHI = (1 + sqrt(5)) / 2; // Golden ratio
class WythoffSequence {
private:
int N;
vector<int> lowerSeq;
vector<int> upperSeq;
// Function to generate the sequences
void generateSequences() {
for (int i = 1; i <= N; i++) {
int lowerValue = static_cast<int>(floor(i * PHI));
int upperValue = lowerValue + i;
lowerSeq.push_back(lowerValue);
upperSeq.push_back(upperValue);
}
}
public:
// Constructor
WythoffSequence(int num) {
if (num <= 0) {
throw invalid_argument("N must be a positive integer.");
}
N = num;
generateSequences();
}
// Function to display the sequences
void displaySequences() const {
cout << "\nWythoff sequence (first " << N << " terms):\n";
cout << "Lower Sequence: ";
for (int val : lowerSeq) {
cout << val << " ";
}
cout << "\nUpper Sequence: ";
for (int val : upperSeq) {
cout << val << " ";
}
cout << endl;
}
// Function to search for an element in the sequence
bool searchElement(int value) const {
return (find(lowerSeq.begin(), lowerSeq.end(), value) != lowerSeq.end() ||
find(upperSeq.begin(), upperSeq.end(), value) != upperSeq.end());
}
// Function to save the sequence to a file
void saveToFile(const string &filename) const {
ofstream file(filename);
if (!file) {
cerr << "Error opening file for writing!\n";
return;
}
file << "Wythoff sequence (first " << N << " terms):\n";
file << "Lower Sequence: ";
for (int val : lowerSeq) {
file << val << " ";
}
file << "\nUpper Sequence: ";
for (int val : upperSeq) {
file << val << " ";
}
file << endl;
file.close();
cout << "Sequence saved to " << filename << endl;
}
};
int main() {
try {
int N;
cout << "Enter the number of terms: ";
cin >> N;
WythoffSequence wythoff(N);
wythoff.displaySequences();
// Search for an element
int searchVal;
cout << "Enter a number to search in the sequence: ";
cin >> searchVal;
if (wythoff.searchElement(searchVal)) {
cout << searchVal << " is present in the sequence.\n";
} else {
cout << searchVal << " is not found in the sequence.\n";
}
// Save sequence to a file
wythoff.saveToFile("wythoff_sequence.txt");
} catch (const exception &e) {
cerr << "Error: " << e.what() << endl;
}
return 0;
}
Output:
Output
Enter the number of terms: 20
Wythoff sequence (first 20 terms):
Lower Sequence: 1 3 4 6 8 9 11 12 14 16 17 19 21 22 24 25 27 29 30 32
Upper Sequence: 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39 41 44 47 49 52
Enter a number to search in the sequence: 23
23 is present in the sequence.
Sequence saved to wythoff_sequence.txt
Applications of the Wythoff Sequence:
- In combinatorial game theory, it is used in Wythoff’s game and other similar two-person games.
- In mathematics, it appears in studies that have to do with the Fibonacci and golden ratio.
- In optimization, it assists in the division of resources amongst two or more parties.
Example 3:
Let's consider a different instance to demonstrate the Wythoff Sequence within C++.
Example
#include <iostream>
#include <cmath>
#include <vector>
#include <thread>
#include <mutex>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <chrono>
#include <algorithm>
using namespace std;
using namespace std::chrono;
const double PHI = (1 + sqrt(5)) / 2; // Golden Ratio
class WythoffSequence {
private:
int N;
vector<int> lowerSeq;
vector<int> upperSeq;
unordered_map<int, pair<int, int>> memoization;
mutex mtx;
// Function to compute a single Wythoff number
pair<int, int> computeTerm(int i) {
if (memoization.find(i) != memoization.end()) {
return memoization[i];
}
int lowerValue = static_cast<int>(floor(i * PHI));
int upperValue = lowerValue + i;
memoization[i] = {lowerValue, upperValue};
return {lowerValue, upperValue};
}
// Function to generate sequences using multithreading
void generateSequences() {
vector<thread> threads;
for (int i = 1; i <= N; i++) {
threads.emplace_back([this, i]() {
pair<int, int> values = computeTerm(i);
lock_guard<mutex> lock(mtx);
lowerSeq.push_back(values.first);
upperSeq.push_back(values.second);
});
}
for (auto& th : threads) {
th.join();
}
}
public:
// Constructor
explicit WythoffSequence(int num) {
if (num <= 0) {
throw invalid_argument("N must be a positive integer.");
}
N = num;
auto start = high_resolution_clock::now();
generateSequences();
auto end = high_resolution_clock::now();
cout << "\nSequence generated in "
<< duration_cast<milliseconds>(end - start).count()
<< " ms.\n";
}
// Function to display sequences
void displaySequences() const {
cout << "\nWythoff sequence (first " << N << " terms):\n";
cout << "Lower Sequence: ";
for (int val : lowerSeq) {
cout << val << " ";
}
cout << "\nUpper Sequence: ";
for (int val : upperSeq) {
cout << val << " ";
}
cout << endl;
}
// Function to check if a number exists in the sequence
bool searchElement(int value) const {
return (find(lowerSeq.begin(), lowerSeq.end(), value) != lowerSeq.end() ||
find(upperSeq.begin(), upperSeq.end(), value) != upperSeq.end());
}
// Function to save the sequence to a file
void saveToFile(const string &filename) const {
ofstream file(filename);
if (!file) {
cerr << "Error opening file!\n";
return;
}
file << "Wythoff sequence (first " << N << " terms):\n";
file << "Lower Sequence: ";
for (int val : lowerSeq) {
file << val << " ";
}
file << "\nUpper Sequence: ";
for (int val : upperSeq) {
file << val << " ";
}
file << endl;
file.close();
cout << "Sequence saved to " << filename << endl;
}
// Function to visualize the sequence as an ASCII bar chart
void visualizeSequence() const {
cout << "\nASCII Representation of Wythoff Sequence:\n";
for (size_t i = 0; i < lowerSeq.size(); ++i) {
cout << setw(3) << i + 1 << ": ";
for (int j = 0; j < lowerSeq[i]; ++j) {
cout << "*";
}
cout << " (" << lowerSeq[i] << ")\n";
}
}
};
// Function to display menu options
void displayMenu() {
cout << "\n===== Wythoff Sequence Generator =====\n";
cout << "1. Generate & Display Sequence\n";
cout << "2. Search for a Number in the Sequence\n";
cout << "3. Save Sequence to a File\n";
cout << "4. Visualize Sequence\n";
cout << "5. Exit\n";
cout << "======================================\n";
}
int main() {
int choice, N;
cout << "Enter the number of terms for Wythoff sequence: ";
cin >> N;
WythoffSequence wythoff(N);
while (true) {
displayMenu();
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
wythoff.displaySequences();
break;
case 2: {
int searchVal;
cout << "Enter number to search: ";
cin >> searchVal;
if (wythoff.searchElement(searchVal)) {
cout << searchVal << " is in the sequence.\n";
} else {
cout << searchVal << " is NOT in the sequence.\n";
}
break;
}
case 3:
wythoff.saveToFile("wythoff_sequence.txt");
break;
case 4:
wythoff.visualizeSequence();
break;
case 5:
cout << "Exiting program...\n";
return 0;
default:
cout << "Invalid choice! Please enter a valid option.\n";
}
}
return 0;
}
Output:
Output
Enter the number of terms for Wythoff sequence: 30
Sequence generated in 6 ms.
===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 1
Wythoff sequence (first 30 terms):
Lower Sequence: 4 19 1 40 3 45 6 8 9 11 12 46 48 14 16 17 21 22 24 25 27 29 30 32 33 35 37 38 42 43
Upper Sequence: 7 31 2 65 5 73 10 13 15 18 20 75 78 23 26 28 34 36 39 41 44 47 49 52 54 57 60 62 68 70
===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 2
Enter number to search: 39
39 is in the sequence.
===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 2
Enter number to search: 43
43 is in the sequence.
===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 2
Enter number to search: 1000
1000 is NOT in the sequence.
===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 3
Sequence saved to wythoff_sequence.txt
===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 4
ASCII Representation of Wythoff Sequence:
1: **** (4)
2: ******************* (19)
3: * (1)
4: **************************************** (40)
5: *** (3)
6: ********************************************* (45)
7: ****** (6)
8: ******** (8)
9: ********* (9)
10: *********** (11)
11: ************ (12)
12: ********************************************** (46)
13: ************************************************ (48)
14: ************** (14)
15: **************** (16)
16: ***************** (17)
17: ********************* (21)
18: ********************** (22)
19: ************************ (24)
20: ************************* (25)
21: *************************** (27)
22: ***************************** (29)
23: ****************************** (30)
24: ******************************** (32)
25: ********************************* (33)
26: *********************************** (35)
27: ************************************* (37)
28: ************************************** (38)
29: ****************************************** (42)
30: ******************************************* (43)
===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 5
Exiting program...
Conclusion:
In summary, the elegant connection between number theory and combinatorial mathematics is effectively demonstrated through the Wythoff sequence. By leveraging the golden ratio, it becomes feasible to generate unique sequences with practical uses. The C++ code presented below offers a streamlined approach to calculating the sequence, enabling seamless exploration of various N values.
