From 86498e5c2388957c90b4ba18cd950d90f5ce9c22 Mon Sep 17 00:00:00 2001 From: Eugene Kovko Date: Sat, 25 Oct 2025 19:07:17 +0200 Subject: [PATCH 1/3] BAEL-8806: Initial Padovan example setup --- .../baeldung/padovan/PadovanSeriesUtils.java | 37 +++++++++++++++++++ .../padovan/PadovanSeriesUtilsUnitTest.java | 29 +++++++++++++++ 2 files changed, 66 insertions(+) create mode 100644 core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java create mode 100644 core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java diff --git a/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java b/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java new file mode 100644 index 000000000000..c0a2fc169be0 --- /dev/null +++ b/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java @@ -0,0 +1,37 @@ +package com.baeldung.padovan; + +public class PadovanSeriesUtils { + + public static int nthPadovanTermRecursiveMethod(int n) { + if (n == 0 || n == 1 || n == 2) { + return 1; + } + return nthPadovanTermRecursiveMethod(n - 2) + nthPadovanTermRecursiveMethod(n - 3); + } + + public static int nthPadovanTermIterativeMethod(int n) { + if (n == 0 || n == 1 || n == 2) { + return 1; + } + int p0 = 1, p1 = 1, p2 = 1; + int tempNthTerm; + for (int i = 3; i <= n; i++) { + tempNthTerm = p0 + p1; + p0 = p1; + p1 = p2; + p2 = tempNthTerm; + } + return p2; + } + + public static int nthPadovanTermUsingFormula(int n) { + if (n == 0 || n == 1 || n == 2) { + return 1; + } + // Padovan spiral can be approximated using formula + // More complex than Fibonacci's Binet formula + double p = Math.pow(1.32471795724474602596, n - 1); + return (int) Math.round(p / 1.045356793252532962); + } +} + diff --git a/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java b/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java new file mode 100644 index 000000000000..a4b239ed0e93 --- /dev/null +++ b/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java @@ -0,0 +1,29 @@ +package com.baeldung.padovan; + +import static org.junit.Assert.assertEquals; +import org.junit.Test; + +public class PadovanSeriesUtilsUnitTest { + + @Test + public void givenTermToCalculate_thenReturnThatTermUsingRecursion() { + int term = 10; + int expectedValue = 12; + assertEquals(PadovanSeriesUtils.nthPadovanTermRecursiveMethod(term), expectedValue); + } + + @Test + public void givenTermToCalculate_thenReturnThatTermUsingIteration() { + int term = 10; + int expectedValue = 12; + assertEquals(PadovanSeriesUtils.nthPadovanTermIterativeMethod(term), expectedValue); + } + + @Test + public void givenTermToCalculate_thenReturnThatTermUsingFormula() { + int term = 10; + int expectedValue = 12; + assertEquals(PadovanSeriesUtils.nthPadovanTermUsingFormula(term), expectedValue); + } +} + From 039efb2f6d558b975653f4dd96f7d1a56f1572f9 Mon Sep 17 00:00:00 2001 From: Eugene Kovko Date: Sun, 26 Oct 2025 23:34:31 +0100 Subject: [PATCH 2/3] BAEL-8806: Minor fixes and tests --- .../baeldung/padovan/PadovanSeriesUtils.java | 41 +++++++-- .../padovan/PadovanSeriesUtilsUnitTest.java | 85 +++++++++++++++++-- 2 files changed, 116 insertions(+), 10 deletions(-) diff --git a/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java b/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java index c0a2fc169be0..fcb4b4935255 100644 --- a/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java +++ b/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java @@ -9,7 +9,33 @@ public static int nthPadovanTermRecursiveMethod(int n) { return nthPadovanTermRecursiveMethod(n - 2) + nthPadovanTermRecursiveMethod(n - 3); } - public static int nthPadovanTermIterativeMethod(int n) { + public static int nthPadovanTermRecursiveMethodWithMemoization(int n) { + int[] memo = new int[n + 1]; + if (n == 0 || n == 1 || n == 2) { + return 1; + } + if (memo[n] != 0) { + return memo[n]; + } + memo[n] = nthPadovanTermRecursiveMethodWithMemoization(n - 2) + nthPadovanTermRecursiveMethodWithMemoization(n - 3); + return memo[n]; + } + + public static int nthPadovanTermIterativeMethodWithArray(int n) { + int[] memo = new int[n + 1]; + if (n == 0 || n == 1 || n == 2) { + return 1; + } + memo[0] = 1; + memo[1] = 1; + memo[2] = 1; + for (int i = 3; i <= n; i++) { + memo[i] = memo[i - 2] + memo[i - 3]; + } + return memo[n]; + } + + public static int nthPadovanTermIterativeMethodWithVariables(int n) { if (n == 0 || n == 1 || n == 2) { return 1; } @@ -28,10 +54,15 @@ public static int nthPadovanTermUsingFormula(int n) { if (n == 0 || n == 1 || n == 2) { return 1; } - // Padovan spiral can be approximated using formula - // More complex than Fibonacci's Binet formula - double p = Math.pow(1.32471795724474602596, n - 1); - return (int) Math.round(p / 1.045356793252532962); + + // Padovan spiral constant (plastic number) - the real root of x^3 - x - 1 = 0 + final double PADOVAN_CONSTANT = 1.32471795724474602596; + + // Normalization factor to approximate Padovan sequence values + final double NORMALIZATION_FACTOR = 1.045356793252532962; + + double p = Math.pow(PADOVAN_CONSTANT, n - 1); + return (int) Math.round(p / NORMALIZATION_FACTOR); } } diff --git a/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java b/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java index a4b239ed0e93..8988160d0afd 100644 --- a/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java +++ b/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java @@ -5,25 +5,100 @@ public class PadovanSeriesUtilsUnitTest { + // Test base cases for all methods + @Test + public void givenBaseCases_thenReturnCorrectValues() { + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethod(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethod(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethod(2)); + + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(2)); + + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(2)); + + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(2)); + + assertEquals(1, PadovanSeriesUtils.nthPadovanTermUsingFormula(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermUsingFormula(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermUsingFormula(2)); + } + + // Test recursive method @Test public void givenTermToCalculate_thenReturnThatTermUsingRecursion() { int term = 10; int expectedValue = 12; - assertEquals(PadovanSeriesUtils.nthPadovanTermRecursiveMethod(term), expectedValue); + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermRecursiveMethod(term)); + } + + // Test recursive method with memoization + @Test + public void givenTermToCalculate_thenReturnThatTermUsingRecursionWithMemoization() { + int term = 10; + int expectedValue = 12; + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(term)); + } + + // Test iterative method with array + @Test + public void givenTermToCalculate_thenReturnThatTermUsingIterationWithArray() { + int term = 10; + int expectedValue = 12; + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(term)); } + // Test iterative method with variables @Test - public void givenTermToCalculate_thenReturnThatTermUsingIteration() { + public void givenTermToCalculate_thenReturnThatTermUsingIterationWithVariables() { int term = 10; int expectedValue = 12; - assertEquals(PadovanSeriesUtils.nthPadovanTermIterativeMethod(term), expectedValue); + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(term)); } + // Test formula method @Test public void givenTermToCalculate_thenReturnThatTermUsingFormula() { int term = 10; int expectedValue = 12; - assertEquals(PadovanSeriesUtils.nthPadovanTermUsingFormula(term), expectedValue); + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermUsingFormula(term)); } -} + // Test multiple terms to verify sequence correctness + @Test + public void givenMultipleTerms_thenReturnCorrectSequence() { + // Padovan sequence: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151 + int[] expectedSequence = {1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151}; + + for (int i = 0; i < expectedSequence.length; i++) { + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermRecursiveMethod(i)); + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(i)); + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(i)); + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(i)); + // Formula method may have slight approximation errors for larger terms + if (i < 15) { // Test formula for first 15 terms only + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermUsingFormula(i)); + } + } + } + + // Test that all methods return the same result for the same input + @Test + public void givenSameInput_thenAllMethodsReturnSameResult() { + int term = 15; + + int recursiveResult = PadovanSeriesUtils.nthPadovanTermRecursiveMethod(term); + int memoizedResult = PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(term); + int arrayResult = PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(term); + int variablesResult = PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(term); + + assertEquals(recursiveResult, memoizedResult); + assertEquals(recursiveResult, arrayResult); + assertEquals(recursiveResult, variablesResult); + } +} \ No newline at end of file From cf0b57045c799c858b0b3b48c08baa8cc92b5464 Mon Sep 17 00:00:00 2001 From: Eugene Kovko Date: Sat, 1 Nov 2025 23:58:21 +0100 Subject: [PATCH 3/3] BAEL-8806: Fixed a few issues --- .../java/com/baeldung/padovan/PadovanSeriesUtils.java | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) diff --git a/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java b/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java index fcb4b4935255..41b3052a70e9 100644 --- a/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java +++ b/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java @@ -10,14 +10,21 @@ public static int nthPadovanTermRecursiveMethod(int n) { } public static int nthPadovanTermRecursiveMethodWithMemoization(int n) { - int[] memo = new int[n + 1]; if (n == 0 || n == 1 || n == 2) { return 1; } + int[] memo = new int[n + 1]; + memo[0] = 1; + memo[1] = 1; + memo[2] = 1; + return nthPadovanTermRecursiveMethodWithMemoization(n, memo); + } + + private static int nthPadovanTermRecursiveMethodWithMemoization(int n, int[] memo) { if (memo[n] != 0) { return memo[n]; } - memo[n] = nthPadovanTermRecursiveMethodWithMemoization(n - 2) + nthPadovanTermRecursiveMethodWithMemoization(n - 3); + memo[n] = nthPadovanTermRecursiveMethodWithMemoization(n - 2, memo) + nthPadovanTermRecursiveMethodWithMemoization(n - 3, memo); return memo[n]; }