[seqfan] Re: Mobile phone security!

[Rob Arthan]

Maximilian,

On 21 Sep 2014, at 14:46, M. F. Hasler <oeis at hasler.fr> wrote:

> Rob,
> 
> I'm not sure the rules stated there are correct:
> not only neighbours may be connected, you can connect e.g. the "1"
> with the "6" on a 3x3 grid (labelled as a numeric keypad)(*), but you
> cannot directly connect the 1 with the 3 or the 9: if you try, the 2
> resp. 5 is added to the path.

Quite so. You could easily calculate the answer from A188147 otherwise.

> (I did not check whether your calculation does use these rules.)

It does (see the description of the graph G(m, n)).

> 
> (*) Here's a screenshot, not sure whether you can access:
> https://lh6.googleusercontent.com/-s7VaC2EXKiA/VB7ViGkqC5I/AAAAAAAABzk/KMos3nWrcko/w346-h519/Screenshot_2014-09-21-08-54-34.png
> 

Thanks for that illustration. Don’t forget to change the password on your phone to something different :-)

Regards,

Rob.

> -- 
> Maximilian
> 
> On Sat, Sep 20, 2014 at 4:17 PM, Rob Arthan <rda at lemma-one.com> wrote:
>> I have been playing with a two-dimensional sequence inspired by the
>> security patterns that you can use like passwords on Android phones.
>> See:
>> 
>> http://math.stackexchange.com/questions/37167/combination-of-smartphones-pattern-password
>> 
>> But I don’t think any of the answers there except (possibly) the one I added this
>> afternoon can be right.
>> 
>> Ignoring the minor detail that Android requires the patterns to have at least
>> four points, this suggests a two-dimensional sequence a(m, n) defined as follows.
>> Let G(m, n) be the graph whose vertices are the integer lattice points (p, q)
>> with 0 <= p < m and 0 <= q < n. The graph has an edge between v
>> and w iff the line segment [v, w] does not contain any other
>> integer lattice points (equivalently, iff v - w = (i, j) with i and j coprime).
>> a(m, n) is the number of acyclic eulerian paths in G(m, n).
>> 
>> I implemented a brute force search and got the following values of:
>> a(m, n) for 1 <= m <= 3 and 1 <= n <= 4:
>> 
>> 0, 2, 6, 12
>> 2, 60, 1058, 25080
>> 6, 1058, 140240, 58673472
>> 
>> I have only been able to verify these results independently
>> in the cases when one of m or n is 1 (which is easy because
>> the paths are uniquely determined by their end-points in that
>> case and in the case m = n = 2 (which is easy because G(2, 2)
>> is the complete graph on 4 vertices).  I would be very grateful
>> for confirmation of (or corrections to) my results and for any
>> thoughts on an efficient way of calculating the sequence.
>> 
>> My OEIS searches haven’t come up with anything like this.
>> Do people think this sequence is worth submitting to OEIS?
>> 
>> Regards,
>> 
>> Rob.
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/