Wythoff Sequence In C++

Introduction

Following the golden ratio, the Wythoff sequence is a mathematical combination used in a player’s movement in combinatorial game theory. It was named after Willem Abraham Wythoff , who made a sequence based on Fibonacci numbers that have curious relationships with the golden section. In this article, we will discuss the Wythoff sequence and present an article on the C++ code that generates it.

Problem Statement:

The Wythoff sequence consists of two interleaved sequences known as the lower and upper Wythoff sequences, denoted as:

A(n) = floor(n * φ)

B(n) = A(n) + n

Where φ (phi) = (1 + sqrt(5)) / 2 is the golden ratio.

Our goal is to generate and display the first N terms of the Wythoff sequence using C++.

Mathematical Background:

The Wythoff sequence is closely linked to the golden ratio, which ensures the numbers are well distributed without clustering. The sequences are defined as:

✅ Lower Wythoff sequence: A(n) = floor(n * φ)
✅ Upper Wythoff sequence: B(n) = A(n) + n

These sequences play a crucial role in combinatorial games like Wythoff’s game and Nim.

Example 1:

Let us take a C++ program to generate and display the first N terms 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 us take another example to illustrate the Wythoff Sequence in C++.

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 us take another example to illustrate the Wythoff Sequence in 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 conclusion, the interactions between number theory and combinatorial mathematics are illustrated elegantly by the Wythoff sequence. It is possible to create special sequences that have real-world applications by utilizing the golden ratio. The C++ implementation provided here efficiently computes the sequence, which makes it easy to experiment with different values of N.

Introduction

Problem Statement:

Mathematical Background:

Example 1:

Explanation of the Code:

Example 2:

Applications of the Wythoff Sequence:

Example 3:

Conclusion:

Input Required