# Maths Puzzle

Discussion

Original Poster 9,969 posts

248 months

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?

1,144 posts

231 months

there are 2492 number that fit that bill

the last of which is 987654564

3,788 posts

180 months

zippy3x said:
there are 2492 number that fit that bill

the last of which is 987654564
and the first is 102456243

Maybe.

1,144 posts

231 months

Road2Ruin said:
and the first is 102456243

Maybe.
According to my (very hastily written program) the first is 102000564

3,788 posts

180 months

I did say maybe. Yes I missed that one....

1,144 posts

231 months

and eight others 6,380 posts

170 months

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++;
}

3,788 posts

180 months

sorry, forgot to carry the 1 17,124 posts

225 months

To be honest, you lost me at 'integer'. I thought that was a car made by Honda. From there it was all downhill.

1,144 posts

231 months

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

Original Poster 9,969 posts

248 months

Damn. Forgot to mention, the digits from 1 to 9 can only appear once each in the number.

3,605 posts

186 months

zippy3x said:
anyone got a working BBC or electron? I'd love to know how long that would take on a 30 year old machine
I've got 7 - but I would probably not write it in C# 26,627 posts

176 months

Alex said:
Damn. Forgot to mention, the digits from 1 to 9 can only appear once each in the number.
Luckily Microsoft made a brilliantly realistic emulator.

They called it Vista.

1,144 posts

231 months

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

Original Poster 9,969 posts

248 months

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.

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.

11,590 posts

150 months

Lightning Bolt!

3,605 posts

186 months

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#)...

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

Original Poster 9,969 posts

248 months

OK, we know the answer. Let's change this to a coding challenge!

I propose the following categories:

• Most elegant
• Shortest
• Fastest
• Daftest
You can use any language. I'll have a go myself.

No doubt some LISP expert will come along with a single line solution...

1,144 posts

231 months

Alex said:
OK, we know the answer. Let's change this to a coding challenge!

I propose the following categories:

• Most elegant
• Shortest
• Fastest
• Daftest
You can use any language. I'll have a go myself.

No doubt some LISP expert will come along with a single line solution...
I'll have a go at Most Elegant, Shortest and Fastest

Console.WriteLine("381654729");

anyone do better?