Posted on by Kalkicode
Code Dynamic Programming

Stern's Diatomic Series

Stern's Diatomic Series is a mathematical sequence that was discovered by Moritz Abraham Stern, a German mathematician, in the early 19th century. The series is generated by starting with the values 0 and 1, and each subsequent term is the sum of the two preceding terms. However, there is a twist in the series: when a new term is odd, it is calculated as the sum of the two closest preceding terms divided by 2 (rounded down). This creates a unique and interesting pattern of numbers.

Problem Statement

The problem is to generate the first 'N' terms of Stern's Diatomic Series. Given a positive integer 'N', we need to calculate and display the first 'N' elements of the series.

For example, if N = 20, the first 20 terms of the Stern's Diatomic Series are:

`0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7`

Pseudocode Algorithm

Let's understand the algorithm to generate the Stern's Diatomic Series:

```1. Define a function printSDS(n) that takes an integer 'n' as input.
2. If n is less than or equal to 0, return from the function.
3. Create an array dp of size n to store the series elements.
4. Set the first element dp[0] as 0.
5. If n is greater than 1, set the second element dp[1] as 1.
6. Iterate from i = 2 to n-1:
a. If i is an even number, set dp[i] as dp[i/2].
b. If i is an odd number, set dp[i] as dp[(i-1)/2] + dp[(i+1)/2].
7. Print "Given N: n" to display the input value.
8. Iterate from i = 0 to n-1 and print dp[i].
```

The time complexity of the algorithm is O(n) because we iterate through the series elements once to calculate each term.

Code Solution

``````/*
C program for
Stern's Diatomic Series
*/
#include <stdio.h>

void printSDS(int n)
{
if (n <= 0)
{
return;
}
int dp[n];
// First element
dp[0] = 0;
if (n > 1)
{
// Second element
dp[1] = 1;
}
for (int i = 2; i < n; ++i)
{
if (i % 2 == 0)
{
// Even numbe
dp[i] = dp[i / 2];
}
else
{
// Odd Number
dp[i] = dp[(i - 1) / 2] + dp[(i + 1) / 2];
}
}
printf("\n Given N : %d\n", n);
// Display calculate sequence
for (int i = 0; i < n; ++i)
{
printf(" %d", dp[i]);
}
}
int main(int argc, char const *argv[])
{
int n = 20;
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
printSDS(n);
return 0;
}``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````
``````// Java program for
// Stern's Diatomic Series
public class SternDiatomicSeries
{
public void printSDS(int n)
{
if (n <= 0)
{
return;
}
int[] dp = new int[n];
// First element
dp[0] = 0;
if (n > 1)
{
// Second element
dp[1] = 1;
}
for (int i = 2; i < n; ++i)
{
if (i % 2 == 0)
{
// Even numbe
dp[i] = dp[i / 2];
}
else
{
// Odd Number
dp[i] = dp[(i - 1) / 2] + dp[(i + 1) / 2];
}
}
System.out.print("\n Given N : " + n + "\n");
// Display calculate sequence
for (int i = 0; i < n; ++i)
{
System.out.print(" " + dp[i]);
}
}
public static void main(String[] args)
{
int n = 20;
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
}
}``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````
``````// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Stern's Diatomic Series
class SternDiatomicSeries
{
public: void printSDS(int n)
{
if (n <= 0)
{
return;
}
int dp[n];
// First element
dp[0] = 0;
if (n > 1)
{
// Second element
dp[1] = 1;
}
for (int i = 2; i < n; ++i)
{
if (i % 2 == 0)
{
// Even numbe
dp[i] = dp[i / 2];
}
else
{
// Odd Number
dp[i] = dp[(i - 1) / 2] + dp[(i + 1) / 2];
}
}
cout << "\n Given N : " << n << "\n";
// Display calculate sequence
for (int i = 0; i < n; ++i)
{
cout << " " << dp[i];
}
}
};
int main()
{
int n = 20;
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
return 0;
}``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````
``````// Include namespace system
using System;
// Csharp program for
// Stern's Diatomic Series
public class SternDiatomicSeries
{
public void printSDS(int n)
{
if (n <= 0)
{
return;
}
int[] dp = new int[n];
// First element
dp[0] = 0;
if (n > 1)
{
// Second element
dp[1] = 1;
}
for (int i = 2; i < n; ++i)
{
if (i % 2 == 0)
{
// Even numbe
dp[i] = dp[i / 2];
}
else
{
// Odd Number
dp[i] = dp[(i - 1) / 2] + dp[(i + 1) / 2];
}
}
Console.Write("\n Given N : " + n + "\n");
// Display calculate sequence
for (int i = 0; i < n; ++i)
{
Console.Write(" " + dp[i]);
}
}
public static void Main(String[] args)
{
int n = 20;
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
}
}``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````
``````package main
import "fmt"
// Go program for
// Stern's Diatomic Series
type SternDiatomicSeries struct {}
func getSternDiatomicSeries() * SternDiatomicSeries {
var me *SternDiatomicSeries = &SternDiatomicSeries {}
return me
}
func(this SternDiatomicSeries) printSDS(n int) {
if n <= 0 {
return
}
var dp = make([] int, n)
// First element
dp[0] = 0
if n > 1 {
// Second element
dp[1] = 1
}
for i := 2 ; i < n ; i++ {
if i % 2 == 0 {
// Even numbe
dp[i] = dp[i / 2]
} else {
// Odd Number
dp[i] = dp[(i - 1) / 2] + dp[(i + 1) / 2]
}
}
fmt.Print("\n Given N : ", n, "\n")
// Display calculate sequence
for i := 0 ; i < n ; i++ {
fmt.Print(" ", dp[i])
}
}
func main() {
var task * SternDiatomicSeries = getSternDiatomicSeries()
var n int = 20
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
}``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````
``````<?php
// Php program for
// Stern's Diatomic Series
class SternDiatomicSeries
{
public	function printSDS(\$n)
{
if (\$n <= 0)
{
return;
}
\$dp = array_fill(0, \$n, 0);
// First element
\$dp[0] = 0;
if (\$n > 1)
{
// Second element
\$dp[1] = 1;
}
for (\$i = 2; \$i < \$n; ++\$i)
{
if (\$i % 2 == 0)
{
// Even numbe
\$dp[\$i] = \$dp[(int)(\$i / 2)];
}
else
{
// Odd Number
\$dp[\$i] = \$dp[(int)((\$i - 1) / 2)] +
\$dp[(int)((\$i + 1) / 2)];
}
}
echo("\n Given N : ".\$n.
"\n");
// Display calculate sequence
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$dp[\$i]);
}
}
}

function main()
{
\$n = 20;
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
}
main();``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````
``````// Node JS program for
// Stern's Diatomic Series
class SternDiatomicSeries
{
printSDS(n)
{
if (n <= 0)
{
return;
}
var dp = Array(n).fill(0);
// First element
dp[0] = 0;
if (n > 1)
{
// Second element
dp[1] = 1;
}
for (var i = 2; i < n; ++i)
{
if (i % 2 == 0)
{
// Even numbe
dp[i] = dp[parseInt(i / 2)];
}
else
{
// Odd Number
dp[i] = dp[parseInt((i - 1) / 2)] +
dp[parseInt((i + 1) / 2)];
}
}
process.stdout.write("\n Given N : " + n + "\n");
// Display calculate sequence
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + dp[i]);
}
}
}

function main()
{
var n = 20;
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
}
main();``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````
``````#  Python 3 program for
#  Stern's Diatomic Series
class SternDiatomicSeries :
def printSDS(self, n) :
if (n <= 0) :
return

dp = [0] * (n)
#  First element
dp[0] = 0
if (n > 1) :
#  Second element
dp[1] = 1

i = 2
while (i < n) :
if (i % 2 == 0) :
#  Even numbe
dp[i] = dp[int(i / 2)]
else :
#  Odd Number
dp[i] = dp[int((i - 1) / 2)] + dp[int((i + 1) / 2)]

i += 1

print("\n Given N : ", n )
i = 0
#  Display calculate sequence
while (i < n) :
print(" ", dp[i], end = "")
i += 1

def main() :
n = 20
#  n = 20
#    0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
#    ---------------------------------------
#    Initial 20 Stern's Diatomic Element

if __name__ == "__main__": main()``````

Output

`````` Given N :  20
0  1  1  2  1  3  2  3  1  4  3  5  2  5  3  4  1  5  4  7``````
``````#  Ruby program for
#  Stern's Diatomic Series
class SternDiatomicSeries
def printSDS(n)
if (n <= 0)
return
end

dp = Array.new(n) {0}
#  First element
dp[0] = 0
if (n > 1)
#  Second element
dp[1] = 1
end

i = 2
while (i < n)
if (i % 2 == 0)
#  Even numbe
dp[i] = dp[i / 2]
else

#  Odd Number
dp[i] = dp[(i - 1) / 2] + dp[(i + 1) / 2]
end

i += 1
end

print("\n Given N : ", n ,"\n")
i = 0
#  Display calculate sequence
while (i < n)
print(" ", dp[i])
i += 1
end

end

end

def main()
n = 20
#  n = 20
#    0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
#    ---------------------------------------
#    Initial 20 Stern's Diatomic Element
end

main()``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````
``````// Scala program for
// Stern's Diatomic Series
class SternDiatomicSeries()
{
def printSDS(n: Int): Unit = {
if (n <= 0)
{
return;
}
var dp: Array[Int] = Array.fill[Int](n)(0);
// First element
dp(0) = 0;
if (n > 1)
{
// Second element
dp(1) = 1;
}
var i: Int = 2;
while (i < n)
{
if (i % 2 == 0)
{
// Even numbe
dp(i) = dp(i / 2);
}
else
{
// Odd Number
dp(i) = dp((i - 1) / 2) + dp((i + 1) / 2);
}
i += 1;
}
print("\n Given N : " + n + "\n");
i = 0;
// Display calculate sequence
while (i < n)
{
print(" " + dp(i));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SternDiatomicSeries = new SternDiatomicSeries();
var n: Int = 20;
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
}
}``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````
``````// Swift 4 program for
// Stern's Diatomic Series
class SternDiatomicSeries
{
func printSDS(_ n: Int)
{
if (n <= 0)
{
return;
}
var dp: [Int] = Array(repeating: 0, count: n);
// First element
dp[0] = 0;
if (n > 1)
{
// Second element
dp[1] = 1;
}
var i: Int = 2;
while (i < n)
{
if (i % 2 == 0)
{
// Even numbe
dp[i] = dp[i / 2];
}
else
{
// Odd Number
dp[i] = dp[(i - 1) / 2] + dp[(i + 1) / 2];
}
i += 1;
}
print("\n Given N : ", n );
i = 0;
// Display calculate sequence
while (i < n)
{
print(" ", dp[i], terminator: "");
i += 1;
}
}
}
func main()
{
let n: Int = 20;
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
}
main();``````

Output

`````` Given N :  20
0  1  1  2  1  3  2  3  1  4  3  5  2  5  3  4  1  5  4  7``````
``````// Kotlin program for
// Stern's Diatomic Series
class SternDiatomicSeries
{
fun printSDS(n: Int): Unit
{
if (n <= 0)
{
return;
}
val dp: Array < Int > = Array(n)
{
0
};
// First element
dp[0] = 0;
if (n > 1)
{
// Second element
dp[1] = 1;
}
var i: Int = 2;
while (i < n)
{
if (i % 2 == 0)
{
// Even numbe
dp[i] = dp[i / 2];
}
else
{
// Odd Number
dp[i] = dp[(i - 1) / 2] + dp[(i + 1) / 2];
}
i += 1;
}
print("\n Given N : " + n + "\n");
i = 0;
// Display calculate sequence
while (i < n)
{
print(" " + dp[i]);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val n: Int = 20;
// n = 20
/*
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
---------------------------------------
Initial 20 Stern's Diatomic Element
*/
}``````

Output

`````` Given N : 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7``````

Resultant Output Explanation

Using the given code, when N is set to 20, the program generates and displays the first 20 terms of Stern's Diatomic Series:

```Given N: 20
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7
```

Each number in the output represents the corresponding term in the Stern's Diatomic Series up to the given value of N.

For example, the first term is 0, followed by 1, 1, 2, 1, 3, and so on. The series exhibits an intriguing pattern where certain terms are repeated, and others are unique.

By understanding and implementing Stern's Diatomic Series, we can explore its properties and applications in various mathematical and computational fields.

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.

Categories
Relative Post