[seqfan] Re: More rows of triangle in A271100?

[Bruce Leenstra]

Hi David et all,

I tried to generate more terms, but my program needs improving. All I get
is:
Creating digraph with primes to 50,000
CPU time: 1195.27 s, Wall time: 1296.31 s
Digraph on 5133 vertices
 ...

I'm going to try removing dead-end vertices before getting the cycles.
Hopefully that will drastically reduce the backtracking.

Best,
Bruce

PS:
If you don't want to wait for me to fix this, while I was waiting for it to
finish I tinkered with the sage PARI/GP mode. Like you, I didn't find
anything similar to a digraph. But I managed to build an arc list, (this is
in sage %gp mode, so syntax may be weird):

cong(p, q) = Mod(p, q^2)^(q-1)==1;
node = primes(100);
arc = [[i | i <- [1..#node], cong(p, node[i])] | p <- node]

Probably also needs reverse arcs:
arcinv = [[i | i <- [1..#node], cong(node[i], p)] | p <- node]
to detect sources and sinks and cleanly remove vertices.

Then a recursive search for n-tuples would be a pari version of:
search(ntuple) =
{
  a = ntuple[0]
  i = ntuple[-1]
  best = cycles[#ntuple]
  for j = arc[i]
  {
    if j == a {
      if ntuple < best // element x element compare
        cycles[#ntuple] = sort(copy(ntuple), reverse)
    } else {
      if (j <= best[0]) AND !ntuple.contains[j]
      {
        ntuple.push[j]
        search(ntuple)
        ntuple.pop[]
      }
    }
  }
}