[seqfan] Mobile phone security!

Rob Arthan rda at lemma-one.com
Sat Sep 20 22:17:03 CEST 2014

I have been playing with a two-dimensional sequence inspired by the
security patterns that you can use like passwords on Android phones.


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?



More information about the SeqFan mailing list