# 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)
{
// Find
}
}``````

#### 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()
{
// Find
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)
{
// Find
}
}``````

#### 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()
{
// Find
}
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()
{
// Find
}
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() :
#  Find

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()
#  Find
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
}
}``````

#### 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()
{
// Find
}
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
{
// Find
}``````

#### 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.

## 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.