Optimization Amplifies — LessWrong

Given m , what is the least number n ≥ 2 such that for 2 ≤ k ≤ m , the base k representation of n consists entirely of 0s and 1s? If you want to think about it yourself, stop reading. For m =2, n =2. For m =3, n =3. For m =4, n =4. For m =5, n =82,000. Indeed, 82,000 is 10100000001010000 in binary, 11011111001 in ternary, 110001100 in base 4, and 10111000 in base 5. What about when m =6? So, a mathematician might tell you that this is an open problem. It is not known if there is any n ≥ 2 which consists of 0s and 1s in bases 2 through 6. A scientist, on the other hand, might just tell you that clearly no such number exists. There are 2 k − 1 numbers that consist of k 0s and 1s in base 6. Each of these has roughly log 5 ( 6 ) ⋅ k digits in base 5, and assuming things are roughly evenly distributed, each of these digits is a 0 or a 1 with "probability" 2 / 5 . The "probability" that there is any number of length k that has the property is thus less than 2 k ⋅

saved by

• Klaudia U.