Maximum GCD-Sum Permutations

Leroy Quet qq-quet at mindspring.com
Sun Apr 18 23:11:09 CEST 2004


If we have the permutation of {1,2,3,...,m}, where the sum of the (m-1) 
GCDs of adjacent elements in the permutation is maximized, we get 
(perhaps, found by hand) the sums equal to:
(starting at m=2)

1, 2, 4, 5, 9, 10, 14, 17, 23, 24, 32,...

(For example, for m = 12, one of the maximum-GCD-sum permutations {there 
are a few which add up to 32} is
{unless I erred}
5,10,2,8,4,12,6,9,3,7,11,1
which gives the GCD-sum of
5+2+2+4+4+6+3+3+1+1+1 = 32)

Now, the sequence of maximum sums matches, for the terms given, sequence 
A063985 of the EIS:

http://www.research.att.com/projects/OEIS?Anum=A063985

This sequence is defined as

sum{k=1 to m} (k - phi(k)),

where phi(k) is the Euler totient function.

Are these two sequences the same for all terms?

thanks,
Leroy Quet





More information about the SeqFan mailing list