%I #61 Dec 19 2024 13:58:29

%S 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,

%T 20,20,21,22,23,24,24,25,26,27,28,29,30,30,31,32,33,34,35,35,36,37,38,

%U 39,40,41,42,42,43,44,45,46,47,48,48,49,50,51,52,53,54,55

%N 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.

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

%C This sequence seems related to both A183867 and A028387.

%C 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.

%C 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).

%C 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

%H <a href="http://grid01.ciirc.cvut.cz/~thibault/qsynt.html">QSYNT</a>

%H Bill McEachen, <a href="/A265436/a265436.txt">Original Python program</a>.

%F 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

%e 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.

%e 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.

%e 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.

%e 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.

%t 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, m<n, m++, pp = pairs[m, n]; If[Sort[pp, csum ] == Sort[pp, cprod], Return[m]]]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 70}] (* _Jean-François Alcover_, Dec 20 2015 *)

%o (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;}

%o vsums(v) = vector(#v, k, v[k][1] + v[k][2]);

%o vprods(v) = vector(#v, k, v[k][1] * v[k][2]);

%o 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;}

%o 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);}

%o one(n, m) = {ok = 0; while (!ok, if (! isok(n, m), m++, ok=1)); m;}

%o lista(nn) = {m = 1; for (n=1, nn, newm = one(n, m); print1(newm, ", "); m = newm;);}

%o \\ _Michel Marcus_, Dec 09 2015

%o (Python)

%o def f1(X):

%o x = X

%o for y in range (1,X + 1): # ie 1 thru X

%o x = ((((((2 + y) * y) // (2 + x)) - 2) + x) // (2 + x)) + x # floor division

%o return x

%o def f0(X):

%o return (f1(X) + 1) - X

%o for x in range(1000):

%o print (f0(x))

%o # _Bill McEachen_, Jun 12 2024 (via the QSYNT link)

%Y Cf. A028387, A035106, A060018, A183867.

%K nonn

%O 1,5

%A _Bill McEachen_ and _Michel Marcus_, Dec 09 2015