Ask Your Question

Is there a functional way to manipulate cycles extracted from a digraph?

asked 2016-05-17 08:51:38 +0200

Maybeso83 gravatar image

I wrote a worksheet that defines a digraph and extracts all of its simple cycles.

pr = prime_range(3600)
wief = DiGraph([pr, lambda p, q: power_mod(p, q - 1, q^2) == 1]) # could take a while!
sc = wief.all_simple_cycles()
sc.append([0, 0])

Then it uses mostly procedural code to:

  1. Remove the duplicate endpoints
  2. Reverse-sort the cycle
  3. Group cycles by length
  4. Sort the group of cycles
  5. Return the first (lexicographically earliest) cycle of each length

maxn = 0
for c in sc:
    del c[0] # duplicate
    maxn = max(maxn, len(c))
    c.sort(reverse=True) # reverse lexicographic
# group by length
tbl = [[c for c in sc if len(c) == n] for n in range(1,maxn)]
n = 1
for t in tbl: # sort tuples by max element, get smallest tuple
    print 'n=%d:'%(n),
    # why can't join handle a list of integers?
    print ', '.join(map(lambda m: '%s'%(m), t[0]))
    n = n + 1

The worksheet is adequate - it performs step 5 correctly, but a listing of the code will be posted as the PROG paragraph of an OEIS entry. So I would really like to reduce the numbered steps to as few lines as possible. Are there more graceful ways to tweak the output of one function before passing it on to another?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2016-05-22 04:16:37 +0200

Maybeso83 gravatar image

With the help of a PARI programmer and OEIS regular I cleaned up my code:

wief = DiGraph([prime_range(3600), lambda p, q: power_mod(p, q-1, q^2)==1])
sc = [[0]] + [sorted(c[1:], reverse=1) for c in wief.all_simple_cycles()]
tbl = [sorted(filter(lambda c: len(c)==n, sc))[0] for n in range(1, len(sc[-1]))]
for t in tbl: print 'n=%d:'%(len(t)), ', '.join("%s"%i for i in t)

and posted it to OEIS sequence A271100 Wieferich n-tuples. I used it to increase the number of listed terms from 15 to 300. We'll probably bump that to nearly 10k soon : )
*For the community, I'd like to add mouse-over hints describing what each piece of code does but I'm a noob.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2016-05-17 08:51:38 +0200

Seen: 238 times

Last updated: May 22 '16