A302245 - OEIS

%I #38 Apr 11 2018 04:59:22

%S 1,2,3,5,7,8,11,11,15,15,19,19,23,23,27,27,31,31,35,35,39,39,43,43,47,

%T 47,51,51,55,55,59,59,63,63,67,67,71,71,75,75,79,79,83,83,87,87,91,91,

%U 95,95,99,99,103,103,107,107,111,111,115,115,119,119,123,123

%N Maximum remainder of p*q divided by p+q with 0 < p <= q <= n.

%F Conjecture: a(n) = 2*(n - 2) - (-1)^n for n > 6.

%F From _Altug Alkan_ and _Robert Israel_, Apr 05 2018: (Start)

%F Proof of conjecture:

%F For n >= 3 odd, we do have p=n-2, q=n, p*q = n^2-2*n = (n-3)/2 * (p+q) + 2*n-3, so a remainder of 2*n-3 is possible.

%F The only possible p <= q <= n with p+q-1 > 2*n-3 are p=n-1,q=n and p=n,q=n, neither of which can improve on this:

%F For p=q=n, p*q = (n-1)/2 * (p+q) + n with n <= 2*n-3.

%F For p=n-1, q=n, p*q = (n-1)/2 * (p+q) + (n-1)/2 with (n-1)/2 < n

%F For n >= 8 even, we have all the cases that worked for n-1, with maximum remainder 2*(n-1)-3 = 2*n-5, and additional possibilities q=n,p=n-3 to n, which don't improve on this:

%F For p=n-3, q=n, p*q = (n/2-1)*(p+q) + n/2-3 with n/2-3 < 2*n-5

%F For p=n-2, q=n, p*q = (n/2-1)*(p+q) + n-2 with n-2 < 2*n-5

%F For p=n-1, q=n, p*q = (n/2-1)*(p+q) + 3*n/2-1 with 3*n/2-1 < 2*n-5.

%F For p=n, q=n, p*q = (n/2)*(p+q) + 0.

%F (End)

%e For n=2 the three possible pairs of positive numbers are enumerated in the following table

%e (i,j) (i*j) (i+j) (i*j) mod (i+j)

%e (1,1)   1     2          1

%e (1,2)   2     3          2

%e (2,2)   4     4          0

%e The greatest remainder is 2 then a(2)=2, and similarly for n=3 the corresponding table is

%e (i,j) (i*j) (i+j) (i*j) mod (i+j)

%e (1,1)   1     2          1

%e (1,2)   2     3          2

%e (2,2)   4     4          0

%e (1,3)   3     4          3

%e (2,3)   6     5          1

%e (3,3)   9     6          3

%e The greatest remainder is 3, then a(3)=3.

%p 1, 2, 3, 5, 7, 8, seq(2*(n-2)-(-1)^n, n=7..100); # _Robert Israel_, Apr 05 2018

%t a[n_]:=Table[Table[Mod[i*j, i + j], {i, 1, j}], {j, 1, n}]//Flatten//Max;

%t Table[a[n], {n, 1, 64}]

%o (PARI) a(n) = vecmax(vector(n, q, vecmax(vector(q, p, (p*q) % (p+q))))); \\ _Michel Marcus_, Apr 05 2018

%o (PARI) a(n) = if(n<7,(n+2)*(n+4)\9, 2*(n-2)-(-1)^n); \\ _Altug Alkan_, Apr 07 2018

%Y Cf. A168269, A302446.

%K nonn,easy

%O 1,2

%A _Andres Cicuttin_, Apr 03 2018