A265436 a(n) is the least m (1 <= m <= n) such that the set of pairs (x, y) of distinct terms from [m, n] can be ordered in such a way that the corresponding sums (x+y) and products (x*y) are monotonic.

1, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 17, 18, 19, 20, 20, 21, 22, 23, 24, 24, 25, 26, 27, 28, 29, 30, 30, 31, 32, 33, 34, 35, 35, 36, 37, 38, 39, 40, 41, 42, 42, 43, 44, 45, 46, 47, 48, 48, 49, 50, 51, 52, 53, 54, 55

Offset: 1

Author

Bill McEachen and Michel Marcus, Dec 09 2015

Keywords

• nonn

Comments

The pairs of distinct terms of [m,n] are first ordered according to their sums, then by their products.

This sequence seems related to both A183867 and A028387.

For A183867, let us define the sequence b(n) that gives the highest k such that a(k) = n. The data show that b(1)=4, b(2)=6, and the sequence b(n) begins 4, 6, 8, 9, 10, 12, 13, 15, 16, 17, 18, 20, ... and matches A183867(n+1) upwards.

Regarding A028387, its terms stem from the last (x,y) pair of each iteration, specifically its sum and product. From the examples provided below, for n=3 the last pair is (5,6) having sum 11. For n=5, the last pair is (9,20) having sum 29. These correspond to A028387(2) and A028387(4) respectively, and generally data from a(n) here produces A028387(n-1).

It appears that for n>5, the indices n where a(n)=a(n-1) are given by A035106(n). - Jean-François Alcover, Dec 20 2015

Examples

			For n=1, the only possible interval is [1,1], the set of distinct pairs is empty, so it satisfies the desired property, hence m=1 and a(1)=1.
For n=2, the candidate interval is [1,2], the set of distinct pairs is reduced to (1,2), which satisfies the order property hence m=1 and a(2)=1.
For n=3, the candidate interval is [1,2,3], with distinct pairs (1,2), (1,3), (2,3); and with corresponding sums (3,4,5) and products (2,3,6), that are monotonically ordered, hence m=1, so a(3)=1.
For n=5, the interval [1,5] fails to produce an ordering where both sums and products follow a monotonic order. But with m=2, here is a correct ordering: (5,6), (6,8), (7,10), (7,12), (8,15), (9,20); hence m=2 and a(5)=2.
		

Links

• QSYNT
• Bill McEachen, Original Python program.

Crossrefs

Cf. A028387, A035106, A060018, A183867.

Programs

Mathematica

pairs[m_, n_] := Flatten[Table[{x, y}, {x, m, n-1}, {y, x+1, n}], 1]; csum[ {x1_, y1_}, {x2_, y2_}] := x1+y1 <= x2+y2; cprod[{x1_, y1_}, {x2_, y2_}] := Which[x1 y1 < x2 y2, True, x1 y1 == x2 y2, x1+y1 <= x2+y2, True, False ]; a[1]=1; a[n_] := For[m=1, mJean-François Alcover, Dec 20 2015 *)

PARI

vpairs(n, m, nbp) = {v = vector(nbp); k = 1; for (i=m, n-1, for (j=i+1, n, v[k] = [i, j]; k++;)); v;}
vsums(v) = vector(#v, k, v[k][1] + v[k][2]);
vprods(v) = vector(#v, k, v[k][1] * v[k][2]);
cmpp(va, vb) = {sa = va[1]+va[2]; sb = vb[1]+vb[2]; if (sa > sb, return (1)); if (sa < sb, return (-1)); pa = va[1]*va[2]; pb = vb[1]*vb[2]; pa - pb;}
isok(n, m) = {nb = n-m+1; nbp = nb*(nb-1)/2; v = vpairs (n, m, nbp); perm = vecsort(v,cmpp,1); vs = vsums(v); vp = vprods(v); vss = vector(#vs, k, vs[perm[k]]); vps = vector(#vp, k, vp[perm[k]]); (vecsort(vps) == vps) && (vecsort(vss) == vss);}
one(n, m) = {ok = 0; while (!ok, if (! isok(n, m), m++, ok=1)); m;}
lista(nn) = {m = 1; for (n=1, nn, newm = one(n, m); print1(newm, ", "); m = newm;);}
\\ Michel Marcus, Dec 09 2015

Python

def f1(X):
  x = X
  for y in range (1,X + 1):  # ie 1 thru X
    x = ((((((2 + y) * y) // (2 + x)) - 2) + x) // (2 + x)) + x    # floor division
  return x
def f0(X):
  return (f1(X) + 1) - X
for x in range(1000):
  print (f0(x))
# Bill McEachen, Jun 12 2024 (via the QSYNT link)

Formula

Conjecture (derived from the assumed relationship with A035106): for n>5, if sqrt(4n+1) is an odd integer or sqrt(n+1) is an integer, then a(n) = a (n-1), otherwise a(n) = a(n-1)+1. - Jean-François Alcover, Dec 21 2015