Newman-Conway Sequence in Java
The Newman-Conway sequence is a sequence of integers as follows:
For n > 2, P(n) = P(P(n-1)) + P(n - P(n-1))
The first few terms of the Newman-Conway sequence are:
1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 9, 10, ...
The task is to find the nth term in the sequence.
Example 1
Input: n = 5
Output: 3
Explanation: For n=5, the sequence value is derived from P(4) + P(5 - P(4)), which is 3.
Example 2
Input: n = 7
Output: 4
Explanation: The 7th term in the sequence is 4, calculated iteratively from the previous terms.
Example 3
Input: n = 12
Output: 7
Explanation: Following the sequence rules, the 12th term is found to be 7.
Example 4
Input: n = 15
Output: 10
Explanation: The 15th term in the Newman-Conway sequence is 10, computed from prior terms.
Approach 1: Using Recursive Approach
The recursive approach directly follows the recursive definition of the sequence. It is simple but inefficient for large inputs due to repeated recalculations.
Algorithm
Step 1: Take an input positive integer n.
Step 2: Base Case:
Step 2.1: If n is 1, return 1.
Step 2.2: If n is 2, return 1.
Step 3: Recursive Case:
Step 3.1: Compute P(n-1) by calling newmanConway(n-1).
Step 3.2: Compute P(n - P(n-1)) by calling newmanConway(n - P(n-1)).
Step 3.3: Compute P(n) as the sum of P(P(n-1)) and P(n - P(n-1)).
Step 4: Return the computed value P(n).
FileName: NewmanConwayRecursive.java
public class NewmanConwayRecursive { // Function to compute the nth number in the Newman-Conway sequence public static int newmanConway(int n) { // Base cases: P(1) and P(2) are both 1 if (n == 1 || n == 2) { return 1; } // Recursive case: P(n) = P(P(n-1)) + P(n - P(n-1)) return newmanConway(newmanConway(n - 1)) + newmanConway(n - newmanConway(n - 1)); } public static void main(String[] args) { int n = 5; // Change this value to compute the nth number System.out.println("The " + n + "th number in the Newman-Conway sequence is: " + newmanConway(n)); } }
Output
The 5th number in the Newman-Conway sequence is: 3
Time Complexity: The time complexity of an algorithm is O(n), where n is the input value. This is because of each number is computed at most once.
Space Complexity: The space complexity of an algorithm is O(n). This is because of the recursion stack depth.
Approach 2: Using Memoization (Top-Down Dynamic Programming) Approach
The approach improves the recursive approach by storing previously computed values in a map (or array) to avoid redundant calculations, thus optimizing performance.
Algorithm
Step 1: Take an input positive integer n.
Step 2: If n is 1 or 2, return 1.
Step 3: If the result for n is already computed (exists in the memo map), return it.
Step 4: Recursive Case:
Step 4.1: Compute P(n-1) and P(n - P(n-1)) recursively.
Step 4.2: Store the result of P(n) in the memo map.
Step 5: Return the value of P(n) from the memo map.
FileName: NewmanConwayMemoization.java
import java.util.HashMap; import java.util.Map; public class NewmanConwayMemoization { // Memoization map to store previously computed values private static Mapmemo = new HashMap<>(); // Function to compute the nth number in the Newman-Conway sequence public static int newmanConway(int n) { // Base cases: P(1) and P(2) are both 1 if (n == 1 || n == 2) { return 1; } // Check if the value for n is already computed and stored in the memo map if (!memo.containsKey(n)) { // Compute the value recursively and store it in the memo map memo.put(n, newmanConway(newmanConway(n - 1)) + newmanConway(n - newmanConway(n - 1))); } // Return the computed value from the memo map return memo.get(n); } public static void main(String[] args) { int n = 5; // Change this value to compute the nth number System.out.println("The " + n + "th number in the Newman-Conway sequence is: " + newmanConway(n)); } }
Output
The 5th number in the Newman-Conway sequence is: 3
Time Complexity: The time complexity of an algorithm is O(n), where n is the input value. This is because of each number is computed at most once.
Space Complexity: The space complexity of an algorithm is O(n). This is because of the storage used by the memo map.