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
- Initialize
value
as 1. - If n is 0 or 1, then directly print
value
as the result. - Otherwise, initialize
x
as 1 andy
as 0. - Use a loop to iterate from 2 to n:
- Calculate the new
y
using the formula2 * value + x
. - Update
x
with the previous value ofvalue
. - Update
value
with the new value ofy
.
- Calculate the new
- 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.
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