Largest number divisible by its digits: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Add a Perl 6 example) |
Thundergnat (talk | contribs) m (→Base 10: fix typos) |
||
Line 19: | Line 19: | ||
===Base 10=== |
===Base 10=== |
||
The number can not have a zero in it, that implies that |
The number can not have a zero in it, that implies that it can not have a 5 either since if it has a 5, it must be divisible by 5, but the only numbers divisible by 5 end in 5 or 0. It can't be zero, and if it is odd, it can't be divisible by 2, 4, 6 or 8. So that leaves 98764321 as possible digits the number can contain. The sum of those 8 digits is not divisible by three so the largest possible integer must use no more than 7 of them. So, strictly by removing possibilities that cannot possibly work we are down to at most 7 digits. |
||
In order to |
In order to accommodate the most possible digits, the number must be divisible by 7, 8 and 9. If that is true than it is automatically divisible by 2, 3, 4, & 6 as they can all be made from the combinations of multiples of 2 and 3 which are present in 8 & 9. So we'll only bother to check multiples of 9 * 8 * 7 or 504. |
||
All of this optimizations get the run time to well under 1 second. |
All of this optimizations get the run time to well under 1 second. |
Revision as of 23:08, 1 September 2017
- Task
Find the largest base 10 integer whose digits are all different, that is evenly divisible by each of its individual digits.
For example: 135 is evenly divisible by 1, 3 and 5.
Note that the digit zero (0) can not be in the number as integer division by zero is undefined. The digits must all be unique so a base 10 number will have at most 9 digits.
Feel free to use analytics and clever algorithms to reduce the search space your example needs to visit, but it must do an actual search. (Don't just feed it the answer and verify it is correct.)
- Stretch goal
Do the same thing for hexadecimal.
Perl 6
Base 10
The number can not have a zero in it, that implies that it can not have a 5 either since if it has a 5, it must be divisible by 5, but the only numbers divisible by 5 end in 5 or 0. It can't be zero, and if it is odd, it can't be divisible by 2, 4, 6 or 8. So that leaves 98764321 as possible digits the number can contain. The sum of those 8 digits is not divisible by three so the largest possible integer must use no more than 7 of them. So, strictly by removing possibilities that cannot possibly work we are down to at most 7 digits.
In order to accommodate the most possible digits, the number must be divisible by 7, 8 and 9. If that is true than it is automatically divisible by 2, 3, 4, & 6 as they can all be made from the combinations of multiples of 2 and 3 which are present in 8 & 9. So we'll only bother to check multiples of 9 * 8 * 7 or 504.
All of this optimizations get the run time to well under 1 second.
<lang perl6>my $magic-number = 9*8*7; # 504
my $div = 9876432 div $magic-number * $magic-number; #largest 7 digit multiple of 504 < 9876432
for $div, { $_ - $magic-number } ... 0 -> $test {
next if $test ~~ / <[05]> /; # skip numbers containing 0 or 5 next if $test ~~ / (.).*$0 /; # skip numbers with non unique digits next unless all $test.comb.map: { $test %% $_ }; # skip numbers that don't divide evenly by all digits
say "Found $test"; # Found a solution, display it for $test.comb { printf "%s / %s = %s\n", $test, $_, $test / $_; } exit
}</lang>
- Output:
Found 9867312 9867312 / 9 = 1096368 9867312 / 8 = 1233414 9867312 / 6 = 1644552 9867312 / 7 = 1409616 9867312 / 3 = 3289104 9867312 / 1 = 9867312 9867312 / 2 = 4933656
Base 16
There are fewer analytical optimizations available for base 16. Other than 0, no digits can be ruled out so a much larger space must be searched. Rather than using a magic number to try to filter the search space and then check for uniqueness, we'll just generate unique permutations and check them for divisibility. In practice this seems to be much faster. We'll start at the largest possible permutation (FEDCBA987654321) and work down so as soon as we find a solution, we know it is the solution
<lang perl6>my $hex = 'FEDCBA987654321'; # largest possible hex number
my %hex = (flat 1..9, 'A'..'F') Z=> flat 1..15; # pre-calculate hex to decimal values
for $hex.comb.permutations -> @test {
my $test = [~] @test; my $num = $test.parse-base(16);
next unless all @test.map: { $num %% %hex{$_} };
say "Found $test"; # Found a solution, display it say ' ' x 12, 'In base 16', ' ' x 36, 'In base 10'; for @test { printf "%s / %s = %s | %d / %2d = %19d\n", $test, $_, ($num / %hex{$_}).base(16), $num, %hex{$_}, $num / %hex{$_}; } exit
}</lang>
- Output:
Found FEDCB59726A1348 In base 16 In base 10 FEDCB59726A1348 / F = 10FDA5B4BE4F038 | 1147797065081426760 / 15 = 76519804338761784 FEDCB59726A1348 / E = 1234561D150B83C | 1147797065081426760 / 14 = 81985504648673340 FEDCB59726A1348 / D = 139AD2E43E0C668 | 1147797065081426760 / 13 = 88292081929340520 FEDCB59726A1348 / C = 153D0F21EDE2C46 | 1147797065081426760 / 12 = 95649755423452230 FEDCB59726A1348 / B = 172B56538F25ED8 | 1147797065081426760 / 11 = 104345187734675160 FEDCB59726A1348 / 5 = 32F8F11E3AED0A8 | 1147797065081426760 / 5 = 229559413016285352 FEDCB59726A1348 / 9 = 1C5169829283B08 | 1147797065081426760 / 9 = 127533007231269640 FEDCB59726A1348 / 7 = 2468AC3A2A17078 | 1147797065081426760 / 7 = 163971009297346680 FEDCB59726A1348 / 2 = 7F6E5ACB93509A4 | 1147797065081426760 / 2 = 573898532540713380 FEDCB59726A1348 / 6 = 2A7A1E43DBC588C | 1147797065081426760 / 6 = 191299510846904460 FEDCB59726A1348 / A = 197C788F1D76854 | 1147797065081426760 / 10 = 114779706508142676 FEDCB59726A1348 / 1 = FEDCB59726A1348 | 1147797065081426760 / 1 = 1147797065081426760 FEDCB59726A1348 / 3 = 54F43C87B78B118 | 1147797065081426760 / 3 = 382599021693808920 FEDCB59726A1348 / 4 = 3FB72D65C9A84D2 | 1147797065081426760 / 4 = 286949266270356690 FEDCB59726A1348 / 8 = 1FDB96B2E4D4269 | 1147797065081426760 / 8 = 143474633135178345