|
| |
|
|
A348069
|
|
Numbers that may be built from fewer ones by using / in addition to +, -, and *.
|
|
5
|
|
|
|
50221174, 251105873, 346765253, 387421583, 394594943, 526392311, 645706283, 657658237, 689544697, 689544698, 695921989, 774842071, 780158669, 782015431
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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:
--------- ------- ------------- -------------
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.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more,changed
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
