Skip to main content

Newman-conway sequence program

Welcome to this article about the Newman-Conway sequence program. In this article, we will discuss the problem statement, provide a pseudocode algorithm with an explanation, and analyze the resultant output. The Newman-Conway sequence is a mathematical sequence named after the mathematicians Edward Newman and John Horton Conway.

Problem Statement

The Newman-Conway sequence is defined as follows:

  1. The first term of the sequence is 1.
  2. The second term of the sequence is 1.
  3. For any other term, the value is determined by taking the value of the previous term as an index and summing the values of the terms at that index and at the index given by subtracting the previous term from the current term.

The task is to write a program that generates the Newman-Conway sequence of a given size.

Pseudocode Algorithm

newmanConwaySequence(n):
    if n <= 0:
        return

    record = array of size n+1
    record[0] = 0
    record[1] = 1

    if n > 2:
        record[2] = 1

    for i from 3 to n:
        record[i] = record[record[i - 1]] + record[i - record[i - 1]]

    for i from 1 to n:
        print record[i]

The pseudocode algorithm begins by checking if the given size, n, is less than or equal to 0. If so, the function returns. Otherwise, an array called record is created with a size of n+1. The initial values for the sequence, record[0] and record[1], are set to 0 and 1, respectively. If n is greater than 2, record[2] is set to 1.

The algorithm then iterates from 3 to n and calculates each term of the Newman-Conway sequence by using the values of the previous terms. The value at index i is determined by adding the values at record[i - 1] and record[i - record[i - 1]].

Finally, the algorithm prints the elements of the sequence from index 1 to n.

Code Solution

/*
    C program for
    Newman-conway sequence program
*/
#include <stdio.h>

void newmanConwaySequence(int n)
{
	if (n <= 0)
	{
		return;
	}
	// This is used to collect result
	int record[n + 1];
	// Set initial value
	record[0] = 0;
	record[1] = 1;
	if (n > 2)
	{
		record[2] = 1;
	}
	for (int i = 3; i <= n; ++i)
	{
		// Collect Newman-conway sequence
		record[i] = record[record[i - 1]] + record[i - record[i - 1]];
	}
	for (int i = 1; i <= n; ++i)
	{
		// Display the sequence element   
		printf("  %d", record[i]);
	}
}
int main(int argc, char
	const *argv[])
{
	// Display size 
	int n = 10;
	printf("\n Newman-conway sequence of size %d is \n", n);
	// n = 10
	newmanConwaySequence(n);
	n = 15;
	printf("\n Newman-conway sequence of size %d is \n", n);
	// n = 15
	newmanConwaySequence(n);
	return 0;
}

Output

 Newman-conway sequence of size 10 is
  1  1  2  2  3  4  4  4  5  6
 Newman-conway sequence of size 15 is
  1  1  2  2  3  4  4  4  5  6  7  7  8  8  8
/*
    Java program for
    Newman-conway sequence program
*/
public class ConwaySequence
{
	public void newmanConwaySequence(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// This is used to collect result
		int[] record = new int[n + 1];
		// Set initial value
		record[0] = 0;
		record[1] = 1;
		if (n > 2)
		{
			record[2] = 1;
		}
		for (int i = 3; i <= n; ++i)
		{
			// Collect Newman-conway sequence
			record[i] = record[record[i - 1]] + record[i - record[i - 1]];
		}
		for (int i = 1; i <= n; ++i)
		{
			// Display the sequence element   
			System.out.print(" " + record[i]);
		}
	}
	public static void main(String[] args)
	{
		ConwaySequence task = new ConwaySequence();
		// Display size 
		int n = 10;
		System.out.print("\n Newman-conway sequence of size " + n + " is \n");
		// n = 10
		task.newmanConwaySequence(n);
		n = 15;
		System.out.print("\n Newman-conway sequence of size " + n + " is \n");
		// n = 15
		task.newmanConwaySequence(n);
	}
}

Output

 Newman-conway sequence of size 10 is
 1 1 2 2 3 4 4 4 5 6
 Newman-conway sequence of size 15 is
 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8
// Include header file
#include <iostream>
using namespace std;
/*
    C++ program for
    Newman-conway sequence program
*/
class ConwaySequence
{
	public: void newmanConwaySequence(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// This is used to collect result
		int record[n + 1];
		// Set initial value
		record[0] = 0;
		record[1] = 1;
		if (n > 2)
		{
			record[2] = 1;
		}
		for (int i = 3; i <= n; ++i)
		{
			// Collect Newman-conway sequence
			record[i] = record[record[i - 1]] + record[i - record[i - 1]];
		}
		for (int i = 1; i <= n; ++i)
		{
			// Display the sequence element   
			cout << " " << record[i];
		}
	}
};
int main()
{
	ConwaySequence *task = new ConwaySequence();
	// Display size 
	int n = 10;
	cout << "\n Newman-conway sequence of size " << n << " is \n";
	// n = 10
	task->newmanConwaySequence(n);
	n = 15;
	cout << "\n Newman-conway sequence of size " << n << " is \n";
	// n = 15
	task->newmanConwaySequence(n);
	return 0;
}

Output

 Newman-conway sequence of size 10 is
 1 1 2 2 3 4 4 4 5 6
 Newman-conway sequence of size 15 is
 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8
// Include namespace system
using System;
/*
    Csharp program for
    Newman-conway sequence program
*/
public class ConwaySequence
{
	public void newmanConwaySequence(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// This is used to collect result
		int[] record = new int[n + 1];
		// Set initial value
		record[0] = 0;
		record[1] = 1;
		if (n > 2)
		{
			record[2] = 1;
		}
		for (int i = 3; i <= n; ++i)
		{
			// Collect Newman-conway sequence
			record[i] = record[record[i - 1]] + record[i - record[i - 1]];
		}
		for (int i = 1; i <= n; ++i)
		{
			// Display the sequence element   
			Console.Write(" " + record[i]);
		}
	}
	public static void Main(String[] args)
	{
		ConwaySequence task = new ConwaySequence();
		// Display size 
		int n = 10;
		Console.Write("\n Newman-conway sequence of size " + n + " is \n");
		// n = 10
		task.newmanConwaySequence(n);
		n = 15;
		Console.Write("\n Newman-conway sequence of size " + n + " is \n");
		// n = 15
		task.newmanConwaySequence(n);
	}
}

Output

 Newman-conway sequence of size 10 is
 1 1 2 2 3 4 4 4 5 6
 Newman-conway sequence of size 15 is
 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8
package main
import "fmt"
/*
    Go program for
    Newman-conway sequence program
*/

func newmanConwaySequence(n int) {
	if n <= 0 {
		return
	}
	// This is used to collect result
	var record = make([]int,n+1)
	// Set initial value
	record[0] = 0
	record[1] = 1
	if n > 2 {
		record[2] = 1
	}
	for i := 3 ; i <= n ; i++ {
		// Collect Newman-conway sequence
		record[i] = record[record[i - 1]] + record[i - record[i - 1]]
	}
	for i := 1 ; i <= n ; i++ {
		// Display the sequence element   
		fmt.Print(" ", record[i])
	}
}
func main() {

	// Display size 
	var n int = 10
	fmt.Print("\n Newman-conway sequence of size ", n, " is \n")
	// n = 10
	newmanConwaySequence(n)
	n = 15
	fmt.Print("\n Newman-conway sequence of size ", n, " is \n")
	// n = 15
	newmanConwaySequence(n)
}

Output

 Newman-conway sequence of size 10 is
 1 1 2 2 3 4 4 4 5 6
 Newman-conway sequence of size 15 is
 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8
<?php
/*
    Php program for
    Newman-conway sequence program
*/
class ConwaySequence
{
	public	function newmanConwaySequence($n)
	{
		if ($n <= 0)
		{
			return;
		}
		// This is used to collect result
		$record = array_fill(0, $n + 1, 0);
		// Set initial value
		$record[0] = 0;
		$record[1] = 1;
		if ($n > 2)
		{
			$record[2] = 1;
		}
		for ($i = 3; $i <= $n; ++$i)
		{
			// Collect Newman-conway sequence
			$record[$i] = $record[$record[$i - 1]] + 
              $record[$i - $record[$i - 1]];
		}
		for ($i = 1; $i <= $n; ++$i)
		{
			// Display the sequence element   
			echo(" ".$record[$i]);
		}
	}
}

function main()
{
	$task = new ConwaySequence();
	// Display size 
	$n = 10;
	echo("\n Newman-conway sequence of size ".$n.
		" is \n");
	// n = 10
	$task->newmanConwaySequence($n);
	$n = 15;
	echo("\n Newman-conway sequence of size ".$n.
		" is \n");
	// n = 15
	$task->newmanConwaySequence($n);
}
main();

Output

 Newman-conway sequence of size 10 is
 1 1 2 2 3 4 4 4 5 6
 Newman-conway sequence of size 15 is
 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8
/*
    Node JS program for
    Newman-conway sequence program
*/
class ConwaySequence
{
	newmanConwaySequence(n)
	{
		if (n <= 0)
		{
			return;
		}
		// This is used to collect result
		var record = Array(n + 1).fill(0);
		// Set initial value
		record[0] = 0;
		record[1] = 1;
		if (n > 2)
		{
			record[2] = 1;
		}
		for (var i = 3; i <= n; ++i)
		{
			// Collect Newman-conway sequence
			record[i] = record[record[i - 1]] + record[i - record[i - 1]];
		}
		for (var i = 1; i <= n; ++i)
		{
			// Display the sequence element   
			process.stdout.write(" " + record[i]);
		}
	}
}

function main()
{
	var task = new ConwaySequence();
	// Display size 
	var n = 10;
	process.stdout.write("\n Newman-conway sequence of size " + n + " is \n");
	// n = 10
	task.newmanConwaySequence(n);
	n = 15;
	process.stdout.write("\n Newman-conway sequence of size " + n + " is \n");
	// n = 15
	task.newmanConwaySequence(n);
}
main();

Output

 Newman-conway sequence of size 10 is
 1 1 2 2 3 4 4 4 5 6
 Newman-conway sequence of size 15 is
 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8
#    Python 3 program for
#    Newman-conway sequence program
class ConwaySequence :
	def newmanConwaySequence(self, n) :
		if (n <= 0) :
			return
		
		#  This is used to collect result
		record = [0] * (n + 1)
		#  Set initial value
		record[0] = 0
		record[1] = 1
		if (n > 2) :
			record[2] = 1
		
		i = 3
		while (i <= n) :
			#  Collect Newman-conway sequence
			record[i] = record[record[i - 1]] + record[i - record[i - 1]]
			i += 1
		
		i = 1
		while (i <= n) :
			#  Display the sequence element   
			print(" ", record[i], end = "")
			i += 1
		
	

def main() :
	task = ConwaySequence()
	#  Display size 
	n = 10
	print("\n Newman-conway sequence of size ", n ," is ")
	#  n = 10
	task.newmanConwaySequence(n)
	n = 15
	print("\n Newman-conway sequence of size ", n ," is ")
	#  n = 15
	task.newmanConwaySequence(n)

if __name__ == "__main__": main()

Output

 Newman-conway sequence of size  10  is
  1  1  2  2  3  4  4  4  5  6
 Newman-conway sequence of size  15  is
  1  1  2  2  3  4  4  4  5  6  7  7  8  8  8
#    Ruby program for
#    Newman-conway sequence program
class ConwaySequence 
	def newmanConwaySequence(n) 
		if (n <= 0) 
			return
		end

		#  This is used to collect result
		record = Array.new(n + 1) {0}
		#  Set initial value
		record[0] = 0
		record[1] = 1
		if (n > 2) 
			record[2] = 1
		end

		i = 3
		while (i <= n) 
			#  Collect Newman-conway sequence
			record[i] = record[record[i - 1]] + record[i - record[i - 1]]
			i += 1
		end

		i = 1
		while (i <= n) 
			#  Display the sequence element   
			print(" ", record[i])
			i += 1
		end

	end

end

def main() 
	task = ConwaySequence.new()
	#  Display size 
	n = 10
	print("\n Newman-conway sequence of size ", n ," is \n")
	#  n = 10
	task.newmanConwaySequence(n)
	n = 15
	print("\n Newman-conway sequence of size ", n ," is \n")
	#  n = 15
	task.newmanConwaySequence(n)
end

main()

Output

 Newman-conway sequence of size 10 is 
 1 1 2 2 3 4 4 4 5 6
 Newman-conway sequence of size 15 is 
 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8
/*
    Scala program for
    Newman-conway sequence program
*/
class ConwaySequence()
{
	def newmanConwaySequence(n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		// This is used to collect result
		var record: Array[Int] = Array.fill[Int](n + 1)(0);
		// Set initial value
		record(0) = 0;
		record(1) = 1;
		if (n > 2)
		{
			record(2) = 1;
		}
		var i: Int = 3;
		while (i <= n)
		{
			// Collect Newman-conway sequence
			record(i) = record(record(i - 1)) + record(i - record(i - 1));
			i += 1;
		}
		i = 1;
		while (i <= n)
		{
			// Display the sequence element   
			print(" " + record(i));
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: ConwaySequence = new ConwaySequence();
		// Display size 
		var n: Int = 10;
		print("\n Newman-conway sequence of size " + n + " is \n");
		// n = 10
		task.newmanConwaySequence(n);
		n = 15;
		print("\n Newman-conway sequence of size " + n + " is \n");
		// n = 15
		task.newmanConwaySequence(n);
	}
}

Output

 Newman-conway sequence of size 10 is
 1 1 2 2 3 4 4 4 5 6
 Newman-conway sequence of size 15 is
 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8
/*
    Swift 4 program for
    Newman-conway sequence program
*/
class ConwaySequence
{
	func newmanConwaySequence(_ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		// This is used to collect result
		var record: [Int] = Array(repeating: 0, count: n + 1);
		// Set initial value
		record[0] = 0;
		record[1] = 1;
		if (n > 2)
		{
			record[2] = 1;
		}
		var i: Int = 3;
		while (i <= n)
		{
			// Collect Newman-conway sequence
			record[i] = record[record[i - 1]] + record[i - record[i - 1]];
			i += 1;
		}
		i = 1;
		while (i <= n)
		{
			// Display the sequence element   
			print(" ", record[i], terminator: "");
			i += 1;
		}
	}
}
func main()
{
	let task: ConwaySequence = ConwaySequence();
	// Display size 
	var n: Int = 10;
	print("\n Newman-conway sequence of size ", n ," is ");
	// n = 10
	task.newmanConwaySequence(n);
	n = 15;
	print("\n Newman-conway sequence of size ", n ," is ");
	// n = 15
	task.newmanConwaySequence(n);
}
main();

Output

 Newman-conway sequence of size  10  is
  1  1  2  2  3  4  4  4  5  6
 Newman-conway sequence of size  15  is
  1  1  2  2  3  4  4  4  5  6  7  7  8  8  8
/*
    Kotlin program for
    Newman-conway sequence program
*/
class ConwaySequence
{
	fun newmanConwaySequence(n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		// This is used to collect result
		val record: Array < Int > = Array(n + 1)
		{
			0
		};
		// Set initial value
		record[0] = 0;
		record[1] = 1;
		if (n > 2)
		{
			record[2] = 1;
		}
		var i: Int = 3;
		while (i <= n)
		{
			// Collect Newman-conway sequence
			record[i] = record[record[i - 1]] + record[i - record[i - 1]];
			i += 1;
		}
		i = 1;
		while (i <= n)
		{
			// Display the sequence element   
			print(" " + record[i]);
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: ConwaySequence = ConwaySequence();
	// Display size 
	var n: Int = 10;
	print("\n Newman-conway sequence of size " + n + " is \n");
	// n = 10
	task.newmanConwaySequence(n);
	n = 15;
	print("\n Newman-conway sequence of size " + n + " is \n");
	// n = 15
	task.newmanConwaySequence(n);
}

Output

 Newman-conway sequence of size 10 is
 1 1 2 2 3 4 4 4 5 6
 Newman-conway sequence of size 15 is
 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8

Resultant Output Explanation

Let's analyze the output of the program for two different input sizes: 10 and 15.

Newman-conway sequence of size 10 is
1 1 2 2 3 4 4 4 5 6

For a size of 10, the Newman-Conway sequence begins with 1 1, as these are the initial terms. The subsequent terms are calculated using the previous terms: 2 is obtained by adding the values at index 1 (1) and index 0 (1), 3 is obtained by adding the values at index 2 (2) and index 1 (1), and so on.

Newman-conway sequence of size 15 is
1 1 2 2 3 4 4 4 5 6 7 7 8 8 8

Similarly, for a size of 15, the sequence is extended following the same rules. The terms are calculated based on the previous terms, resulting in the sequence shown above.

The Newman-Conway sequence has a time complexity of O(n) since it requires iterating through the numbers from 3 to n to calculate each term of the sequence.

Congratulations! You now understand the Newman-Conway sequence program. Feel free to explore different input sizes and observe the resulting sequences.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment