A302245 Maximum remainder of p*q divided by p+q with 0 < p <= q <= n.
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, 47, 51, 51, 55, 55, 59, 59, 63, 63, 67, 67, 71, 71, 75, 75, 79, 79, 83, 83, 87, 87, 91, 91, 95, 95, 99, 99, 103, 103, 107, 107, 111, 111, 115, 115, 119, 119, 123, 123
Offset: 1
Examples
For n=2 the three possible pairs of positive numbers are enumerated in the following table (i,j) (i*j) (i+j) (i*j) mod (i+j) (1,1) 1 2 1 (1,2) 2 3 2 (2,2) 4 4 0 The greatest remainder is 2 then a(2)=2, and similarly for n=3 the corresponding table is (i,j) (i*j) (i+j) (i*j) mod (i+j) (1,1) 1 2 1 (1,2) 2 3 2 (2,2) 4 4 0 (1,3) 3 4 3 (2,3) 6 5 1 (3,3) 9 6 3 The greatest remainder is 3, then a(3)=3.
Programs
-
Maple
1, 2, 3, 5, 7, 8, seq(2*(n-2)-(-1)^n, n=7..100); # Robert Israel, Apr 05 2018
-
Mathematica
a[n_]:=Table[Table[Mod[i*j, i + j], {i, 1, j}], {j, 1, n}]//Flatten//Max; Table[a[n], {n, 1, 64}] -
PARI
a(n) = vecmax(vector(n, q, vecmax(vector(q, p, (p*q) % (p+q))))); \\ Michel Marcus, Apr 05 2018
-
PARI
a(n) = if(n<7,(n+2)*(n+4)\9, 2*(n-2)-(-1)^n); \\ Altug Alkan, Apr 07 2018
Formula
Conjecture: a(n) = 2*(n - 2) - (-1)^n for n > 6.
From Altug Alkan and Robert Israel, Apr 05 2018: (Start)
Proof of conjecture:
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.
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:
For p=q=n, p*q = (n-1)/2 * (p+q) + n with n <= 2*n-3.
For p=n-1, q=n, p*q = (n-1)/2 * (p+q) + (n-1)/2 with (n-1)/2 < n
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:
For p=n-3, q=n, p*q = (n/2-1)*(p+q) + n/2-3 with n/2-3 < 2*n-5
For p=n-2, q=n, p*q = (n/2-1)*(p+q) + n-2 with n-2 < 2*n-5
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.
For p=n, q=n, p*q = (n/2)*(p+q) + 0.
(End)