mersenneforum.org - An Unurned Sum

[SPOILER]You only need to generate all the possible combinations of the n digits. As soon as you find a combination of k digits who's sum is divisible by n you know that there are k! ways of arranging those digits and (n-k)! ways of arranging the remaining ones. Hence you have found k!(n-k)! solutions in one test.
However there is a complication, see the example below.

for k = 1 to n
1) Generate all possible combinations of k out of n numbers
2) increment count by k!(n-k)! for each combination who's sum is divisible by n, but see note below.
3) increment k
4) repeat steps 1 to 4 for all remaining combinations.

Thus, take the easy case of n=4
count=0
k=1
1 - no
2 - no
3 - no
4 - yes count= count + 1!*3! = 6
k=2
1,2 - no
1,3 - yes count= count + 2!*2! = 10
1,4 - no
2,3 - no
2,4 - no
3,4 - no
k=3
1,2,3 - no
1,2,4 - no
1,3,4 - yes, but counts as only 2, count = count + 2 = 12 *
2,3,4
k=4
1,2,3,4 - no
done

* Only count these as 2 rather than 3!. If you find a combination of k digits where sum is divisible by n AND sum/n > 1 you test all the sub-combinations of those k digits to see if any match the previously marked shorter combinations and adjust the contribution accordingly. So if a sub-combination of j of the k digits is also divisible by n then only count (k-j)!(n-k)!2!. The 2! is because the two groups of number can be arranged in 2! ways.
In the case of 1,3,4 k=3 and each has a subset 1,3 so j=2, therefore count (3-2)!(4-3)!2! = 2 .

Note that this only requires 14 steps rather than 24 for a brute force attack and I'm pretty certain the as n increases the advantage becomes greater.

Anyone out there see how to simplify the additional test step?

Further musings

Question - if sum/n > 1 will there ALWAYS be a sub-combination divisible by n?
In the case of 4 the answer is yes.

Can we use the information that if you find a sub-combination divisible by n, but not containing n then appending n to that combination will generate a new combination that is also divisible by n. Example, append 4 to 1,3 gives 1,3,4.

Would an attack that first found all combinations of digits that added up to n and then worked on combinations of these subsets work? You could only count the mutually exclusive combinations - maybe.
So n=6 has combinations 6 1,5 2,4 & 1,2,3.
6 counts as 1!5! = 120
1,5 counts as 2!4! = 48
2,4 counts as 2!4! = 48
1,2,3 counts as 3!3! = 36

1,5 & 6 counts as 2!3! = 12
2,4 & 6 counts as 2!3! = 12
1,2,3 & 6 counts as 3!2! = 12
1,5 & 2,4 counts as 2!2! = 4 - no it's 32 using pencil and paper! All 16 combinations of the 4 digits not starting 1,5 or 2,4 which have already been taken into account and the remaining 2 digits 3,6 can be arranged in 2! ways.

But these do not add up to the known answer of 440, so I've missed something, such as 3,4,5 (=12) which has no subset divisible by 6 and counts as 3!3! = 36. Well that answers my above question! Then all 9 combinations of 3,4,5,6 that don't start 6 or 3,4,5 count as 18.[/SPOILER]