Skip to main content

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.

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