In this article, we will discuss Nicomachus’s Theorem (Sum of k-th group of odd positive numbers) in C++ with its different approaches. Before going to its approaches, we must know something about Nicomachus’s Theorem in C++ .
Explaining Nicomachus’s Theorem using an Example
A square of k equals the sum of numbers from 1 to k, which are odd positive integers. In mathematical notation, the theorem can be expressed as 1+3+5+⋯+(2k−1)=k 2 .
For example:
The sum of 1, 3, 5, the 1st 3 odd numbers, is 9 = 3 2 .
The sum for the first 5 odd numbers (1+3+5+7+9 = 25) is also 25 and 5 2 .
This elegant result displays that simple arithmetic operations expose the intrinsic symmetry of numbers and can yield deeper mathematical truths.
Approach-1: Mathematical Inductions
Mathematical induction is a very powerful way to prove statements about natural numbers. It involves two key steps: the inductive step and the base case.
- Base Case: First, we prove that the statement is true for the smallest k (usually k = 1) that appears.
- Inductive Step: In this step, we prove that if the statement holds for some arbitrary k=n (the inductive hypothesis), it must be true for k=n+1.
Following this, it is shown that it is true for all natural numbers k, and that is done by completing each subsequent value from the base case.
When translating mathematical induction to programming, we run these steps to verify a theorem. For instance, consider Niomachus’ theorem, that the sum of the first k odd numbers is k 2 , onto which we can put code directly. After that, we check the base case (k=1), i.e., the sum of the first odd number 1 is 1 2 . We prove next that the sum for k=n+1 is also equal to (n+1) ^{2} and proceed thus assuming the theorem for k=n.
It can be applied to programming as well, using recursion, loops, etc. Instead of summing each number and comparing it to k 2 , we sum the first k odd numbers, set that equal to k 2 , compare that to the next value, and repeat. The method works in a similar way as mathematical induction so that the theorem will hold for all values of k.
Example:
Let us take an example to illustrate the Nicomachus’s theorem in C++ using Mathematical induction approach.
Example
#include <iostream>
#include <cmath> // For pow() function
#include <iomanip> // For formatted output
// Function to calculate the sum of the first k odd numbers
int sumOddNumbers(int k) {
int sum = 0;
for (int i = 1; i <= k; ++i) {
sum += (2 * i - 1); // Odd number formula: 2*i - 1
}
return sum;
}
// Function to verify the base case of Nicomachus' theorem (k=1)
bool verifyBaseCase() {
int sum = sumOddNumbers(1); // The sum of the first odd number
int square = pow(1, 2); // Square of 1, which is 1^2
std::cout << "Base Case Check: Sum = " << sum << ", 1^2 = " << square << std::endl;
return sum == square;
}
// Function to verify the inductive hypothesis and step
bool verifyInductiveStep(int k) {
// Base case already checked before this function call
int sum = sumOddNumbers(k);
int square = pow(k, 2); // k^2
std::cout << "Inductive Hypothesis Check: Sum of first " << k << " odd numbers = " << sum
<< ", k^2 = " << square << std::endl;
// Now check the inductive step: sum of first k+1 odd numbers equals (k+1)^2
int sumNext = sumOddNumbers(k + 1);
int squareNext = pow(k + 1, 2); // (k+1)^2
std::cout << "Inductive Step Check: Sum of first " << k + 1 << " odd numbers = " << sumNext
<< ", (k+1)^2 = " << squareNext << std::endl;
return sumNext == squareNext;
}
// Function to verify the theorem for all values from 1 to maxK
void inductionVerification(int maxK) {
if (!verifyBaseCase()) {
std::cout << "Base case failed. Nicomachus' theorem does not hold for k = 1." << std::endl;
return;
}
for (int k = 1; k <= maxK; ++k) {
std::cout << "\nVerifying for k = " << k << "..." << std::endl;
if (!verifyInductiveStep(k)) {
std::cout << "Inductive step failed for k = " << k << ". Nicomachus' theorem does not hold for k = " << k << "." << std::endl;
return;
}
}
std::cout << "\nInduction completed successfully. Nicomachus' theorem holds for all k from 1 to " << maxK << "." << std::endl;
}
// Function to print the sum of odd numbers up to k in a table format
void printSumTable(int maxK) {
std::cout << "\nSum of Odd Numbers up to k:\n";
std::cout << std::setw(10) << "k" << std::setw(25) << "Sum of Odd Numbers" << std::setw(15) << "k^2" << std::endl;
std::cout << "-----------------------------------------------\n";
for (int k = 1; k <= maxK; ++k) {
int sum = sumOddNumbers(k);
int square = pow(k, 2);
std::cout << std::setw(10) << k << std::setw(25) << sum << std::setw(15) << square << std::endl;
}
}
// Function to check and print the detailed verification for k
void detailedVerification(int k) {
std::cout << "\nDetailed Verification for k = " << k << ":\n";
int sum = sumOddNumbers(k);
int square = pow(k, 2); // k^2
std::cout << "Sum of the first " << k << " odd numbers: " << sum << std::endl;
std::cout << "k^2 (square of " << k << "): " << square << std::endl;
if (sum == square) {
std::cout << "The theorem holds for k = " << k << ".\n";
} else {
std::cout << "The theorem does not hold for k = " << k << ".\n";
}
// Checking next k (k+1)
int sumNext = sumOddNumbers(k + 1);
int squareNext = pow(k + 1, 2); // (k+1)^2
std::cout << "Sum of the first " << k + 1 << " odd numbers: " << sumNext << std::endl;
std::cout << "(k+1)^2 (square of " << k + 1 << "): " << squareNext << std::endl;
if (sumNext == squareNext) {
std::cout << "The theorem holds for k = " << k + 1 << ".\n";
} else {
std::cout << "The theorem does not hold for k = " << k + 1 << ".\n";
}
}
// Function to demonstrate sum of odd numbers for a larger value of k
int optimizedSumOddNumbers(int k) {
return k * k;
}
int main() {
int maxK;
std::cout << "Enter the value of k up to which to verify Nicomachus' theorem: ";
std::cin >> maxK;
// Induction verification for range of k
inductionVerification(maxK);
// Print sum table for the first 'maxK' odd numbers and check k^2
printSumTable(maxK);
// Alternatively, simulate detailed verification for each k
for (int k = 1; k <= maxK; ++k) {
detailedVerification(k);
}
// Optimized verification for large k values (based on k^2 formula)
std::cout << "\nOptimized verification for large k values:\n";
for (int k = 1; k <= maxK; ++k) {
int sum = optimizedSumOddNumbers(k);
std::cout << "Sum of first " << k << " odd numbers (Optimized): " << sum << ", k^2 = " << k * k << std::endl;
}
return 0;
}
Output:
Output
Enter the value of k up to which to verify Nicomachus' theorem: 3
Base Case Check: Sum = 1, 1^2 = 1
Verifying for k = 1...
Inductive Hypothesis Check: Sum of first 1 odd numbers = 1, k^2 = 1
Inductive Step Check: Sum of first 2 odd numbers = 4, (k+1)^2 = 4
Verifying for k = 2...
Inductive Hypothesis Check: Sum of first 2 odd numbers = 4, k^2 = 4
Inductive Step Check: Sum of first 3 odd numbers = 9, (k+1)^2 = 9
Verifying for k = 3...
Inductive Hypothesis Check: Sum of first 3 odd numbers = 9, k^2 = 9
Inductive Step Check: Sum of first 4 odd numbers = 16, (k+1)^2 = 16
Induction completed successfully. Nicomachus' theorem holds for all k from 1 to 3.
Sum of Odd Numbers up to k:
k Sum of Odd Numbers k^2
-----------------------------------------------
1 1 1
2 4 4
3 9 9
Detailed Verification for k = 1:
Sum of the first 1 odd numbers: 1
k^2 (square of 1): 1
The theorem holds for k = 1.
Sum of the first 2 odd numbers: 4
(k+1)^2 (square of 2): 4
The theorem holds for k = 2.
Detailed Verification for k = 2:
Sum of the first 2 odd numbers: 4
k^2 (square of 2): 4
The theorem holds for k = 2.
Sum of the first 3 odd numbers: 9
(k+1)^2 (square of 3): 9
The theorem holds for k = 3.
Detailed Verification for k = 3:
Sum of the first 3 odd numbers: 9
k^2 (square of 3): 9
The theorem holds for k = 3.
Sum of the first 4 odd numbers: 16
(k+1)^2 (square of 4): 16
The theorem holds for k = 4.
Optimized verification for large k values:
Sum of first 1 odd numbers (Optimized): 1, k^2 = 1
Sum of first 2 odd numbers (Optimized): 4, k^2 = 4
Sum of first 3 odd numbers (Optimized): 9, k^2 = 9
Explanation:
- sumOddNumbers(int k) This function calculates the sum of the first k-odd integers or numbers. The formula for the nth odd number is 2i −1, where i is the index of the sequence, and i starts at 1. At the first iteration, we run through the first ‘k’ odd numbers, adding them together and returning the summation.
- verifyBaseCase This function checks the base case of mathematical induction for k=1. It compares the sum of the first odd number (which is 1) to 1, (which is also 1). If they match, the base case is valid, and the theorem holds for k=1.
- verifyInductiveStep(int k) In this function, we first check that the sum of the first k odd numbers equals k2. After that, we verify the inductive step by ensuring that the sum of the first k+1 odd numbers equals (k+1) 2. This process ensures that the theorem holds for k+1 if it holds for k.
- inductionVerification(int maxK) This function performs the induction verification process for all values from 1 to maxK. It first verifies the base case and then checks the inductive step for each k up to maxK. If the theorem fails at any point, it halts and outputs an error.
- printSumTable(int maxK) This function prints a formatted table displaying the sum of odd numbers up to k and the corresponding value of k^2 for each k from 1 to maxK. The table is printed in a nice format by adjusting the width of column entries with the help of the setw function of <iomanip>.
- detailedVerification(int k) It provides an individual theorem for a particular k and gives a detailed output of the sum of the odd numbers against k^2. It also includes an assertion k+1, and to prove the theorem is step by step.
- optimizedSumOddNumbers(int k) Similar to previous functions, this function calculates the sum of the first k odd numbers directly from the formula as 𝑘^2.
Complexity Analysis:
Time Complexity:
- sumOddNumbers(int k): It iterates over the first k odd numbers. The loop is run k times, and in each iteration, we do a constant time operation, that is, (adding an odd number). Hence, the time complexity is O(k).
- verifyBaseCase: This function only does the base case for k=1, which compares the sum (1) to 2. These are all constant-time operations, so time complexity becomes O(1).
- verifyInductiveStep(int k): The first one is a function that calculates the sum of the first k odd numbers, which compares it with k 2 (which takes O(k) as sumOddNumbers(k) is called). Secondly, it performs the same steps for k+1, and its complexity stays O(k) for each verification.
Space Complexity:
Each function is dominated by storage for the variables and, therefore, by space complexity. Since all our functions just use constant space (sums and counters, for example), space complexity is O(1) except for input and output data.
Approach-2: Formula Based Approach
Nicomachus’s Theorem states that the sum of the first k odd numbers is equal to k 2 . The sum of the first k odd numbers can be expressed directly as: S(k)=1+3+5+⋯+(2k−1)=k 2 .
Instead of summing each odd number individually, we can calculate the sum using the formula directly. For this, we simply need to compare the result of k 2 with the sum computed using the direct mathematical formula for the sum of the first k-odd numbers.
Example:
Let us take an example to illustrate the Nicomachus’s theorem in C++ using formula based approach.
Example
#include <iostream>
#include <iomanip>
#include <cmath> // For pow() function
// Function to calculate the sum of the first k odd numbers using the formula
int sumOddNumbers(int k) {
return k * k; // The sum of the first k odd numbers is k^2
}
// Function to calculate the sum of first k odd numbers using an iterative approach
int sumOddNumbersIterative(int k) {
int sum = 0;
for (int i = 1; i <= k; ++i) {
sum += (2 * i - 1); // Sum the odd numbers: 1, 3, 5, ...
}
return sum;
}
// Function to verify Nicomachus' theorem using the formula approach
void verifyTheoremFormula(int maxK) {
std::cout << "\nVerifying Nicomachus' Theorem using the mathematical formula:\n";
for (int k = 1; k <= maxK; ++k) {
// Calculate the sum using the formula k^2
int sum = sumOddNumbers(k);
// Calculate k^2 for comparison
int square = pow(k, 2); // k^2
std::cout << "For k = " << k << ":\n";
std::cout << "Sum of first " << k << " odd numbers (calculated): " << sum << std::endl;
std::cout << "k^2 (calculated): " << square << std::endl;
if (sum == square) {
std::cout << "The theorem holds for k = " << k << ".\n";
} else {
std::cout << "The theorem does not hold for k = " << k << ".\n";
}
}
}
// Function to verify Nicomachus' theorem using the iterative approach
void verifyTheoremIterative(int maxK) {
std::cout << "\nVerifying Nicomachus' Theorem using the iterative approach:\n";
for (int k = 1; k <= maxK; ++k) {
// Calculate the sum using the iterative method
int sum = sumOddNumbersIterative(k);
// Calculate k^2 for comparison
int square = pow(k, 2); // k^2
std::cout << "For k = " << k << ":\n";
std::cout << "Sum of first " << k << " odd numbers (iterative): " << sum << std::endl;
std::cout << "k^2 (calculated): " << square << std::endl;
if (sum == square) {
std::cout << "The theorem holds for k = " << k << ".\n";
} else {
std::cout << "The theorem does not hold for k = " << k << ".\n";
}
}
}
// Function to display a table of odd numbers and their sums for verification
void printSumTable(int maxK) {
std::cout << "\nSum of first k odd numbers for k = 1 to " << maxK << ":\n";
std::cout << std::setw(10) << "k" << std::setw(30) << "Sum of first k odd numbers" << std::setw(20) << "k^2\n";
for (int k = 1; k <= maxK; ++k) {
int sum = sumOddNumbers(k);
int square = pow(k, 2);
std::cout << std::setw(10) << k << std::setw(30) << sum << std::setw(20) << square << std::endl;
}
}
// Function for input validation and to ensure the value of maxK is positive
int getMaxK() {
int maxK;
while (true) {
std::cout << "Enter the value of k (positive integer) up to which to verify Nicomachus' theorem: ";
std::cin >> maxK;
if (std::cin.fail() || maxK <= 0) {
std::cin.clear(); // Clears the error flag
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // Ignores invalid input
std::cout << "Invalid input. Please enter a positive integer.\n";
} else {
break;
}
}
return maxK;
}
int main() {
int maxK = getMaxK(); // Input validation for maxK
// Verify the theorem using both approaches
verifyTheoremFormula(maxK); // Verification using the formula approach
verifyTheoremIterative(maxK); // Verification using the iterative approach
// Print the sum table for k = 1 to maxK
printSumTable(maxK); // it display a table showing the sum of odd numbers and k^2
return 0;
}
Output:
Output
Enter the value of k (positive integer) up to which to verify Nicomachus' theorem: 3
Verifying Nicomachus' Theorem using the mathematical formula:
For k = 1:
Sum of first 1 odd number (calculated): 1
k^2 (calculated): 1
The theorem holds for k = 1.
For k = 2:
Sum of first 2 odd numbers (calculated): 4
k^2 (calculated): 4
The theorem holds for k = 2.
For k = 3:
Sum of first 3 odd numbers (calculated): 9
k^2 (calculated): 9
The theorem holds for k = 3.
Verifying Nicomachus' Theorem using the iterative approach:
For k = 1:
Sum of first 1 odd numbers (iterative): 1
k^2 (calculated): 1
The theorem holds for k = 1.
For k = 2:
Sum of first 2 odd numbers (iterative): 4
k^2 (calculated): 4
The theorem holds for k = 2.
For k = 3:
Sum of first 3 odd numbers (iterative): 9
k^2 (calculated): 9
The theorem holds for k = 3.
Sum of first k odd numbers for k = 1 to 3:
k Sum of first k odd numbers k^2
1 1 1
2 4 4
3 9 9
Explanation:
- The sumOddNumbersIterative(int k) function sums first k odd numbers by iterating over them one by one. It will help us to see how to get the result as well.
- The verifyTheoremFormula(int maxK) function runs the theorem formula for all values k from 1 to maxK and then verifies. After that, we prove that the formula we calculate for the sum as formula 𝑘^2 for each k found (which we denote verifyTheoremIterative) is equal to k2, since the theorem is correct for any k.
- The printSumTable(int maxK) function adds a visual representation to the results of the table. Each pair has a sum of 𝑘 odd numbers up to 𝑘th (as calculated) and 𝑘^2 next to it.
- In the getMaxK function, we prompt the user to enter a positive integer. If the input is invalid, we repeatedly ask until a valid input is provided. Once a valid number is entered, we print the results, handle the user input appropriately, and call the necessary functions to test the theorem and display the results.
Complexity Analysis:
Time Complexity:
- The functions sumOddNumbers and sumOddNumbersIterative are dictate the complexity of the code. It computes the sum using the direct formula, k^2, which is a constant time operation, so now it is O(1). The other hand is sumOddNumbersIterative(int k), which loops through the first k odd numbers and does addition for each of them, so it is O(k) time complexity. Using the direct formula k^2, which is a constant-time operation, its time complexity is O(1).
- On the other hand, the sumOddNumbersIterative(int k) function involves looping through the first k odd numbers and performing an addition operation for each, resulting in a time complexity of O(k).
- For each k, the sumOddNumbers(k) function has O(1) complexity. The verifyTheoremFormula(int maxK) function iterates from 1. This function’s total complexity is O(maxK).
- Similarly, the sumOddNumbersIterative calls itself for each k, which gives us an O(k⋅maxK) time because the latter ones run O(k) for each one.
- The printSumTable(int maxK) is a function that will iterate from 1 to maxK, doing a constant time operation for every k. Therefore, the complexity of this algorithm becomes O(maxK).
Space Complexity:
- The program’s space complexity is O(1) because it uses constant memory to perform things like integers, doesn’t use memory-intensive operations, and doesn’t utilize any extra data structures .