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 Continue reading...
