Given a positive integer n, I wish to find the longest unique sequence of positive integers, none greater than n, such that for every pair of adjacent numbers in the sequence one is an integral multiple of the other.
Given n=3, the longest sequence would be:
(2, 1, 3) or (3, 1, 2)
Because 3 is 1×3, and 2 is 1×2.
Given n=4, it would be:
(2, 4, 1, 3) or (3, 1, 2, 4) or (3, 1, 4, 2) or (4, 2, 1, 3)
Because 4 is 2×2.
Given n=5, it would still be the same because 5 can only pair with 1 but 1 is always full.
Given n=6, it can now be (3, 6, 2, 4, 1, 5) etc.
I only need one sequence. Here's the one with brute forcing:
n = 6
from itertools import permutations
def check_adjacent(seq):
for a, b in zip(seq[1:], seq[:-1]):
min_ = min(a, b)
max_ = max(a, b)
if max_ % min_ != 0:
return False
return True
def decreaser(n, m):
for seq in permutations([i for i in range(1, n+1)], m):
if check_adjacent(seq):
return seq
return decreaser(n, m-1)
print(decreaser(n, n))
How to design this algorithm since brute forcing would be tragic.