Problem 44316. Pandigital Multiples of 11 (based on Project Euler 491)
A "Pandigital number of order X" is one that contains all of the numbers from 0 to X, but with no leading zeroes. If X>9, the cycle 0-9 repeats itself. For example, 2310 is a Pandigital number of order 3 (0-3), while 120345678901 is a Pandigital number of order 11, with the "01" at the end of the number representing 10 and 11, respectively (10 and 11 mod 10, essentially). 0321 is not a Pandigital number, as it has a leading zero.
Given a number X, determine how many pandigital numbers of that order are divisible by 11. You do not need to return the numbers themselves, just how many of them there are.
Solution Stats
Problem Comments
-
13 Comments
I don't think the case for x > 9 is handled correctly. Consider x = 11. My interpretation is that a pandigital number of order 11 will contain exactly two 0's, two 1's and one of every digit 2 through 9. Using a brute force approach, I can check every pandigital number of order 11 and see if it is a multiple of 11:
count = 0;
digs = 0:11;
for d0 = 1:9
strs = unique(perms(char(mod(setdiff(digs, d0), 10) + '0')), 'rows');
nums = str2num([repmat(char(d0 + '0'), size(strs, 1), 1) strs]);
count = count + sum(mod(nums, 11) == 0);
end
Quite simply, this loops over each starting digit, except zero, takes all possible unique permutations of the remaining digits, then counts the number divisible by 11. This yields a solution of 9072000.
Note that this approach is not a suitable answer for Cody, since its runtime is on the order of an hour, but is the simplest way to demonstrate a correct solution for x = 11.
Reggie, I think you may be right, and I think I know what the issue is with my test cases. Sadly, I can't check out my suspicions yet; the machine I need to use with enough memory for a brute force test for x=11 is currently using all 12 cores running very long calculations which are using up about 85% of the available memory. I've disabled the X>9 cases in the solution set for now until I can double check them, so the problem should be much easier now. If your solution works for X<10, go ahead and submit.
to add to the confusion, my (non-brute-force) approach leads to the following counts N(10)=2,246,400 N(11)=22,896,000 and N(14)=26,714,545,200
My combinatoric approach and brute force method both agree for x = 10 with 1454400 and for x = 11 with 9072000. I can't brute force beyond that, but an reasonably I am handling the redundant permutations introduced when we have duplicate digits due to these two cases. For reference, I get 3216477600 for x = 14.
my mistake, my results now match those reported by Reggie, I get N(10)=1,454,400, N(11)=9,072,000, and N(14)=3,216,477,600.
I figured out what the issue was with the code I was using for the test suite - I neglected to put in the check in to make sure that the first set of numbers I was checking hadn't already been calculated by the code. It wasn't a problem when there were no repeats (X<10), but once X>9, repeats started occuring. Since 1-2-3-4-0 and 1-2-3-0-4 were both checked and calculated, that made my values higher than they should have been. (Short version - I forgot a "unique" command.) On the bright side, going through the code line-by-line to figure out what was going on allowed me to make it much, much faster.
And now we know why this one is a hard problem! :-)
Quite right James! It took me some time to fix the repeating combinations error, but it was worth :D
I just feel better knowing that even Alfonso messed up a bit on this one. If he can screw up, what chance do we mere mortals have? ;-)
Project Euler solution for x=19.
It was a real nightmare for me.
Thank you James
Please correct me if I'm wrong. How come pandigitalby11(6)>0. Since the sum of its digits is 21, which can never by a multiple of 11.
Never mind my comment xD
This one took a while.
Pandigital number of order 10 has two 0s and one 1
Pandigital number of order 11 has two 0s and two 1s
Pandigital number of order 12 has two 0s, two 1s and two 2s
Pandigital number of order 13 has two 0s, two 1s, two 2s and two 3s
and so on...It wasn't clear to me at first, and I didn't find on the net anything about the order of pandigital numbers. Moreover, If one needs more examples: pandigit11(9) = 285120; and pandigital(12) = 59875200.
Solution Comments
Show commentsProblem Recent Solvers47
Suggested Problems
-
Sort numbers by outside digits
147 Solvers
-
Determine the number of odd integers in a vector
708 Solvers
-
190 Solvers
-
4096 Solvers
-
82 Solvers
More from this Author80
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!