Next #BrisFunctional

[Arwyn]

Hi All,

Are we on for next Tuesday (17th)?

Arwyn

P.S.

Here's a little puzzle courtesy of New Scientist:

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?

[Timothy Perrett]

Doh, that clashes with ScalaDays this year. Next month perhaps! Have fun :-)

Cheers, Tim

[Thom Leggett]

Hey All,

Happy to do tomorrow but I've not had a chance to prepare anything,
sorry. We could do it next week on the 24th?

Thanks,
T.

[Sam Phippen]

On 16 Apr 2012, at 13:44, Thom Leggett wrote:

> Hey All,
>
> Happy to do tomorrow but I've not had a chance to prepare anything,
> sorry. We could do it next week on the 24th?

Plus one for next week because I'm not in bristol at the moment :)

[Arwyn]

24th works for me.

Cheers,

Arwyn

[Thom Leggett]

24th it is then.

Any suggestions for topics, talks, labs?

T.

[Arwyn]

My boss has suddenly dragged me of to a meeting abroad next week.

I'm not going to get back in time for the meet-up on the 24th, after all!

Curses!

Cheers,

Arwyn

[Timothy Perrett]

Guys, having a meltdown at work - wont make the meetup tonight im afraid sorry. have a great one though :-)

Cheers, Tim

[James Carnegie]

Me neither... :(

[Jim Farrand]

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_numbers_1.E2.80.9320


Jim

[Arwyn]

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

[Matthew G]

> 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

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

[Matthew Gilliard]

Hmm - the formatting ate my link to the core.logic primer:
https://github.com/clojure/core.logic/wiki/A-Core.logic-Primer

MG