Follow

I used #lisp in #emacs to help solve this #puzzle - 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 #Conway puzzles in the Guardian

@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.

@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.

Michał "phoe" Herda@phoe@functional.cafe@EdS Are the digits decimal?