Tutorialspoint.dev

Print n terms of Newman-Conway Sequence

Newman-Conway numbers is the one which generates the following integer sequence.
1 1 2 2 3 4 4 4 5 6 7 7….. and follows below recursive formula.

P(n) = P(P(n - 1)) + P(n - P(n - 1))

Given a number n then print n terms of Newman-Conway Sequence

Examples:

Input : 13
Output : 1 1 2 2 3 4 4 4 5 6 7 7 8

Input : 20
Output : 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12 


C++

// C++ Program to print n terms 
// of Newman-Conway Sequence
#include <bits/stdc++.h>
using namespace std;
  
// Function to find 
// the n-th element
void sequence(int n) 
{
    // Declare array to store sequence
    int f[n + 1];
    f[0] = 0;
    f[1] = 1;
    f[2] = 1;
      
    cout << f[1] << " " << f[2] << " ";
      
    for (int i = 3; i <= n; i++) {
        f[i] = f[f[i - 1]] + f[i - f[i - 1]];        
        cout << f[i] << " ";
    }
}
  
// Driver Program
int main()
{    
    int n = 13;    
    sequence(n);    
    return 0;
}

Java

// Java Program to print n terms
// of Newman-Conway Sequence
  
class GFG 
{
    // Function to find 
    // the n-th element
    public static void sequence(int n) 
    {
        // Declare array to store sequence
        int f[] = new int[n + 1];
          
        f[0] = 0;
        f[1] = 1;
        f[2] = 1;
          
        System.out.print( f[1] + " " + f[2] + " ");
        for (int i = 3; i <= n; i++) 
        {
            f[i] = f[f[i - 1]] + f[i - f[i - 1]];     
            System.out.print(f[i] + " ");
        }
    }
      
    //Driver code
    public static void main(String []args)
    {
        int n = 13 ;
        sequence(n);
    }
  
}
  
  
// This program is contributed 
// by upendra singh bartwal

Python3

# Python Program to print n terms
# of Newman-Conway Sequence
  
def sequence(n):
  
    # Function to find
    # the n-th element
    # Declare array to store sequence
    f = [0, 1, 1]
  
    print(f[1], end=" "),
    print(f[2], end=" "),
    for i in range(3,n+1):
        f.append( f[f[i - 1]] + f[i - f[i - 1]])
        print(f[i], end=" "),
          
# driver code
n = 13
sequence(n)
  
# This code is contributed
# by upendra singh bartwal

C#

// C# Program to print n terms
// of Newman-Conway Sequence
using System;
class GFG 
{
    // Function to find 
    // the n-th element
    public static void sequence(int n) 
    {
        // Declare array to store sequence
        int []f = new int[n + 1];
          
        f[0] = 0;
        f[1] = 1;
        f[2] = 1;
          
        Console.Write( f[1] + " " + f[2] + " ");
        for (int i = 3; i <= n; i++) 
        {
            f[i] = f[f[i - 1]] + f[i - f[i - 1]]; 
            Console.Write(f[i] + " ");
        }
    }
      
    // Driver code
    public static void Main()
    {
        int n = 13 ;
        sequence(n);
    }
  
}
  
  
// This program is contributed 
// by vt_m.

PHP

<?php
// PHP Program to print n terms 
// of Newman-Conway Sequence
  
// Function to find 
// the n-th element
function sequence($n
{
      
    // Declare array to 
    // store sequence
    $f=array(0);
  
    $f[0] = 0;
    $f[1] = 1;
    $f[2] = 1;
      
    echo $f[1] , " " , $f[2] , " ";
      
    for ($i = 3; $i <= $n; $i++) 
    {
        $f[$i] = $f[$f[$i - 1]] + 
                 $f[$i - $f[$i - 1]];     
        echo $f[$i], " ";
    }
}
  
// Driver Code
    $n = 13; 
    sequence($n); 
    return 0;
}
  
// This code is contributed by nitin mittal.
?>


Output :

1 1 2 2 3 4 4 4 5 6 7 7 8 


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter