Calculate Newman Conway Sequence

Reading time: 25 minutes | Coding time: 10 minutes

Newman Conway Sequence is the sequence which follows a given recursive relation (p(n) = p(p(n-1)) + p(n-p(n-1))) to generate a series of numbers. We will calculate the elements using a Dynamic Programming approach in linear time O(N).

First few elements of Newman Conway Sequence are:

1 1 2 2 3 4 4 4 5 6 7 7.......

In terms of mathematical model, the Newman Conway sequence follows the following Recurrence Relation:

P(n) = P(P(n - 1)) + P(n - P(n - 1))
where,
P(n) = n-th number in Newman Conway Sequence
with P(1) = P(2) = 1

We solve this using two approaches:

• Naive approach O(2^N) time
• Dynamic Programming approach O(N) time

Naive Approach

Implementing the Recurrance Relation as it is in the structure, follwing is the Pseudocode

unsigned int NewmanConwaySequenceTerm (unsigned int n)
{
    if(n == 1 or n == 2)
        return 1;
    else
        NewmanConwaySequenceTerm(NewmanConwaySequenceTerm(n - 1)) 
        + NewmanConwaySequenceTerm(n - NewmanConwaySequenceTerm(n - 1));
}

Implementation of Naive Approach

Following is the C++ implementation of the Naive approach:

#include<iostream>
class NewmanConwaySequence
{
public:
    NewmanConwaySequence(unsigned int n) : n(n) {}
    unsigned int calculateNewmanConwaySequenceTermRecur(unsigned int n);
private:
    unsigned int n;
};
unsigned int NewmanConwaySequence::calculateNewmanConwaySequenceTermRecur(unsigned int n)
{
    if(n == 1 or n == 2)
        return 1;
    else
        return calculateNewmanConwaySequenceTermRecur(calculateNewmanConwaySequenceTermRecur(n - 1)) + calculateNewmanConwaySequenceTermRecur(n - calculateNewmanConwaySequenceTermRecur(n - 1));
}
int main()
{
    unsigned int nValue;
    std::cout << "\nEnter the Index of Newman Conway Sequence : ";
    std::cin >> nValue;
    NewmanConwaySequence aNewmanConwaySequenceObj(nValue);
    std::cout << "\nValue of term at " << nValue << " indexed in Newman Conway Sequence : " << aNewmanConwaySequenceObj.calculateNewmanConwaySequenceTermRecur(nValue);
}

Input

Enter the Index of Newman Conway Sequence : 10

Output

Value of term at 10 indexed in Newman Conway Sequence : 6

Complexity

The Time and Space Complexities of code by using Naive Approach are :

• Time complexity: O(2n)
• Space complexity: k

space complexity here k means, k frames will loaded in RAM containing the local varialbles declared in function with respective data-type which will depend directly on architecture of Operating System of Local Host Machine

Approach Using Dynamic Programming

Basic Idea in using Dynamic Programming is storing the precomputed terms of a sequence in a data structure and use it for next generating sequence term.

Algorithm

• Step 1 : Input to execute the following program is twofold, get the positive input integer from user: the index of the required Newman Conway Sequence term and the bool datatype second input 'true' for generating the Newman Conway sequence till the index provided by the user and 'false' for generating the particular Newman Conway sequence term.
• Step 2 : Check the requirement of the user against the Newman Conway Sequence by chacking the status of flag whether it is 'true' or 'false'.
• Step 3 : If flag found 'true' : generating the sequence, initializing the first three flagship members of the sequence as 0, 1 and 1 respectively in a data structure called array(in C++, any other linear data structure can be used in other languages) in size of n + 1.
• Step 4 : Further, computing the forward terms from pre-computer terms according to the recurrance relation. The advantage of using this approach is at each and every time computing higher indexed terms we don't have to compute all the low indexed terms of sequence, which saves the resources (space and time).
• Step 5 : If flag found 'false' : generating the required specific term, execute Step 3 and Step 4 with a slight change in way of displaying the output : return the positive integer situated at last index of the data structure used, is the required output.
• Step 6 : Stop.

The basic idea is as follows:

int ncs[n + 1];
// Base case
ncs[0] = 0;
ncs[1] = 1;
ncs[2] = 1;
// Bottom up dynamic programming approach
for (int i = 3; i <= n; i++)
    ncs[i] = ncs[ncs[i - 1]] + ncs[i - ncs[i - 1]];

Implementation

#include<iostream>
class NewmanConwaySequence
{
public:
    NewmanConwaySequence(unsigned int n) : n(n) {}
    void calculateNewmanConwaySequenceTermDP(bool flag);
private:
    unsigned int n;
};
void NewmanConwaySequence::calculateNewmanConwaySequenceTermDP(bool flag)
{
    if(flag == true)
    {
        unsigned int ncs[n + 1];
        ncs[0] = 0;
        ncs[1] = 1;
        ncs[2] = 1;
        for (int i = 3; i <= n; i++)
            ncs[i] = ncs[ncs[i - 1]] + ncs[i - ncs[i - 1]];
        std::cout << "\nNewman Conway Sequence with " << n << " elements : ";
        for(int i = 1; i <= n; i++)
            std::cout << ncs[i] << " ";
    }
    else
    {
        unsigned int ncs[n + 1];
        ncs[0] = 0;
        ncs[1] = 1;
        ncs[2] = 1;
        for (int i = 3; i <= n; i++)
            ncs[i] = ncs[ncs[i - 1]] + ncs[i - ncs[i - 1]];
        std::cout << "\nNewman Conway Sequence term at " << n << " indexed : ";
        std::cout << ncs[n];
    }
}
int main()
{
    unsigned int nValue, value;
    bool flag;
    std::cout << "\nEnter the Index of Newman Conway Sequence : ";
    std::cin >> nValue;
    NewmanConwaySequence aNewmanConwaySequenceoj(nValue);
    std::cout << "\nEnter the non-zero to generate the Newman Conway Sequence or zero to generate particular term in Newman Conway Sequence : ";
    std::cin >> value;
    if(value)
        flag = true;
    else
        flag = false;
    if(flag == true)
        aNewmanConwaySequenceoj.calculateNewmanConwaySequenceTermDP(true);
    else
        aNewmanConwaySequenceoj.calculateNewmanConwaySequenceTermDP(false);
 }

Input

Enter the Index of Newman Conway Sequence : 12

Enter the non-zero to generate the Newman Conway Sequence or zero to generate particular term in Newman Conway Sequence : 1

Output

Newman Conway Sequence with 12 elements : 1 1 2 2 3 4 4 4 5 6 7 7

Complexity

The Time and Space Complexities of code by using Dynamic Programming Approach are :

• Time complexity: O(n)
• Space complexity: n
  where n is the user required index of the Newman Conway Sequence.