Follow

I used in to help solve this - but only as a calculator!

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 puzzles in the Guardian

I reckon so. It just might be that a hexadecimal version would also have a unique solution. Or octal!

@phoe

@EdS @phoe Thanks for pointing out the puzzle. It was a fun diversion. Transforming the puzzle in the "obvious" way for different bases, I found that octal has three solutions, and hexadecimal appears to have none.

@EdS @phoe Of course, now I'm thinking about translating the problem to sexagesimal, and... I think I'll need a different approach. 😆

@cstanhope @EdS I guess you could easily specify the problem in Prolog and have it find all the answers for you for all the bases you can think of.

@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!). 😬

> sexagesimal

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.

@cstanhope @phoe

@EdS Yahoo answers says 3816547290, but I'm still looking for a description of any cleverness which would help solve it.

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.

@vandys

@EdS @vandys yeah, second and third digit already limits out so many combinations that it is a childs play after that 🙂

That's one smart child!

Or at least, persistent and methodical. And perhaps knowing one or two divisibility tricks...

@pet84rik @vandys

@EdS @vandys I will maybe try to solve this without any computer 😄 just for fun and test how long it will take.

@EdS @vandys 35 minutes.. but yes, it helps to know when the number is divisible by 3, for example 😄

Sign in to participate in the conversation
Mastodon @ SDF

"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