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:
- The first term of the sequence is 1.
- The second term of the sequence is 1.
- 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.
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