Wythoff array is an infinite matrix of integers derived from the Fibonacci sequence. Every positive integer in the matrix occurs only once.
Wythoff array:
1 2 3 5 8 13 ...
4 7 11 18 29 47 ...
6 10 16 26 42 68 ...
9 15 24 39 63 102 ...
12 20 32 52 84 136 ...
14 23 37 60 97 157 ...
. . . . . .
. . . . . .
If Am, n denotes the element in the mth row and nth column then
- Am, 1 = [[m?]?]
- Am, 2 = [[m?]?2]
- Am, n = Am, n-2 + Am, n-1 for n > 2
- ? = (1 + ?5) / 2
If we traverse matrix in an anti-diagonal way starting from top-left element then
Wythoff sequence:
1, 2, 4, 3, 7, 6, 5, 11, 10, 9….
For a given N, the task to print first N numbers of the sequence.
Examples:
Input : N = 10
Output : 1, 2, 4, 3, 7, 6, 5, 11, 10, 9
Input : N = 15
Output : 1, 2, 4, 3, 7, 6, 5, 11, 10, 9, 8, 18, 16, 15, 12
Approach:
The above recursions can be modified as
- T(n, -1) = n-1, if k = -1
- T(n, 0) = [n*?], if k = 0
- T(n, k) = T(n, k-1) + T(n, k-2), if k > 0
- ? = (1 + ?5) / 2
So we can recursively find the value of T(n, k) with two base cases for t = 0 and for t = –1. we will store the values in a map and use it when needed to reduce computation. After we get the array we have to traverse it in an anti- diagonal way, so we set i=0 and j=0 and decrease the j and increase i when the j < 0 we initialise j = i and i = 0.
we also keep a count which is increased when a number is displayed. We break the array when the count reaches the required value.
Below is the implementation of the above approach :
CPP
// C++ program to find Wythoff array#include <bits/stdc++.h>using namespace std;// Function to find the n, k term of Wythoff arrayint Wythoff(map<int, map<int, int> >& mp, int n, int k){ // tau = (sqrt(5)+1)/2 double tau = (sqrt(5) + 1) / 2.0, t_n_k; // Already_stored if (mp[n][k] != 0) return mp[n][k]; // T(n, -1) = n-1. if (k == -1) { return n - 1; } // T(n, 0) = floor(n*tau). else if (k == 0) { t_n_k = floor(n * tau); } // T(n, k) = T(n, k-1) + T(n, k-2) for k>=1. else { t_n_k = Wythoff(mp, n, k - 1) + Wythoff(mp, n, k - 2); } // Store mp[n][k] = t_n_k; // Return the ans return (int)t_n_k;}// Function to find first n terms of Wythoff // array by traversing in anti-diagonalvoid Wythoff_Array(int n){ int i = 0, j = 0, count = 0; // Map to store the Wythoff array map<int, map<int, int> > mp; while (count < n) { cout << Wythoff(mp, i + 1, j + 1); count++; if(count != n) cout << ", "; // Anti diagonal i++; j--; if (j < 0) { j = i; i = 0; } }}// Driver codeint main(){ int n = 15; // Function call Wythoff_Array(n); return 0;} |
Java
// Java program to find Wythoff arrayimport java.util.*; public class GFG{ // Function to find the n, k term of Wythoff array static int Wythoff(HashMap<Integer, HashMap<Integer, Integer>> mp, int n, int k) { // tau = (sqrt(5)+1)/2 double tau = (Math.sqrt(5) + 1) / 2.0, t_n_k; // Already_stored if (mp.containsKey(n) && mp.get(n).containsKey(k) && mp.get(n).get(k) != 0) return mp.get(n).get(k); // T(n, -1) = n-1. if (k == -1) { return n - 1; } // T(n, 0) = floor(n*tau). else if (k == 0) { t_n_k = Math.floor(n * tau); } // T(n, k) = T(n, k-1) + T(n, k-2) for k>=1. else { t_n_k = Wythoff(mp, n, k - 1) + Wythoff(mp, n, k - 2); } // Store mp.put(n, new HashMap<Integer, Integer>(k,(int)t_n_k)); // Return the ans return (int)t_n_k; } // Function to find first n terms of Wythoff // array by traversing in anti-diagonal static void Wythoff_Array(int n) { int i = 0, j = 0, count = 0; // Map to store the Wythoff array HashMap<Integer, HashMap<Integer,Integer>> mp = new HashMap<Integer, HashMap<Integer,Integer>>(); while (count < n) { System.out.print(Wythoff(mp, i + 1, j + 1)); count++; if(count != n) System.out.print(", "); // Anti diagonal i++; j--; if (j < 0) { j = i; i = 0; } } } // Driver code public static void main(String[] args) { int n = 15; // Function call Wythoff_Array(n); }}// This code is contributed by divyeshrabadiya07. |
Python3
# Python3 program to find Wythoff arrayimport math# Function to find the n, k term of Wythoff arraydef Wythoff(mp, n, k): # tau = (sqrt(5)+1)/2 tau = (math.sqrt(5) + 1) / 2 t_n_k = 0 # Already_stored if ((n in mp) and (k in mp[n])): return mp[n][k]; # T(n, -1) = n-1. if (k == -1): return n - 1; # T(n, 0) = floor(n*tau). elif (k == 0): t_n_k = math.floor(n * tau); # T(n, k) = T(n, k-1) + T(n, k-2) for k>=1. else: t_n_k = Wythoff(mp, n, k - 1) + Wythoff(mp, n, k - 2) # Store if n not in mp: mp[n] = dict() mp[n][k] = t_n_k; # Return the ans return int(t_n_k)# Function to find first n terms of Wythoff # array by traversing in anti-diagonaldef Wythoff_Array(n): i = 0 j = 0 count = 0; # Map to store the Wythoff array mp = dict() while (count < n): print(Wythoff(mp, i + 1, j + 1), end = '') count += 1 if(count != n): print(", ", end = '') # Anti diagonal i += 1 j -= 1 if (j < 0): j = i; i = 0; # Driver codeif __name__=='__main__': n = 15; # Function call Wythoff_Array(n); # This code is contributed by rutvik_56 |
C#
// C# program to find Wythoff arrayusing System;using System.Collections.Generic; class GFG { // Function to find the n, k term of Wythoff array static int Wythoff(Dictionary<int, Dictionary<int, int>> mp, int n, int k) { // tau = (sqrt(5)+1)/2 double tau = (Math.Sqrt(5) + 1) / 2.0, t_n_k; // Already_stored if (mp.ContainsKey(n) && mp[n].ContainsKey(k) && mp[n][k] != 0) return mp[n][k]; // T(n, -1) = n-1. if (k == -1) { return n - 1; } // T(n, 0) = floor(n*tau). else if (k == 0) { t_n_k = Math.Floor(n * tau); } // T(n, k) = T(n, k-1) + T(n, k-2) for k>=1. else { t_n_k = Wythoff(mp, n, k - 1) + Wythoff(mp, n, k - 2); } // Store if(!mp.ContainsKey(n)) { mp[n] = new Dictionary<int,int>(); } mp[n][k] = (int)t_n_k; // Return the ans return (int)t_n_k; } // Function to find first n terms of Wythoff // array by traversing in anti-diagonal static void Wythoff_Array(int n) { int i = 0, j = 0, count = 0; // Map to store the Wythoff array Dictionary<int, Dictionary<int,int>> mp = new Dictionary<int, Dictionary<int,int>>(); while (count < n) { Console.Write(Wythoff(mp, i + 1, j + 1)); count++; if(count != n) Console.Write(", "); // Anti diagonal i++; j--; if (j < 0) { j = i; i = 0; } } } // Driver code static void Main() { int n = 15; // Function call Wythoff_Array(n); }}// This code is contributed by divyesh072019. |
Javascript
// JS program to find Wythoff array// Function to find the n, k term of Wythoff arrayfunction Wythoff(mp, n, k){ // tau = (sqrt(5)+1)/2 let tau = (Math.sqrt(5) + 1) / 2.0, t_n_k; // Already_stored if (mp.hasOwnProperty(n) && mp[n].hasOwnProperty(k) && mp[n][k] != 0) return mp[n][k]; // T(n, -1) = n-1. if (k == -1) { return n - 1; } // T(n, 0) = floor(n*tau). else if (k == 0) { t_n_k = Math.floor(n * tau); } // T(n, k) = T(n, k-1) + T(n, k-2) for k>=1. else { t_n_k = Wythoff(mp, n, k - 1) + Wythoff(mp, n, k - 2); } // Store if (!mp.hasOwnProperty(n)) { mp[n] = {}; } mp[n][k] = Math.floor(t_n_k); // Return the ans return Math.floor(t_n_k);}// Function to find first n terms of Wythoff// array by traversing in anti-diagonalfunction Wythoff_Array(n){ let i = 0, j = 0, count = 0; // Map to store the Wythoff array let mp = {}; while (count < n) { process.stdout.write("" + Wythoff(mp, i + 1, j + 1)); count++; if (count != n) process.stdout.write(", "); // Anti diagonal i++; j--; if (j < 0) { j = i; i = 0; } }}// Driver codelet n = 15;// Function callWythoff_Array(n);// This code is contributed by phasing17. |
Output:
1, 2, 4, 3, 7, 6, 5, 11, 10, 9, 8, 18, 16, 15, 12,
Reference : https://oeis.org/A035513
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
