Discussion
This was originally in Acorn User magazine many years ago.
Find a 9-digit integer that is exactly divisible by 9.
Now remove the 9th digit to leave an 8-digit integer that is exactly divisible by 8.
Now remove the 8th digit to leave an 7-digit integer that is exactly divisible by 7.
And so on, down to a 1-digit integer that is obviously divisible by 1.
What is the 9-digit number? Is there more than one answer?
Find a 9-digit integer that is exactly divisible by 9.
Now remove the 9th digit to leave an 8-digit integer that is exactly divisible by 8.
Now remove the 8th digit to leave an 7-digit integer that is exactly divisible by 7.
And so on, down to a 1-digit integer that is obviously divisible by 1.
What is the 9-digit number? Is there more than one answer?
I'm sure there is a better way of doing it but (apologies for formatting but the code tags don't seem to work):
int count = 0;
for (int i = 100000000; i < 999999999; i++) {
int div = 9;
int temp = i;
do {
if (temp % div == 0) {
div--;
temp = (temp / 10);
} else break;
} while (div > 0);
if (div == 0) count++;
}
int count = 0;
for (int i = 100000000; i < 999999999; i++) {
int div = 9;
int temp = i;
do {
if (temp % div == 0) {
div--;
temp = (temp / 10);
} else break;
} while (div > 0);
if (div == 0) count++;
}
Here's my code
DateTime start = DateTime.Now;
int count = 0;
for (int i = 100000000; i < 999999999; i++)
{
if (i % 9 == 0)
{
int n = i / 10;
if (n % 8 == 0 && ((n /= 10) % 7 == 0) && ((n /= 10) % 6 == 0) && ((n /= 10) % 5 == 0) &&
((n /= 10) % 4 == 0) && ((n /= 10) % 3 == 0) && ((n /= 10) % 2 == 0))
{
Console.WriteLine(i.ToString());
count++;
}
}
}
TimeSpan duration = DateTime.Now.Subtract(start);
Console.WriteLine(count.ToString());
Console.WriteLine("duration - " + duration.ToString());
Duration 5.95 seconds - quickly hacked and optimised for speed
anyone got a working BBC or electron? I'd love to know how long that would take on a 30 year old machine
DateTime start = DateTime.Now;
int count = 0;
for (int i = 100000000; i < 999999999; i++)
{
if (i % 9 == 0)
{
int n = i / 10;
if (n % 8 == 0 && ((n /= 10) % 7 == 0) && ((n /= 10) % 6 == 0) && ((n /= 10) % 5 == 0) &&
((n /= 10) % 4 == 0) && ((n /= 10) % 3 == 0) && ((n /= 10) % 2 == 0))
{
Console.WriteLine(i.ToString());
count++;
}
}
}
TimeSpan duration = DateTime.Now.Subtract(start);
Console.WriteLine(count.ToString());
Console.WriteLine("duration - " + duration.ToString());
Duration 5.95 seconds - quickly hacked and optimised for speed
anyone got a working BBC or electron? I'd love to know how long that would take on a 30 year old machine
Alex said:
Damn. Forgot to mention, the digits from 1 to 9 can only appear once each in the number.
Tease....Ok - with the new criteria it's down to 121
However i will pre-empt your next post and tell you that when the digits 0 to 9 can only appear one it goes down to 4
381654720
381654729
783204165
801654723
zippy3x said:
Tease....
Ok - with the new criteria it's down to 121
However i will pre-empt your next post and tell you that when the digits 0 to 9 can only appear one it goes down to 4
381654720
381654729
783204165
801654723
381654729 was the answer I was looking for, and is the only solution without using zero.Ok - with the new criteria it's down to 121
However i will pre-empt your next post and tell you that when the digits 0 to 9 can only appear one it goes down to 4
381654720
381654729
783204165
801654723
I wrote a BASIC program to solve it on my mate's Dragon 32. I recall it ran for around 30 minutes before finding the solution.
zippy3x said:
Tease....
Ok - with the new criteria it's down to 121
However i will pre-empt your next post and tell you that when the digits 0 to 9 can only appear one it goes down to 4
381654720
381654729
783204165
801654723
I've done my own version (in C#)...Ok - with the new criteria it's down to 121
However i will pre-empt your next post and tell you that when the digits 0 to 9 can only appear one it goes down to 4
381654720
381654729
783204165
801654723
C:\stprojects\tmp\NumberCrunch\NumberCrunch\bin\Debug>NumberCrunch.exe
381654720
381654729
783204165
801654723
Count: 4
duration - 00:00:00
Yes, I am running debug. Yes, it did take 0 seconds.
The thing is you've got to think about it in reverse. My code starts with the first two digits, and makes sure that they're different, and the number's even. All other combinations after this can be ignored. It then adds the third number, checks it's different, and makes sure that it's divisible by 3. And so on.
For the 2nd, 4th, 6th and 8th numbers, they need to be even - so it just starts at 0, and increments by 2.
Here's the code:
DateTime start = DateTime.Now;
int count = 0;
for (int a = 1; a < 10; a++)
{
for (int b = 0; b < 10; b += 2)
{
if (a == b)
continue;
for (int c = 0; c < 10; c++)
{
if ((c == a) || (c == b))
continue;
if (((a + b + c) % 3) != 0)
continue;
for (int d = 0; d < 10; d += 2)
{
if ((d == a) || (d == b) || (d == c))
continue;
if (((c * 10 + d) & 3) != 0)
continue;
for (int e = 0; e < 10; e += 5)
{
if ((e == a) || (e == b) || (e == c) || (e == d))
continue;
for (int f = 0; f < 10; f += 2)
{
if ((f == a) || (f == b) || (f == c) || (f == d) || (f == e))
continue;
if (((a + b + c + d + e + f) % 3) != 0)
continue;
for (int g = 0; g < 10; g++)
{
if ((g == a) || (g == b) || (g == c) || (g == d) || (g == e) || (g == f))
continue;
if (((a * 1000000 + b * 100000 + c * 10000 + d * 1000 + e * 100 + f * 10 + g) % 7) != 0)
continue;
for (int h = 0; h < 10; h++)
{
if ((h == a) || (h == b) || (h == c) || (h == d) || (h == e) || (h == f) || (h == g))
continue;
if (((f * 100 + g * 10 + h) & 7) != 0)
continue;
for (int i = 0; i < 10; i++)
{
if ((i == a) || (i == b) || (i == c) || (i == d) || (i == e) || (i == f) || (i == g) || (i == h))
continue;
if (((a + b + c + d + e + f + g + h + i) % 9) != 0)
continue;
Console.WriteLine(string.Format("{0}{1}{2}{3}{4}{5}{6}{7}{8}", a, b, c, d, e, f, g, h, i));
count++;
}
}
}
}
}
}
}
}
}
TimeSpan duration = DateTime.Now.Subtract(start);
Console.WriteLine(string.Format("Count: {0}", count));
Console.WriteLine("duration - " + duration.ToString());
I nicked your timespan code - easier than writing my own.
Each check to see if it's divisible by <n>, I've used mathematical trickery where possible.
ETA: I found a slight bug, which I corrected here before testing it, and it came up with other answers. I'll correct it when it's done, but hopefully the idea of how to solve this has been put across.
Edited again: I found the bug, and it's now producing the same 4 results, albeit a bit faster I've corrected the code.
Edited by tribbles on Tuesday 22 February 16:19
Edited by tribbles on Tuesday 22 February 16:22
Alex said:
OK, we know the answer. Let's change this to a coding challenge!
I propose the following categories:
No doubt some LISP expert will come along with a single line solution...
I'll have a go at Most Elegant, Shortest and FastestI propose the following categories:
- Most elegant
- Shortest
- Fastest
- Daftest
No doubt some LISP expert will come along with a single line solution...
Console.WriteLine("381654729");
anyone do better?
Gassing Station | Computers, Gadgets & Stuff | Top of Page | What's New | My Stuff