Ask Your Question

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

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 # 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
t.sort()
print 'n=%d:'%(n),
# why can't join handle a list of integers?
print ', '.join(map(lambda m: '%s'%(m), t))
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 close merge delete

## 1 Answer

Sort by » oldest newest most voted

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 = [] + [sorted(c[1:], reverse=1) for c in wief.all_simple_cycles()]
tbl = [sorted(filter(lambda c: len(c)==n, sc)) 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.

more

## Your Answer

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

Add Answer

## Stats

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

Seen: 68 times

Last updated: May 22 '16