How to calculate sum of all permutations of a whole number
Calculate sum of all permutations of a whole number
Calculate sum of permutations of digits problem statement:
Can the reader give the sum of all the whole numbers that can be formed with the four figures 1, 2, 3, 4? That is, the addition of all such numbers as 1,234,1,423,4,312, etc. You can, of course, write them all out and make the addition, but the interest lies in finding a very simple rule for the sum of all the numbers that can be made with four different digits selected in every possible way, but zero excluded ?
There are 2 ways to solve this puzzle, one is to brute force all permutations of the whole number and sum up each of the permutations together which is pretty straightforward, second way is to find a correlation between those permutations and deduce a formula for the same which can be used for any number. We will go through both approaches in this blog.
Below code snippet returns the sum of all permutations of the whole number by brute force:-
The logic behind the above code is fairly simple, it recursively feeds in substrings to the permuteAndCalcSum() function for different prefixes one by one , say for e.g , prefixes like 1,2,3,4 for the string ‘1234’ and repeats the same process recursively for corresponding substrings : 234, 134, 124, 123, breaks down these substrings again into smaller substrings till base condition is met.
Below are the permutations deduced by this function for numbers 123 and 1234
From the above output, it’s very easy to find a correlation between the pattern of digits each of the whole number permutations has!!
In case of 1234, the digit combination which is repeated for each of the permutations of the whole number is
4 4 3 3 2 2
4 4 3 3 1 1
4 4 2 2 1 1
3 3 2 2 1 1
which means 6 times, which is equal to (lengthOfNumber -1) = 4-1 = 3! times each of the digits 1,2,3,4 is repeated..
For number 123, the digit combination is:-
3 3 2 2 1 1
which means 2 times, which is equal to (lengthOfNumber -1) = 3-1 = 2! times each of the digits 1,2,3 is repeated.
if we sum up these digits thus obtained we get sum of each of the digits of the whole number permutations. This can be expressed as the following:
4*6! + 3*6! + 2*6! + 1*6! = (4+3+2+1)*6! = Sum of all the digits * (n-1)! where n = number of digits in the whole number. In this case, as it’s first n natural numbers without any repetition , sum of digits can be represented as n(n+1)/2, so the final formula for sum of each of the digits in unit’s, ten’s, hundred’s and thousand’s place will be n(n+1)/2 * (n-1)!.
Now we have sum represented by each of the digits in the permutation, it’s easy to obtain the sum of all the whole numbers by totalling the face values of each of the digit sums using powers of 10 since it’s a decimal number.
So, final sum of all permutations = [10(n-1) + 10(n-2) +…….+10(n-n)] * Sum of all the digits * (n-1)! = [10(n-1) + 10(n-2) +…….+10(n-n)] * (n(n+1)/2) * (n-1)! ——–(1)
We can use the formula given in equation (1) to compute sum of all possible permutations of a given whole number. This formula also works for whole numbers with repetitive digits in place.
The formula and brute force algorithm are generic and can be applied to any number.
Combining all the above as a single jsfiddle:-
Hope you enjoyed reading this. Like us on Golibrary for interesting reads like this.