The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Next #BrisFunctional
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 13 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Apr 13 2012, 6:15 am
From: Arwyn <arwyn.robe...@gmail.com>
Date: Fri, 13 Apr 2012 03:15:22 -0700 (PDT)
Local: Fri, Apr 13 2012 6:15 am
Subject: Next #BrisFunctional

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?

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 13 2012, 6:18 am
From: Timothy Perrett <tperr...@gmail.com>
Date: Fri, 13 Apr 2012 11:18:28 +0100
Local: Fri, Apr 13 2012 6:18 am
Subject: Re: Next #BrisFunctional
Doh, that clashes with ScalaDays this year. Next month perhaps! Have fun :-)

Cheers, Tim

On 13 Apr 2012, at 11:15, Arwyn wrote:

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 16 2012, 8:44 am
From: Thom Leggett <t...@thomleggett.co.uk>
Date: Mon, 16 Apr 2012 13:44:26 +0100
Local: Mon, Apr 16 2012 8:44 am
Subject: Re: Next #BrisFunctional
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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 16 2012, 8:46 am
Date: Mon, 16 Apr 2012 13:46:15 +0100
Local: Mon, Apr 16 2012 8:46 am
Subject: Re: Next #BrisFunctional

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 :)

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 16 2012, 12:58 pm
From: Arwyn <arwyn.robe...@gmail.com>
Date: Mon, 16 Apr 2012 09:58:30 -0700 (PDT)
Local: Mon, Apr 16 2012 12:58 pm
Subject: Re: Next #BrisFunctional

24th works for me.

Cheers,
Arwyn

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 17 2012, 6:52 am
From: Thom Leggett <t...@thomleggett.co.uk>
Date: Tue, 17 Apr 2012 11:52:05 +0100
Local: Tues, Apr 17 2012 6:52 am
Subject: Re: Next #BrisFunctional
24th it is then.

Any suggestions for topics, talks, labs?

T.

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 19 2012, 6:20 am
From: Arwyn <arwyn.robe...@gmail.com>
Date: Thu, 19 Apr 2012 03:20:28 -0700 (PDT)
Local: Thurs, Apr 19 2012 6:20 am
Subject: Re: Next #BrisFunctional

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 24 2012, 11:11 am
From: Timothy Perrett <tperr...@gmail.com>
Date: Tue, 24 Apr 2012 08:11:30 -0700 (PDT)
Local: Tues, Apr 24 2012 11:11 am
Subject: Re: Next #BrisFunctional

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

Cheers, Tim

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 24 2012, 11:29 am
From: James Carnegie <k...@neuralyte.org>
Date: Tue, 24 Apr 2012 16:29:23 +0100
Local: Tues, Apr 24 2012 11:29 am
Subject: Re: Next #BrisFunctional

Me neither... :(
On Apr 24, 2012 4:11 PM, "Timothy Perrett" <tperr...@gmail.com> wrote:

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 26 2012, 2:32 pm
From: Jim Farrand <jim.farr...@gmail.com>
Date: Thu, 26 Apr 2012 19:32:49 +0100
Local: Thurs, Apr 26 2012 2:32 pm
Subject: Re: Next #BrisFunctional
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

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

Jim

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 27 2012, 5:57 am
From: Arwyn <arwyn.robe...@gmail.com>
Date: Fri, 27 Apr 2012 02:57:37 -0700 (PDT)
Local: Fri, Apr 27 2012 5:57 am
Subject: Re: Next #BrisFunctional

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

To post a message you must first join this group.
You do not have the permission required to post.
More options May 26 2012, 5:20 pm
From: Matthew G <matthew.gilli...@gmail.com>
Date: Sat, 26 May 2012 14:20:08 -0700 (PDT)
Local: Sat, May 26 2012 5:20 pm
Subject: Re: Next #BrisFunctional

> 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

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:

To post a message you must first join this group.
You do not have the permission required to post.
More options May 26 2012, 5:22 pm
From: Matthew Gilliard <matthew.gilli...@gmail.com>
Date: Sat, 26 May 2012 22:22:36 +0100
Local: Sat, May 26 2012 5:22 pm
Subject: Re: Next #BrisFunctional
Hmm - the formatting ate my link to the core.logic primer:
https://github.com/clojure/core.logic/wiki/A-Core.logic-Primer

MG