A265436 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

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

LINKS

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

QSYNT

Bill McEachen, Original Python program.

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

EXAMPLE

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.

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, 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 *)

PROG

(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):