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

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)
print("1, 1, ")
x=[1, 2]
maxx=50
final=[1, 2]
n=3
x.append(n)
oldLen=len(x)
while n<maxx:
   myLen=len(x)
   if myLen>oldLen:
      print (x[0], ", ", end="")
   s=[]
   p=[]
   z=[]
   for i in range(myLen-1):
      for j in range(i+1, myLen):
         s.append( x[i]+x[j] )
         p.append( x[i]*x[j] )
   z=list(zip( s, p ))
   y=[]
   y=sorted(z)
   sumsort=[]
   prodsort=[]
   for h5 in range(len(y)):
      vals, valp=y[h5]
      sumsort.append(vals)
      prodsort.append(valp)
   errer=0
   for j5 in range(len(sumsort)-1):
      for k5 in range(j5+1, len(sumsort)):
         if sumsort[k5]<sumsort[j5]:
            errer=1
            break
         if prodsort[k5]<prodsort[j5]:
            errer=1
            break
      if errer>0:
         break
   if errer<1:
      for ptr in range (len(y)-1):
         if y[ptr]==y[ptr+1]:
            errer=1
            break
   if errer>0:
      final.append(-x[0])
      x.pop(0)
   else:
      final.append(n)
      n+=1
      x.append(n)
   oldLen=myLen
# Bill McEachen, Dec 09 2015

Crossrefs

Cf. A028387, A035106, A060018, A183867.

Sequence in context: A116579 A156253 A346693 * A060151 A285902 A097330

Adjacent sequences: A265433 A265434 A265435 * A265437 A265438 A265439

Keyword

nonn

Author

Bill McEachen and Michel Marcus, Dec 09 2015

Status

approved