Page 1 of 1

Nine digit puzzle

Posted: Mon Mar 05, 2018 7:42 pm UTC
by DataGenetics
Not too challenging, and fun to solve over a cup of coffee, if you've not seen it before.

Arrange the digits 1-9 to make a nine digit number such that the first digit is divisible by one, the first two digits divisible by two, first three digits divisible by three …

Solution here:

Re: Nine digit puzzle

Posted: Wed Mar 07, 2018 9:05 am UTC
by Bloopy
Almost too challenging for me but got it eventually. I used a bit of dumb trial and error.


I thought checking for divisibility by 7 would be the snag to rule out a lot of possibilities so I aimed to sort that out much earlier than the linked solution. I put the 5 in place and put 2,4,6,8 in the even positions in any old order. Then I tried the other odd digits in various permutations preserving the divisibility by 3, while using the first method posted here to check for divisibility by 7 (I found it easier to swap digits around in a formula rather than a 7 digit number). If none of those worked, I rearranged the 2,4,6,8. Eventually after a few wrong turns I paid a bit more attention to the divisibility by 4, 6 & 8 and homed in on the answer fairly quickly.

Re: Nine digit puzzle

Posted: Thu Mar 08, 2018 1:30 pm UTC
by patzer

Unless I'm misunderstanding it, this puzzle seems fairly trivial. Just do it from left to right– there's always a number you can use.

One solution is 444456648.

I'd estimate that there would be approximately 2756 possible solutions to this puzzle ( = 10^9 / 9! ).

Would be much more difficult, of course, with more digits. Try to solve the puzzle with fifteen digits instead of nine!

EDIT: just realized I misread the puzzle. Didn't see the "arrange the digits 1 to 9" bit...

Re: Nine digit puzzle

Posted: Thu Mar 08, 2018 7:39 pm UTC
by Soupspoon
Place the 5 the only place it can go. The four even numbers have only four places, and these in turn tie down the 3, 6, and 7-place numbers (the 1-digit solution is always unconstrained, save by availability, as is the 9-digit one) with some digits already ruled out, through prior use, as you progressively fill in the gaps and check the multiples (when you add digit 3 you can validate 3ness, 4ness and 6ness; if so, adding digit 7 validates/otherwise 7ness and 8ness; 1/2/5/9ness is inherent).

There may be a quicker method, but with a phase-space significantly lower than 1x(4x3x2x1)x(4x3x2x1), as dead-ends reveal themselves and the (sole) solution pops out.

***long pause, before actually posting…***

I actually just tried semi-brute-forcing the answer in various ways, the "intelligent" solution has the program hit 34 dead ends on the way to the answer, while with the most basic method of trying (the current remainder of) digits 1..9 from position 1 to position 9, moving onto the next most recent alternative option at each failure, hits 413 failures along the way with trying the order-of-preference of digits 9..1 giving 2127 failures!

Obviously depends upon order of preference (present the digits in the order of the eventual answer, and it gets there with zero failures) and I'm tempted to meta-brute-force all permutations of 1..9 to see the total range of possibilities (from straight to the answer to the absolute worst 'misteps all the way' combination, which is not necessarily the exact reverse of the answer, as it should also pass muster in lower lengths to waste time) but that'd need another layer of multilayer iteration atop my dumb-and-dumber engines.

(Unintelligently) populating in any order other than left-to-right is already a bad idea, if you need to wait for the first digit to be permuted in before you can yay-or-nay any multiple (besides the 5 and the cut-down selection necessary on the even spots, but I'm not crediting that brute-forcer with any programmed-in sense to do that), so we can probably forget about meta-meta-bruteforcing a more generalised strategy, knowing that it's a total waste.

there's a spoiler tag. use it. -jr