I have a ten digit number, abcdefghij. Each of the digits is different, and
a is divisible by 1
ab is divisible by 2
abc is divisible by 3
abcd is divisible by 4
abcde is divisible by 5
abcdef is divisible by 6
abcdefg is divisible by 7
abcdefgh is divisible by 8
abcdefghi is divisible by 9
abcdefghij is divisible by 10
What’s my number?
From a pair of John #Conway puzzles in the Guardian
@EdS Are the digits decimal?
I reckon so. It just might be that a hexadecimal version would also have a unique solution. Or octal!
@phoe @EdS I only know a little about Prolog, but I'm not sure it would save me from searching the factorially exploding solution space? Of course, if there are clever ways to constrain the solutions, then that would help.
I initially took the approach described in the Guardian solution, and I was carefully crafting rules and finding parts of the solution, but then I found it was easer to brute force it with a simple recursive function that searched the solution space. But, that is O(N!). 😬
Seems like a good idea to me, if N! is too small to be inconvenient, then try a higher base!
I didn't want to solve this problem by brute force, and I managed to restrain myself. Likewise I managed not to skip straight to reading the solution, which was an unusual thing for me to succeed at.
Although, on recollection, my best beloved did give me a hint.
Figuring out divisibility shortcuts in other bases might be fun. Base 12 might be an interesting one.
@EdS Yahoo answers says 3816547290, but I'm still looking for a description of any cleverness which would help solve it.
@EdS Here's the best solution walk-through I found:
oh I do hope you tried to solve it before searching!
It's a nice puzzle I think, not a gigantic exploration of combinations, no more than a few to check and rule out.
"I appreciate SDF but it's a general-purpose server and the name doesn't make it obvious that it's about art." - Eugen Rochko