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

Author

Glen Whitney, Sep 27 2021

Keywords

• nonn
• more

Comments

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.

Examples

			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.
		

Links

• Glen Whitney, C program to discover numbers in this sequence

Crossrefs

Cf. A253177.

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