A253177 -id:A253177 - cp's OEIS frontend

A348069 Numbers that may be built from fewer ones by using / in addition to +, -, and *.

50221174, 251105873, 346765253, 387421583, 394594943, 526392311, 645706283, 657658237, 689544697, 689544698, 695921989, 774842071, 780158669, 782015431

Offset: 1

Glen Whitney, Sep 27 2021

Consider an integer complexity measure b(n) which is the number of ones required to build n using +, -, *, and /, where the latter operation is strict integer division, i.e., n/d is defined only when d|n. In other words, b(n) is defined identically to A091333(n) except that division is also allowed. Clearly for all n, b(n) <= A091333(n). This sequence lists the integers k for which b(k) < A091333(k).
Both b(n) and A091333(n) are also often equal to A005245(n), the number of ones required to build n using just + and *.
For the first 14 values of a, b(a(i)) = A091333(a(i)) - 1; it seems likely, however, that this difference will increase for larger values.
Computing all n such that b(n) <= 64 reveals the following numbers that must appear in this sequence, with their b-values in brackets: 1011597943 [63], 1032855583 [63], 1035512789 [63], 1038141563 [64], 1040295757 [63], 1040295759 [63], 1162264748 [63], 1162264749 [63], 1183784827 [63], 1183784828 [63], 1183784829 [63], 1292730233 [64], 1370320619 [64], 1376697911 [64], 1377760793 [64], 1378292233 [64], 1379886557 [64], 1542507503 [64], 1556856409 [64], 1571205317 [64].  However, because the least n for which b(n) = 65 is A255641(65) = 913230103 < 1011597943, it's not necessarily the case that the next entry in a after 782015431 is 1011597943, although it's likely; and given the examples where the b-values decrease for successive terms of a, these listed numbers are quite likely not all consecutive terms of a.

			The smallest n for which b(n) as defined in the Comments is strictly less than A091333(n) is 50221174, because 50221174 = (7*3^15 - 1)/2, which requires b(7) + 15*b(3) + 1 + 2 = 6 + 15*3 + 1 + 2 = 54 ones to express with these operations, whereas A091333(a(1)) = A005245(a(1)) = 55 by virtue of the minimal expression 50221174 = 3(2*3*5(2*2*3(3*2+1)(3^4(3^4+1)+1)+1)+1)+1 requiring 3+2+3+5+2+2+3+3+2+1+3*4+3*4+1+1+1+1+1 = 55 ones. Thus the first element of the sequence a is 50221174.
The next smallest n with b(n) < A091333(n) is 251105873 = (5*7*3^15 + 1)/2, requiring 59 ones, as compared with the minimal expression 2^2(3^2(3*2^2+1)(2*3(2^3*3^5(3^2*5+1)+1)+1)+1)+1 showing A091333(a(2)) = A005245(a(1)) = 60, so the second term of a is 251105873.
The next three values with their respective minimal expressions:
346765253 = (3^14(2^4*3^2 + 1) + 1)/2 [60 ones] = 2((2^2*3^4+1)(2*3^2(2^3*3^2+1)(3^4*5+1)+1)+1)+1 [61 ones].
387421583 = (3^7(2*3^11+1)+1)/2 [60 ones] = 2(2*5*7(2^2*3+1)(2^2*3^6(2^3*3^2+1)+1)+1)+1 [61 ones].
394594943 = (3^15(2*3^3 + 1) + 1)/2 [60 ones] = 2*7(2*3^3(5(2^4*3^2-1)(3^6+1)+1)-1)+1 [61 ones] = 3(2^2*3+1)(2*3^2(2*7(2*3^3+1)(3^6+1)+1)+1)+2 [62 ones]. Thus n=394594943 is the least n such that b(n) < A091333(n) < A005245(n).
Additional known values with their respective complexities:
     a(i)   b(a(i)) A091333(a(i)) A005245(a(i))
  --------- ------- ------------- -------------
  526392311    62         63            63
  645706283    62         63            63
  657658237    62         63            64
  689544697    62         63            63
  689544698    62         63            63
  695921989    62         63            63
  774842071    62         63            63
  780158669    63         64            64
  782015431    62         63            63
Thus 782015431 is the smallest value in this sequence at which b decreases from one entry to the next.

Glen Whitney, C program to discover numbers in this sequence

Cf. A253177.

Cf. A091333 and A005245 (other integer complexity measures).

A346742 Numbers that may be built from fewer ones using floor(j/k) in addition to +, -, and *.

Original entry on oeis.org

1860043, 3198487, 4782847, 5580129, 6111571, 9300217, 9566302, 9595461, 9595462, 9654511, 10678027, 12725059, 12843157, 13551745, 14349271, 14614627, 16740391, 17094685, 18334713, 18334714, 19220449, 27900651, 28698178, 28701094, 29494975, 31620739, 32034081, 33484063, 34100797, 35872267, 37998031

Offset: 1

Glen Whitney, Sep 28 2021

nonn

Consider an integer complexity measure c(n) which is the number of ones required to build n using +, -, *, and "floor division" which for convenience will be written in this entry (after Python notation) j//k = floor(j/k). In other words, c(n) is defined identically to A091333(n) except that this floor division is also allowed, and identically to the complexity b(n) described in A348069 except that division is extended to all pairs of natural numbers by taking the floor of the quotient. Clearly for all n, c(n) <= b(n) <= A091333(n). This sequence lists the integers k for which c(k) < A091333(k).
Because of the inequality c(n) <= b(n) <= A091333(n), every entry in A348069 will eventually appear in this sequence. For example, the first term of A348069 is 50221174 = (7*3^15)//2, so we have c(50221174) = 53, b(50221174) = 54, and A091333(50221174) = 55.
The extended domain of division means that terms of this sequence are much more frequent than A348069, but it's still quite rare for division to provide more compact expressions for natural numbers (except in the presence of exponentiation, see A348089).

			The smallest n for which c(n) as defined in the comments is strictly less than A091333(n) is 1860043, because 1860043 = (7*3^12)//2 which requires c(7) + 12*c(3) + c(2) = 6 + 12*3 + 2 = 44 ones to express with these operations, whereas A091333(1860043) = A005245(1860043) = 45 by virtue of the minimal expression 1860043 = 2(2^2*5*7(3^4(3^4+1)+1)+1)+1 requiring 2+2*2+5+6+3*4+3*4+1+1+1+1 = 45 ones. Hence, the first term in this sequence is 1860043.
The next three terms with their respective minimal expressions:
3198487 = (3^9(2^2*3^4+1))//2 [46 ones] = 2*3(3^2(2^2*3*5+1)(2^2*3^5-1)+2)+1 [47 ones] = 2*3(2(7(2^2*3+1)(2^2*3(3^5+1)+1)+1)+1)+1 [48 ones]. Thus n=319487 is the least n for which c(n) < A091333(n) < A005245(n).
4782847 = (3^5(2*3^9-1))//2 [47 ones] = 2*3(2*5(3^2(2^2*3^3(3^4+1)+1)+1)+1)+1 [48 ones]
5580129 = 3*1860043 = 3((7*3^12)//2) [47 ones] = 2^3(3*5*7(3^4(3^4+1)+1)+1)+1 [48 ones]. Note this example critically takes advantage of the fact that * and // are not associative.

Cf. A253177 and A348069.

Cf. A091333 and A005245 (other integer complexity measures).

cp's OEIS Frontend

A348069 Numbers that may be built from fewer ones by using / in addition to +, -, and *.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs