How to find the longest elementary path in a graph?

Question

The problem is to find the longest sequence of numbers from 1 to 100 such that each number is either multiple or divisor or the previous, and with no repetition. For example, 50 25 5 35 7 63 21 is a valid sequence

I consider this problem as finding the longest path in a graph. The graph's nodes are all integers from 1 to 100 and the nodes x and y are connected if x divides y or y divides x.

This problem is well known to be a NP-problem : https://en.wikipedia.org/wiki/Longest_path_problem

I implemented the graph structure that I found on this answer on another post : https://stackoverflow.com/a/30747003/16673579

And created the corresponding graph with that code :

connections = []
for i in range(1,101):
    for j in range(1,101):
        if math.gcd(i,j) in [i,j] and i!=j:
            connections.append((i,j))

my_graph = Graph(connections=connections)

(I know this code could be optimised but it's not the point)

Now I'm looking for a way to design such an algorithm. I searched for a lot of references for the current fastest algorithm to find the longest path in a graph, even though I expect that it might be impossible due to the complexity and the size of the data, but I can't find a reliable source and python implementation

if you need theory them maybe you could ask on similar site Mathematics Stack Exchange — furas
– furas, Commented Sep 14 at 19:11
I don't have an answer, but maybe you should think about primes and not graphs. — lastchance
– lastchance, Commented Sep 15 at 9:23
Rob Pratt's comment on A337125 gives a complete albeit highly compressed algorithm that he apparently used in computing his table up to 200. If you want to have a go at implementing it yourself, all of the relevant background comes up in solving the Traveling Salesman Problem with integer programming, for which there is a wealth of tutorial material. — David Eisenstat
– David Eisenstat, Commented Sep 23 at 14:08

maraca · Accepted Answer · 2025-09-15 17:39:41Z

If we define pi to to be all the primes where p * i <= 100 < p * (i + 1). Then we can say that prime pi has to be connected to another prime (and its multiples) by a number <= i.

p1 = 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

p2 = 37, (74), 41, (82), 43, (86), 47, (94)

p3 = 29, (58), (87), 31, (62), (93)

p4 = 23, (46), (69), (92)

p5 = 17, (34), (51), (68), (85), 19, (38), (57), (76), (95)

p7 = 13, p9 = 11, p14 = 7, p20 = 5, p33 = 3, p50 = 2

If we apply this rule for i = 5, where it is the most restrictive (max 5 primes > 16, which includes p3, p4 and p5) we can see that we can savely discard p1, p2 and their multiples without shortening the maximum possible path (discarding 18 numbers).

If all those 5 primes are indeed used in the sequence, it would have to start (or end) something like this:

3p3 p3 2p3 2 2p3 p3 3p3 3 3p4 p4 2p4 4p4 4 4p5 2p5 p5 5p5 5 5p5 p5 2p5 4p5 1 ...

The two 3p5 are not used bringing the upper bound of the longest sequence down to 80.

We can probably make more observations to simplify the calculation of the longest path. The results also don't seem to be completely independent, mabe we can try to find or construct a longest path iteratively somehow.

jirassimok · Accepted Answer · 2025-09-15 01:53:22Z

In general, as you noted, there is no usefully-efficient solution to the longest-path problem.

A simple depth-first-search can be used to find longest paths in any graph, and you can optimize it by quitting early if you find a Hamiltonian path (reaching all nodes), but it won't be fast enough for a 100-node graph with as many edges as the divisor graph.¹ With some analysis of the graph and its paths, I'm sure you could invent heuristics to make it a bit faster, but in general, DFS won't work.

After trying DFS on a few smaller graphs myself, I fed the numbers I got into OEIS and found A337125, the sequence of solutions to this problem. From this, we get a very boring answer to the question:

In the divisor graph for 1 to 100, the longest paths have length 77.

But that's not very interesting, so the next thing to try is to see if the numeric structure of this graph might provide some properties that make it tractable. Based on a very brief look into the literature on the subject, it seems that while there are tricks that have been used to make the search faster, the actual search work is done in integer programming (and related paradigms), so there's not much that points towards a "classic" programmatic approach.

This blog post references several other papers and was very useful as a literature review. This paper proving the longest path for n=1000 is also interesting, but not as directly useful (though it gives an idea of some of the math involved in finding solutions).

¹ A naive implementation starts getting really slow around n = 24, so n = 100 is right out.

ThomasIsCoding · Accepted Answer · 2025-09-14 21:31:51Z

I didn't try this approach on large data but it should be able to give you desired output. Frankly speaking, my algorithm seems not optimized nor efficient.

A helper function NextCandidate is implemented to find valid values to be added to the existing path(s), otherwise, the "tree" will be pruned and the processes continues on the branches that survives (say, valid candidates to add can be found)

import itertools
def f(n):
  v = list(range(1, n+1))
  def NextCandidate(path):
    e = path[-1]
    c = [i for i in set(v) - set(path) if (i%e)*(e%i)==0]
    return [path + [cc] for cc in c] if len(c)>0 else []
  
  p, l = [[x] for x in v], 1
  while len(p)>0:
    pp = list(itertools.chain(*map(NextCandidate,p)))
    if len(pp)>0:
      p = pp
      l += 1
    else:
      print(f'length of longest elementary path is: {l}\n')
      print(f'desired path sequence: \n')
      print(*p, sep = '\n')
      break

Examples

Run f(10) will show

length of longest elementary path is: 9

desired path sequence: 

[4, 8, 1, 5, 10, 2, 6, 3, 9]
[4, 8, 1, 9, 3, 6, 2, 10, 5]
[4, 8, 2, 6, 3, 9, 1, 10, 5]
[4, 8, 2, 6, 3, 9, 1, 5, 10]
[4, 8, 2, 10, 5, 1, 9, 3, 6]
[4, 8, 2, 10, 5, 1, 6, 3, 9]
[5, 10, 1, 4, 8, 2, 6, 3, 9]
[5, 10, 1, 8, 4, 2, 6, 3, 9]
[5, 10, 1, 9, 3, 6, 2, 8, 4]
[5, 10, 1, 9, 3, 6, 2, 4, 8]
[5, 10, 2, 4, 8, 1, 9, 3, 6]
[5, 10, 2, 4, 8, 1, 6, 3, 9]
[5, 10, 2, 6, 3, 9, 1, 8, 4]
[5, 10, 2, 6, 3, 9, 1, 4, 8]
[5, 10, 2, 8, 4, 1, 9, 3, 6]
[5, 10, 2, 8, 4, 1, 6, 3, 9]
[6, 3, 9, 1, 4, 8, 2, 10, 5]
[6, 3, 9, 1, 5, 10, 2, 8, 4]
[6, 3, 9, 1, 5, 10, 2, 4, 8]
[6, 3, 9, 1, 8, 4, 2, 10, 5]
[8, 4, 1, 5, 10, 2, 6, 3, 9]
[8, 4, 1, 9, 3, 6, 2, 10, 5]
[8, 4, 2, 6, 3, 9, 1, 10, 5]
[8, 4, 2, 6, 3, 9, 1, 5, 10]
[8, 4, 2, 10, 5, 1, 9, 3, 6]
[8, 4, 2, 10, 5, 1, 6, 3, 9]
[9, 3, 6, 1, 4, 8, 2, 10, 5]
[9, 3, 6, 1, 5, 10, 2, 8, 4]
[9, 3, 6, 1, 5, 10, 2, 4, 8]
[9, 3, 6, 1, 8, 4, 2, 10, 5]
[9, 3, 6, 2, 4, 8, 1, 10, 5]
[9, 3, 6, 2, 4, 8, 1, 5, 10]
[9, 3, 6, 2, 8, 4, 1, 10, 5]
[9, 3, 6, 2, 8, 4, 1, 5, 10]
[9, 3, 6, 2, 10, 5, 1, 8, 4]
[9, 3, 6, 2, 10, 5, 1, 4, 8]
[10, 5, 1, 4, 8, 2, 6, 3, 9]
[10, 5, 1, 8, 4, 2, 6, 3, 9]
[10, 5, 1, 9, 3, 6, 2, 8, 4]
[10, 5, 1, 9, 3, 6, 2, 4, 8]

Run f(13) will show

length of longest elementary path is: 11

desired path sequence: 

[5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 11]
[5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 13]
[5, 10, 2, 8, 4, 12, 6, 3, 9, 1, 7]
[7, 1, 5, 10, 2, 8, 4, 12, 6, 3, 9]
[7, 1, 9, 3, 6, 12, 4, 8, 2, 10, 5]
[9, 3, 6, 12, 4, 8, 2, 10, 5, 1, 11]
[9, 3, 6, 12, 4, 8, 2, 10, 5, 1, 13]
[9, 3, 6, 12, 4, 8, 2, 10, 5, 1, 7]
[11, 1, 5, 10, 2, 8, 4, 12, 6, 3, 9]
[11, 1, 9, 3, 6, 12, 4, 8, 2, 10, 5]
[13, 1, 5, 10, 2, 8, 4, 12, 6, 3, 9]
[13, 1, 9, 3, 6, 12, 4, 8, 2, 10, 5]

Great implementation but there's no way I'll do my 100 numbers in realistic time, the time suddenly jumps around N=22 and I'm afraid to go further

Collectives™ on Stack Overflow

How to find the longest elementary path in a graph?

3 Answers 3

Comments

Comments

Examples

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Examples

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related