On Sat, May 26, 2012 at 10:20 PM, Matthew G <matthew.gilli...@gmail.com> wrote:
>> So now we're down to 102+40+80 = 222 possibilities.
>> Can we do any better?

>   We do seem to be able to do a bit better.  After seeing some pretty
> exciting code and demos at EuroClojure, I tried this out using
> core.logic which is a logic programming library for Clojure.
>  core.logic is similar in its capabilities to prolog, but is just a
> regular clojure lib so you can mix logic programming with functional
> very easily.

> core.logic: https://github.com/clojure/core.logic
> A (really nice) core.logic primer:  https://github.com/clojure/
> core.logic/wiki/A-Core.logic-Primer

> My code: https://github.com/mjg123/bf-logic/blob/master/src/bflogic/core.clj

>   Jim's analysis is really excellent, and all I had to do was write it
> out in the format that core.logic expects.  I added to Jim's lemmas
> 1-4 a further constraint that the first 2 digits must differ by one.
>  The result (which takes my laptop about a minute and a half) is a
> list of 30 candidates, from which the correct one can easily be
> selected by eye.  436578912.

>   Can anyone constrain the solution list further?  To one item,
> ideally ;)

> Matthew

> On Apr 27, 10:57 am, Arwyn <arwyn.robe...@gmail.com> wrote:
>> Hi Jim,

>> That's an impressive effort!
>> You certainly got much further than I did with logic.

>> I must admit that I suggested this as a programming problem, so I was kind
>> of ignoring the "Clever logic..." bit.

>> My original aim was to write something that reads like a statement of the
>> problem and also solves it.
>> In a language like Prolog I think that might not be too difficult.
>> However, working in Haskell I have found it quite challenging.
>> I did a filter-based solution which essentially brute-forces the whole
>> thing (9! perms).
>> However, I would like to do something a bit more clever, by which I mean
>> something that tests fewer candidates.

>> You have already cut the space down considerably: 144+48+96=288 << 9!
>> I think we can cut it down a bit further.

>> E.g. taking:

>> >> Ending 12 can be split up 3 ways:
>> >>      - Containing (34 or 43) and (56 or 65) and (789 or 987)
>> >>      - Containing (34 or 43) and (567 or 765) and (89 or 98)
>> >>      - Containing (345 or 543) and (67 or 76) and (89 or 98)
>> >>      = 3*2*2*2*3*2*1=144 possibilities

>> Some of the permutations can be excluded by the rule: "In just one case a
>> digit has both neighbours differing from it by one."
>> E.g. the first permutation enumerated would be 345678912 which has 5 digits
>> which have both neighbours differing by 1.
>> Your three lines above already give the three cases for which digit has 2
>> neighbours differing by one: 8, 6 and 4 respectively.
>> So we just have to exclude all the incidental ones; I'll call them
>> "collisions".

>> We still have 3x2x1 perms of the arrangement of groups, however all of them
>> result in at least 1 possible collision and 2 result in 2.
>> If there is 1 possible collision, that reduces the number of perms of the
>> ordering within the groups from 8 to 6 (3 for the collided groups x 2 for
>> the other one).
>> If there are 2 possible collisions, that reduces the number of such perms
>> to 5 because 1 of those 6 is excluded.

>> What this means is that instead of each line being 6x8 = 48 permutations we
>> have 4x6+2x5 = 34.
>> By three lines gives 102.

>> Using similar logic we get 4x6+2x8 = 40 perms for Ending 56 and 80 for
>> Ending 76.

>> So now we're down to 102+40+80 = 222 possibilities.
>> Can we do any better?

>> Cheers,
>> Arwyn

>> On Thursday, 26 April 2012 19:32:49 UTC+1, Jimbo F wrote:

>> > On 2012-04-13 11:15, Arwyn wrote:

>> > > Clever logic should enable you to find the nine-figure number that I
>> > > have in mind. It consists of the digits 1 to 9 in some order, and in
>> > > the number each digit is next to another that differs from it by one.

>> > > In just one case a digit has both neighbours differing from it by one.
>> > > Furthermore, the solution is exactly divisible by more than
>> > > three-quarters of the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12.

>> > > What is the nine-figure number?

>> > Totally off topic.

>> > Did anyone solve this? I made some progress, but didn't nail it.

>> > Lemma 1: The solution must be divisible by 4.

>> > Assume the solution is not divisible by 4.  It is therefore not
>> > divisible by 8 or 12.  However, this would mean that the solution is
>> > only divisible by at most 3/4th of the numbers between 1 and 12, which
>> > contradicts the problem, which states it is divisible by strictly more
>> > than 3/4th.

>> > We could apply the same argument to 2 and 3, but we don't need to...

>> > Lemma 2: The solution is divisible by 1, 2, 3, 4, 6, 7, 8, 9, 11 and 12,
>> > but not 5 or 10.

>> > All numbers divisible by 10 end in 0.  The solution doesn't contain a
>> > 0.  We know from Lemma 1 that it's divisible by 4.  If it is also
>> > divisible by 5, it must also end in 0.  If the solution were not
>> > divisible by any other numbers on the list, it would only be divisible
>> > by 3/4ths, which contradicts the problem, so it must be divisible by the
>> > remaining numbers.

>> > Lemma 3: The solution must end in 12, 32, 56 or 76

>> > Because the solution is divisible by 4, it's last two digits must be
>> > divisible by 4.  The two digits must differ by 1.  The second digit must
>> > be even, since it is divisible by 4, so the first digit must be odd.
>> > This only leaves a few possibilities.  Checking them, we find that 12,
>> > 32, 56 and 76 fit the bill.

>> > Lemma 4: The solution cannot end in 32.

>> > Assume the number ended with 32.  According to the rules, the digit 1
>> > must be next to digit 2.  However, digit 2 is at the end, so this is a
>> > contradiction.

>> > Where next?

>> > Ending 12 can be split up 3 ways:
>> >      - Containing (34 or 43) and (56 or 65) and (789 or 987)
>> >      - Containing (34 or 43) and (567 or 765) and (89 or 98)
>> >      - Containing (345 or 543) and (67 or 76) and (89 or 98)
>> >      = 3*2*2*2*3*2*1=144 possibilities

>> > Ending 56 can only split 1 way:
>> >      - Containing (12 or 21) and (34 or43) and (789 or 987)
>> >      = 1*2*2*2*3*2*1=48 possibilities

>> > (Note that, ending 456 is not allowed unless the preceding digit is 3,
>> > because then we'd have to form a group from 123, or leave 3 on it's own)

>> > Ending 76 can be split up 2 ways:
>> >      - Containing (12 or 21) and (345 or 543) and (89 or 98)
>> >      - Containing (123 or 321) and (45 or 54) and (89 or 98)
>> >      = 2*2*2*2*3*2*1= 96 possibilities

>> > Brute forcible, but the question suggests we shouldn't need to.

>> > Can we exclude more possibilities using other divisors?

>> > 2: Not really any help, as we already made use of 4, which is strictly
>> > stronger.
>> > 3: No help - if you rearrange the digits of a number divisible by 3, you
>> > get another number divisible by 3.  So we can't exclude any wrong
>> > answers, because they will also be divisible by 3.
>> > 4: Already used
>> > 9: No help for the same reasons as 3.

>> > 8 can be used to restrict the 3rd from last digit, but it only excludes
>> > a handful of possibilities (it doesn't even uniquely determine the 3rd
>> > digit).  Depending on whether the last 2 digits are divisible by 8, the
>> > second to last digit must be either even or odd.  Some possibilities are
>> > excluded because the result in illegal combinations of digits)

>> > My gut feeling tells me that 12 isn't very useful - we already made use
>> > of one it's factors (4) and we know that the other one (3) provides no
>> > useful information,  so I don't think 12 tells us anything.  (But I'm
>> > not sure I have a watertight argument, so I could be wrong here)

>> > So I'm pretty sure we need to make use of 7 and 11 - but I can't see an
>> > easy way or doing so (without doing a tonne of algebra, which I don't
>> > think the question is looking for)

>> >http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_rules_for...

>> > Jim