4 ms·

"I don't ask this problem, because I'm dying to know the 12th digit of the fibonacci sequence. I already know that's 144." That was certainly news to me. Who w

by ckuehne 16y ago

"I don't ask this problem, because I'm dying to know the 12th digit of the fibonacci sequence. I already know that's 144." That was certainly news to me. Who would have thought that the 12th _digit_ of the Fibonacci sequence is 144.

wbhart 16y ago
Interesting problem: for what base (if any) is this actually true. Now there's an actual interview question!
- jerf 16y ago
  Your problem is either ill-specified or trivial. The trivial answer is any base greater than 144, allowing all numbers up to that point to be one-digit each. Since to have a 144 "digit" we must already be in base > 144, as chosen by what appears to be your problem, there's no other possible solution. (I'm assuming integral bases to keep things well-enough contained for a simple HN post here.) "Ill-specified" is if you're still playing fast-and-loose with the meaning of "digit"; I've tried to adopt the closest meaning I can come up with where 144 can be a "digit" but in conventional terms the "digit" refers not to the number, but the encoding, in which case 144 can't be a "digit". It may be the ordinal identifier of some digit, but it is not itself a digit, which by definition is a single atomic unit in your number digitization scheme. (That is, your atomic glyph may itself be encoded by multiple glyphs in another scheme, I could imagine representing base 1296 numbers (36 times 36) by definition as two base36 numbers with the obvious English encoding, but in the base1296 encoding a "digit" would be two alphanums in the English encoding. Gotta make sure to keep all the layers straight; there's the abstract number, there's the digit breakdown in a given base, and there's the serialization of those digits in some concrete format.)
  - wbhart 16y ago
    The trick with such questions is finding an interpretation which is neither over nor underspecified and for which the answer is not obvious. The question only supposes that 144 is a digit in the base. We might also write the fibonacci sequence in whatever base is chosen, i.e. the fibonnaci sequence is no longer 1, 1, 2, 3, 5, 8, .... but may be 31, 31, 32, 33, 39, .... To keep the problem simple, let's suppose that our digits are represented by glyphs which just happen to be composed of ordered sequences of decimal digits and that the glyph m corresponds to a lesser digit than the glyph n only if m < n when considered as decimal numbers. Thus we could have 37 < 144 but not 144 < 37 for glyphs 37 and 144. This already places some hard restrictions, e.g. as 144 is a digit, 1 and 4 cannot both be digits. Now I think the problem is neither trivial, nor overspecified (though I didn't actually check the latter). I certainly agree it was underspecified.

by ckuehne 16y ago

wbhart 16y ago

Interesting problem: for what base (if any) is this actually true. Now there's an actual interview question!

jerf 16y ago
Your problem is either ill-specified or trivial. The trivial answer is any base greater than 144, allowing all numbers up to that point to be one-digit each. Since to have a 144 "digit" we must already be in base > 144, as chosen by what appears to be your problem, there's no other possible solution. (I'm assuming integral bases to keep things well-enough contained for a simple HN post here.) "Ill-specified" is if you're still playing fast-and-loose with the meaning of "digit"; I've tried to adopt the closest meaning I can come up with where 144 can be a "digit" but in conventional terms the "digit" refers not to the number, but the encoding, in which case 144 can't be a "digit". It may be the ordinal identifier of some digit, but it is not itself a digit, which by definition is a single atomic unit in your number digitization scheme. (That is, your atomic glyph may itself be encoded by multiple glyphs in another scheme, I could imagine representing base 1296 numbers (36 times 36) by definition as two base36 numbers with the obvious English encoding, but in the base1296 encoding a "digit" would be two alphanums in the English encoding. Gotta make sure to keep all the layers straight; there's the abstract number, there's the digit breakdown in a given base, and there's the serialization of those digits in some concrete format.)
- wbhart 16y ago
  The trick with such questions is finding an interpretation which is neither over nor underspecified and for which the answer is not obvious. The question only supposes that 144 is a digit in the base. We might also write the fibonacci sequence in whatever base is chosen, i.e. the fibonnaci sequence is no longer 1, 1, 2, 3, 5, 8, .... but may be 31, 31, 32, 33, 39, .... To keep the problem simple, let's suppose that our digits are represented by glyphs which just happen to be composed of ordered sequences of decimal digits and that the glyph m corresponds to a lesser digit than the glyph n only if m < n when considered as decimal numbers. Thus we could have 37 < 144 but not 144 < 37 for glyphs 37 and 144. This already places some hard restrictions, e.g. as 144 is a digit, 1 and 4 cannot both be digits. Now I think the problem is neither trivial, nor overspecified (though I didn't actually check the latter). I certainly agree it was underspecified.