Skip to main content

Find Newman–Shanks–Williams prime

The Newman–Shanks–Williams (NSW) primes are a special class of prime numbers that are generated by a recursive formula. They are named after mathematicians Simon V. Newman, Daniel Shanks, and Hugh C. Williams, who studied these primes. NSW primes are intriguing due to their relation to Fibonacci and Lucas sequences, and they find applications in various areas of mathematics and cryptography.

Problem Statement

The task is to find the n-th NSW prime using a given recursive formula.

Example

Let's take n = 6 as an example. The recursive formula to find the NSW primes is as follows:

NSW(0) = 1
NSW(1) = 1
NSW(n) = 2 * NSW(n-1) + NSW(n-2)

Applying the formula step by step:

  • NSW(2) = 2 * NSW(1) + NSW(0) = 2 * 1 + 1 = 3
  • NSW(3) = 2 * NSW(2) + NSW(1) = 2 * 3 + 1 = 7
  • NSW(4) = 2 * NSW(3) + NSW(2) = 2 * 7 + 3 = 17
  • NSW(5) = 2 * NSW(4) + NSW(3) = 2 * 17 + 7 = 41
  • NSW(6) = 2 * NSW(5) + NSW(4) = 2 * 41 + 17 = 99

Thus, the 6-th NSW prime is 99.

Idea to Solve

The problem can be solved by implementing a function that calculates the n-th NSW prime using the given recursive formula. This involves maintaining two auxiliary variables and iteratively updating them according to the formula.

Pseudocode

function nswPrime(n)
    value = 1
    if n == 0 or n == 1
        print value
    else
        x = 1
        y = 0
        for i from 2 to n
            y = 2 * value + x
            x = value
            value = y
        print n-th NSW prime is value

Algorithm Explanation

  1. Initialize value as 1.
  2. If n is 0 or 1, then directly print value as the result.
  3. Otherwise, initialize x as 1 and y as 0.
  4. Use a loop to iterate from 2 to n:
    • Calculate the new y using the formula 2 * value + x.
    • Update x with the previous value of value.
    • Update value with the new value of y.
  5. Print the n-th NSW prime as value.

Program Solution

// C Program
// Find Newman–Shanks–Williams prime
#include <stdio.h>

void nswPrime(int n)
{
	int value = 1;
	if (n == 0 || n == 1)
	{
		printf("\n  %d", value);
	}
	else
	{
		// Auxiliary variables
		int x = 1;
		int y = 0;
		for (int i = 2; i <= n; ++i)
		{
			y = 2 *value + x;
			x = value;
			value = y;
		}
	}
	// Display calculated result
	printf("\n %d-th Newman–Shanks–Williams prime is : %d", n, value);
}
int main()
{
	// Test
	nswPrime(2);
	nswPrime(6);
	nswPrime(5);
	return 0;
}

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
/*
    Java Program for
    Find Newman–Shanks–Williams Prime
*/
public class NewmanShanksWilliams
{
	public void nswPrime(int n)
	{
		int value = 1;
		if (n == 0 || n == 1)
		{
			System.out.print("\n " + value);
		}
		else
		{
			// Auxiliary variables
			int x = 1;
			int y = 0;
			for (int i = 2; i <= n; ++i)
			{
				y = 2 * value + x;
				x = value;
				value = y;
			}
		}
		// Display calculated result
		System.out.print("\n " + n
              + "-th Newman–Shanks–Williams prime is : " + value);
	}
	public static void main(String[] args)
	{
		NewmanShanksWilliams task = new NewmanShanksWilliams();
		// Find
		task.nswPrime(2);
		task.nswPrime(6);
		task.nswPrime(5);
	}
}

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program for
    Find Newman–Shanks–Williams Prime
*/
class NewmanShanksWilliams
{
	public: void nswPrime(int n)
	{
		int value = 1;
		if (n == 0 || n == 1)
		{
			cout << "\n " << value;
		}
		else
		{
			// Auxiliary variables
			int x = 1;
			int y = 0;
			for (int i = 2; i <= n; ++i)
			{
				y = 2 *value + x;
				x = value;
				value = y;
			}
		}
		// Display calculated result
		cout << "\n " << n 
      		 << "-th Newman–Shanks–Williams prime is : " << value;
	}
};
int main()
{
	NewmanShanksWilliams *task = new NewmanShanksWilliams();
	// Find
	task->nswPrime(2);
	task->nswPrime(6);
	task->nswPrime(5);
	return 0;
}

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
// Include namespace system
using System;
/*
    Csharp Program for
    Find Newman–Shanks–Williams Prime
*/
public class NewmanShanksWilliams
{
	public void nswPrime(int n)
	{
		int value = 1;
		if (n == 0 || n == 1)
		{
			Console.Write("\n " + value);
		}
		else
		{
			// Auxiliary variables
			int x = 1;
			int y = 0;
			for (int i = 2; i <= n; ++i)
			{
				y = 2 * value + x;
				x = value;
				value = y;
			}
		}
		// Display calculated result
		Console.Write("\n " + n + 
                      "-th Newman–Shanks–Williams prime is : " + value);
	}
	public static void Main(String[] args)
	{
		NewmanShanksWilliams task = new NewmanShanksWilliams();
		// Find
		task.nswPrime(2);
		task.nswPrime(6);
		task.nswPrime(5);
	}
}

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
package main
import "fmt"
/*
    Go Program for
    Find Newman–Shanks–Williams Prime
*/

func nswPrime(n int) {
	var value int = 1
	if n == 0 || n == 1 {
		fmt.Print("\n ", value)
	} else {
		// Auxiliary variables
		var x int = 1
		var y int = 0
		for i := 2 ; i <= n ; i++ {
			y = 2 * value + x
			x = value
			value = y
		}
	}
	// Display calculated result
	fmt.Print("\n ", n, 
		"-th Newman–Shanks–Williams prime is : ", value)
}
func main() {
	
	// Find
	nswPrime(2)
	nswPrime(6)
	nswPrime(5)
}

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
<?php
/*
    Php Program for
    Find Newman–Shanks–Williams Prime
*/
class NewmanShanksWilliams
{
	public	function nswPrime($n)
	{
		$value = 1;
		if ($n == 0 || $n == 1)
		{
			echo("\n ".$value);
		}
		else
		{
			// Auxiliary variables
			$x = 1;
			$y = 0;
			for ($i = 2; $i <= $n; ++$i)
			{
				$y = 2 * $value + $x;
				$x = $value;
				$value = $y;
			}
		}
		// Display calculated result
		echo("\n ".$n.
			"-th Newman–Shanks–Williams prime is : ".$value);
	}
}

function main()
{
	$task = new NewmanShanksWilliams();
	// Find
	$task->nswPrime(2);
	$task->nswPrime(6);
	$task->nswPrime(5);
}
main();

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
/*
    Node JS Program for
    Find Newman–Shanks–Williams Prime
*/
class NewmanShanksWilliams
{
	nswPrime(n)
	{
		var value = 1;
		if (n == 0 || n == 1)
		{
			process.stdout.write("\n " + value);
		}
		else
		{
			// Auxiliary variables
			var x = 1;
			var y = 0;
			for (var i = 2; i <= n; ++i)
			{
				y = 2 * value + x;
				x = value;
				value = y;
			}
		}
		// Display calculated result
		process.stdout.write("\n " + n + "-th Newman–Shanks–Williams prime is : " + value);
	}
}

function main()
{
	var task = new NewmanShanksWilliams();
	// Find
	task.nswPrime(2);
	task.nswPrime(6);
	task.nswPrime(5);
}
main();

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
#    Python 3 Program for
#    Find Newman–Shanks–Williams Prime
class NewmanShanksWilliams :
	def nswPrime(self, n) :
		value = 1
		if (n == 0 or n == 1) :
			print("\n ", value, end = "")
		else :
			#  Auxiliary variables
			x = 1
			y = 0
			i = 2
			while (i <= n) :
				y = 2 * value + x
				x = value
				value = y
				i += 1
			
		
		#  Display calculated result
		print("\n ", n ,
              "-th Newman–Shanks–Williams prime is : ", 
              value, end = "",sep="")
	

def main() :
	task = NewmanShanksWilliams()
	#  Find
	task.nswPrime(2)
	task.nswPrime(6)
	task.nswPrime(5)

if __name__ == "__main__": main()

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
#    Ruby Program for
#    Find Newman–Shanks–Williams Prime
class NewmanShanksWilliams 
	def nswPrime(n) 
		value = 1
		if (n == 0 || n == 1) 
			print("\n ", value)
		else
 
			#  Auxiliary variables
			x = 1
			y = 0
			i = 2
			while (i <= n) 
				y = 2 * value + x
				x = value
				value = y
				i += 1
			end

		end

		#  Display calculated result
		print("\n ", n ,
              "-th Newman–Shanks–Williams prime is : ", value)
	end

end

def main() 
	task = NewmanShanksWilliams.new()
	#  Find
	task.nswPrime(2)
	task.nswPrime(6)
	task.nswPrime(5)
end

main()

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
/*
    Scala Program for
    Find Newman–Shanks–Williams Prime
*/
class NewmanShanksWilliams()
{
	def nswPrime(n: Int): Unit = {
		var value: Int = 1;
		if (n == 0 || n == 1)
		{
			print("\n " + value);
		}
		else
		{
			// Auxiliary variables
			var x: Int = 1;
			var y: Int = 0;
			var i: Int = 2;
			while (i <= n)
			{
				y = 2 * value + x;
				x = value;
				value = y;
				i += 1;
			}
		}
		// Display calculated result
		print("\n " + n + 
              "-th Newman–Shanks–Williams prime is : " + value);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: NewmanShanksWilliams = new NewmanShanksWilliams();
		// Find
		task.nswPrime(2);
		task.nswPrime(6);
		task.nswPrime(5);
	}
}

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
/*
    Swift 4 Program for
    Find Newman–Shanks–Williams Prime
*/
class NewmanShanksWilliams
{
	func nswPrime(_ n: Int)
	{
		var value: Int = 1;
		if (n == 0 || n == 1)
		{
			print("\n ", value, terminator: "");
		}
		else
		{
			// Auxiliary variables
			var x: Int = 1;
			var y: Int = 0;
			var i: Int = 2;
			while (i <= n)
			{
				y = 2 * value + x;
				x = value;
				value = y;
				i += 1;
			}
		}
		// Display calculated result
		print("\n ", n ,
              "-th Newman–Shanks–Williams prime is : ", 
              value,separator:"", terminator: "");
	}
}
func main()
{
	let task: NewmanShanksWilliams = NewmanShanksWilliams();
	// Find
	task.nswPrime(2);
	task.nswPrime(6);
	task.nswPrime(5);
}
main();

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41
/*
    Kotlin Program for
    Find Newman–Shanks–Williams Prime
*/
class NewmanShanksWilliams
{
	fun nswPrime(n: Int): Unit
	{
		var value: Int = 1;
		if (n == 0 || n == 1)
		{
			print("\n " + value);
		}
		else
		{
			// Auxiliary variables
			var x: Int = 1;
			var y: Int ;
			var i: Int = 2;
			while (i <= n)
			{
				y = 2 * value + x;
				x = value;
				value = y;
				i += 1;
			}
		}
		// Display calculated result
		print("\n " + n + "-th Newman–Shanks–Williams prime is : " + value);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: NewmanShanksWilliams = NewmanShanksWilliams();
	// Find
	task.nswPrime(2);
	task.nswPrime(6);
	task.nswPrime(5);
}

Output

 2-th Newman–Shanks–Williams prime is : 3
 6-th Newman–Shanks–Williams prime is : 99
 5-th Newman–Shanks–Williams prime is : 41

Time Complexity

The time complexity of the algorithm is O(n) since we are performing a loop from 2 to n, and within each iteration, we are performing constant time operations. The space complexity is O(1) as we are using only a few auxiliary variables regardless of the input size.

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