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,2

Links

Table of n, a(n) for n=1..64.

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)

Example

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.

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}]

Prog

(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

Crossrefs

Cf. A168269, A302446.

Sequence in context: A159556 A219643 A194798 * A028728 A286758 A106735

Adjacent sequences: A302242 A302243 A302244 * A302246 A302247 A302248

Keyword

nonn,easy

Author

Andres Cicuttin, Apr 03 2018

Status

approved