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)
{
SternDiatomicSeries task = new SternDiatomicSeries();
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
*/
task.printSDS(n);
}
}
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()
{
SternDiatomicSeries *task = new SternDiatomicSeries();
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
*/
task->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
// 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)
{
SternDiatomicSeries task = new SternDiatomicSeries();
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
*/
task.printSDS(n);
}
}
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
*/
task.printSDS(n)
}
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()
{
$task = new SternDiatomicSeries();
$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
*/
$task->printSDS($n);
}
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 task = new SternDiatomicSeries();
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
*/
task.printSDS(n);
}
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() :
task = SternDiatomicSeries()
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
task.printSDS(n)
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()
task = SternDiatomicSeries.new()
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
task.printSDS(n)
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
*/
task.printSDS(n);
}
}
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 task: SternDiatomicSeries = SternDiatomicSeries();
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
*/
task.printSDS(n);
}
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 task: SternDiatomicSeries = SternDiatomicSeries();
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
*/
task.printSDS(n);
}
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.
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