A255641 -id:A255641 - 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).

A253177 Numbers which can be expressed with fewer 1s using +, -, and * than with + and *.

Original entry on oeis.org

23, 47, 53, 59, 69, 71, 89, 94, 106, 107, 134, 141, 142, 143, 159, 161, 167, 177, 178, 179, 188, 191, 207, 212, 213, 214, 215, 227, 233, 239, 242, 251, 263, 265, 267, 268, 269, 282, 283, 284, 286, 287, 299, 311, 317, 318, 319, 321

Offset: 1

Charles R Greathouse IV, Mar 23 2015

nonn

Numbers n such that A005245(n) > A091333(n). Is it true that a(n) ~ n?

			23 = 2*3*4 - 1 = 3*(2*3 + 1) + 2 can be written with 10 1s using subtraction but requires 11 without, hence 23 is a member. Here the digits 2, 3, and 4 are used for clarity, but could be expanded to (1+1), (1+1+1), etc.

Charles R Greathouse IV, Table of n, a(n) for n = 1..3128
Index to sequences related to the complexity of n

Cf. A091333, A005520, A005245, A173419, A255641.

A347983 Smallest number requiring n 1's to build using +, -, *, and ^.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 11, 13, 21, 39, 41, 43, 115, 173, 276, 413, 823, 1389, 1654

Offset: 1

Glen Whitney, Sep 22 2021

Until n = 10 the terms are equal to A003037(n) where subtraction is not allowed; that is the same value of n at which A255641 and A005520, which also differ only in allowing subtraction, diverge.

The values given are all of the exact ones available from the program posted with A091334, which ignores intermediate results over 2^65, but which nevertheless is provably exact for small values of n up to complexity 19. Running the same program with a larger complexity limit leads to the uncertain (but highly likely correct) values for a(20) through a(26): 3306, 3307, 8871, 22261, 31661, 69467, 155051. (These values were stable for different intermediate-result cutoffs from 2^33 through 2^65, supporting their likely correctness.)

			a(7) = 11 because 2=1+1, 3=1+1+1, 4=1+1+1+1, 5=1+1+1+1+1, 6=(1+1)(1+1+1), 7=(1+1)(1+1+1)+1, 8=(1+1)^(1+1+1), 9=(1+1+1)^(1+1), and 10=(1+1+1)^(1+1)+1, all requiring fewer than seven ones, whereas a minimal way of expressing 11 is (1+1+1)^(1+1)+1+1 with seven ones. (Subtraction does not actually play a necessary role in a minimal expression until 15=(1+1)^(1+1+1+1)-1, and does not affect the value of a(n) until n = 10 because 23=(1+1+1)(1+1)^(1+1+1)-1 would otherwise be the smallest number requiring ten ones.)

Least inverse (or records) of A091334.

Cf. least inverses A003037, A005520, A255641 of other such "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

A253177 Numbers which can be expressed with fewer 1s using +, -, and * than with + and *.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A347983 Smallest number requiring n 1's to build using +, -, *, and ^.

Views

Author

Keywords

Comments

Examples

Crossrefs