|
%I #29 Jul 16 2024 15:41:06
%S 50221174,251105873,346765253,387421583,394594943,526392311,645706283,
%T 657658237,689544697,689544698,695921989,774842071,780158669,782015431
%N Numbers that may be built from fewer ones by using / in addition to +, -, and *.
%C 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).
%C Both b(n) and A091333(n) are also often equal to A005245(n), the number of ones required to build n using just + and *.
%C 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.
%C 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.
%H Glen Whitney, <a href="/A348069/a348069.c.txt">C program to discover numbers in this sequence</a>
%e 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.
%e 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.
%e The next three values with their respective minimal expressions:
%e 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].
%e 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].
%e 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).
%e Additional known values with their respective complexities:
%e a(i) b(a(i)) A091333(a(i)) A005245(a(i))
%e --------- ------- ------------- -------------
%e 526392311 62 63 63
%e 645706283 62 63 63
%e 657658237 62 63 64
%e 689544697 62 63 63
%e 689544698 62 63 63
%e 695921989 62 63 63
%e 774842071 62 63 63
%e 780158669 63 64 64
%e 782015431 62 63 63
%e Thus 782015431 is the smallest value in this sequence at which b decreases from one entry to the next.
%Y Cf. A253177.
%Y Cf. A091333 and A005245 (other integer complexity measures).
%K nonn,more
%O 1,1
%A _Glen Whitney_, Sep 27 2021
| 