Mathematical Proof to show the divisibility of 11
Consider a Palindromic Number:
Start by considering a palindromic number, denoted as βx,β which possesses an even number of digits.
Letβs express βxβ as:
- x = x1x2xβxββ¦xn-3xn-2xn-1xn, Here, βnβ represents the total number of digits, and it is an even number.
Palindromic Property:
Since βxβ is a palindrome, we can make the following observations:
- x1 equals xn
- x2 equals xn-1
- x3 equals xn-2
- x4 equals xn-3, And so onβ¦
Sum of Digits at Odd and Even Positions:
Now, letβs explore the sums of the digits at odd and even positions within βxβ:
- The sum of digits at odd positions = x1 + x3 + β¦ + xn-3 + xn-1
- The sum of digits at even positions = x2 + x4 + β¦ + xn-2 + xn
Difference between Odd and Even Position Sums:
Next, we calculate the difference between the sum of digits at odd positions and the sum of digits at even positions:
Difference = (x1 + x3 + β¦ + xn-3 + xn-1) β (x2 + x4 + β¦ + xn-2 + xn)
By applying our earlier observations about palindromes, this difference simplifies to:
Difference = (x1 β xn) + (x2 β xn-1) + (x3 β xn-2) + (x4 β xn-3) + β¦
Key Insight:
At this point, we recognize a pattern. Each term in the difference expression pairs up the corresponding digits from the outer ends of βx,β such as x1 with xn, x2 with xn-1, and so forth. Since each pair is identical in a palindrome, the difference between them is always zero.
Divisibility by 11:
Therefore, our final result is:
- Difference = 0
- This means that the difference between the sum of digits at odd positions and the sum of digits at even positions is always zero for an even-digit palindrome βx.β
- As a result, βxβ is divisible by 11, demonstrating the interesting property that all palindromes with an even number of digits are divisible by 11.
Lets take a coding example to show that All palindromes with an even number of digits are divisible by 11:
The idea is to iterate through the string and calculate the sum of the digits at even and sum of digits at odd positions in the string and then check if the absolute difference between these sums is divisible by 11.
Coding example to show that All palindromes with an even number of digits are divisible by 11:
C++
// C++ code for the abovbe approach: #include <iostream> #include <string> using namespace std; // Function to show that the even digit // palindrome is divisible by 11 bool isEvenDigitPalindromeDivisibleBy11(string& str) { int sumOdd = 0; int sumEven = 0; int n = str.length(); for ( int i = 0; i < n; i++) { int digit = str[i] - '0' ; if (i % 2 == 0) { sumEven += digit; } else { sumOdd += digit; } } return ( abs (sumEven - sumOdd) % 11 == 0); } // Drivers code int main() { // An even-digit palindrome divisible by 11 string palindrome1 = "1221" ; // An odd-digit palindrome not divisible by 11 string palindrome2 = "132231" ; // Function Call cout << palindrome1 << " is divisible by 11: " << boolalpha << isEvenDigitPalindromeDivisibleBy11(palindrome1) << endl; cout << palindrome2 << " is divisible by 11: " << boolalpha << isEvenDigitPalindromeDivisibleBy11(palindrome2) << endl; return 0; } |
Java
// Java code for the abovbe approach: import java.util.*; class GFG { // Function to show that the even digit // palindrome is divisible by 11 static boolean isEvenDigitPalindromeDivisibleBy11(String str) { int sumOdd = 0 ; int sumEven = 0 ; int n = str.length(); for ( int i = 0 ; i < n; i++) { int digit = Character.getNumericValue(str.charAt(i)); if (i % 2 == 0 ) { sumEven += digit; } else { sumOdd += digit; } } return (Math.abs(sumEven - sumOdd) % 11 == 0 ); } // Driver code public static void main(String[] args) { // An even-digit palindrome divisible by 11 String palindrome1 = "1221" ; // An odd-digit palindrome not divisible by 11 String palindrome2 = "132231" ; // Function Call System.out.println( palindrome1 + " is divisible by 11: " + isEvenDigitPalindromeDivisibleBy11( palindrome1)); System.out.println( palindrome2 + " is divisible by 11: " + isEvenDigitPalindromeDivisibleBy11( palindrome2)); } } |
Python3
def is_even_digit_palindrome_divisible_by_11(s): sum_even = 0 sum_odd = 0 for i in range ( len (s)): digit = int (s[i]) if i % 2 = = 0 : sum_even + = digit else : sum_odd + = digit return abs (sum_even - sum_odd) % 11 = = 0 if __name__ = = "__main__" : # An even-digit palindrome divisible by 11 palindrome1 = "1221" # An odd-digit palindrome not divisible by 11 palindrome2 = "132231" # Function Calls print (f "{palindrome1} is divisible by 11: {is_even_digit_palindrome_divisible_by_11(palindrome1)}" ) print (f "{palindrome2} is divisible by 11: {is_even_digit_palindrome_divisible_by_11(palindrome2)}" ) |
C#
using System; class Program { // Function to show that the even digit // palindrome is divisible by 11 static bool IsEvenDigitPalindromeDivisibleBy11( string str) { int sumOdd = 0; int sumEven = 0; int n = str.Length; for ( int i = 0; i < n; i++) { int digit = ( int )Char.GetNumericValue(str[i]); if (i % 2 == 0) { sumEven += digit; } else { sumOdd += digit; } } return (Math.Abs(sumEven - sumOdd) % 11 == 0); } // Main method static void Main() { // An even-digit palindrome divisible by 11 string palindrome1 = "1221" ; // An odd-digit palindrome not divisible by 11 string palindrome2 = "132231" ; // Function Call Console.WriteLine($ "{palindrome1} is divisible by 11: {IsEvenDigitPalindromeDivisibleBy11(palindrome1)}" ); Console.WriteLine($ "{palindrome2} is divisible by 11: {IsEvenDigitPalindromeDivisibleBy11(palindrome2)}" ); } } |
Javascript
// JavaScript code for the abovbe approach: // Function to check if an even-digit // palindrome is divisible by 11 function isEvenDigitPalindromeDivisibleBy11(str) { let sumOdd = 0; let sumEven = 0; const n = str.length; for (let i = 0; i < n; i++) { const digit = parseInt(str[i]); if (i % 2 === 0) { sumEven += digit; } else { sumOdd += digit; } } return Math.abs(sumEven - sumOdd) % 11 === 0; } // Driver code // An even-digit palindrome divisible by 11 const palindrome1 = "1221" ; // An odd-digit palindrome not divisible by 11 const palindrome2 = "132231" ; // Function Call console.log(palindrome1 + " is divisible by 11: " + isEvenDigitPalindromeDivisibleBy11(palindrome1)); console.log(palindrome2 + " is divisible by 11: " + isEvenDigitPalindromeDivisibleBy11(palindrome2)); |
1221 is divisible by 11: true 12321 is divisible by 11: false
Time Compexity: O(n), n is the size of string
Auxilary Space: O(1)
G-Fact | All palindromes with an even number of digits are divisible by 11
The statement βAll palindromes with an even number of digits are divisible by 11β is a well-known property in number theory and mathematics. It is an intriguing characteristic of palindromic numbers, which are numbers that read the same forwards and backward. In this context, even-digit palindromes are those numbers with an even number of digits that exhibit a special divisibility property when it comes to the number 11.