Awesome explanation and a nice solution! I've recently started realizing the power of math and taking a very huge interest in it. Also, just wanted to bring to your attention a minor typo in your article. Under the section "The Computation" you have "2+3+4+5+7+11 = 28" when I'm sure you meant '2+3+5+7+11 = 28'
Thanks.
wilson
· 2 years ago
While those are some snazzy puzzles, I imagine that they are not at all along the lines of the work that anyone hired by Facebook will actually be doing... They are more like brain teasers to see how motivated you are and to see if you can solve odd problems like that.
Jesse
· 2 years ago
wilson,
Oh, for sure. I don't think anyone is claiming they're anything more than puzzles (although Landau's function is not without its uses). But it does demonstrate ones ability to reason analytically and translate that reasoning into code.
Saumitro
· 1 year ago
I believe there is a slight error in your calculations. The problem is right on the "threshold length" of 4. The maximum LCM of a length four partition of 26 is 1155, corresponding to the partition [11,7,5,3], not 1260. The set you specified [4,5,7,9] isn't a partition of 26; it adds up to 25. However, you can insert a 1 in the set, leaving the lcm unaffected which gives you the max lcm of 1260 for length 5 and beyond.
I solved the problem on a lazy afternoon last year, and was curious about its origins and other solutions, and I came across your page. The origin as far as I can tell is an ancient 70s paper entitled "Control Structure Abstractions of the Backtracking Programming Technique". They called the problem "Malicious Secretary" (IMHO, a much better title than the misleading "Korn Shell")
Jesse
· 1 year ago
Saumitro,
In the general case we're not computing partitions of 26, but rather the value of Laundau's function. We only have to consider partitions of 26 because we're left with too few letters to fill each cycle.
Also, in the general case, I'm talking about cycles in permutations rather than partitions. Why I list 4 rather than 5 is a side-effect of the mathematical notation: cycles of length one are left out. Thus, up to conjugation, the permutation of interest is (1..4)(5..9)(10..16)(17..25). At least, that's how we'd write it in group theory.
So, IOW, if we have at least four distinct letters we can put one in each of those cycles, producing a game that lasts 1260 rounds. That the fifth, single-element cycle is left unfilled has no impact, as you said.
As for the name, I got it from Facebook. Blame them. :P
Saumitro
· 1 year ago
Ah, I used an incorrect constraint of sum(cycle-lengths)=26 instead of sum(cycle-lengths)
Saumitro
· 1 year ago
[got truncated?] Ah, I used an incorrect constraint of sum(cycle-lengths)=26 instead of sum(cycle-lengths)
the landau function in the code section seems incorrect. landau(29) gives 2310, while g(29) from http://www.research.att.com/~njas/sequences/A00... is 2520 (i.e 9*8*7*5). i can see no reason to assume that g(n) is always lcm(m, g(n - m)) for some m.
Jesse Farmer
· 11 months ago
You're right, Mike. Unfortunately I don't have time to correct it myself.
I thought I found a solution that didn't require a full search of the problem space. Guess I was too clever.
Know of any papers that outline an efficient algorithm for calculating Landau's function?
All Comments
Thanks.
Oh, for sure. I don't think anyone is claiming they're anything more than puzzles (although Landau's function is not without its uses). But it does demonstrate ones ability to reason analytically and translate that reasoning into code.
I solved the problem on a lazy afternoon last year, and was curious about its origins and other solutions, and I came across your page. The origin as far as I can tell is an ancient 70s paper entitled "Control Structure Abstractions of the Backtracking Programming Technique". They called the problem "Malicious Secretary" (IMHO, a much better title than the misleading "Korn Shell")
In the general case we're not computing partitions of 26, but rather the value of Laundau's function. We only have to consider partitions of 26 because we're left with too few letters to fill each cycle.
Also, in the general case, I'm talking about cycles in permutations rather than partitions. Why I list 4 rather than 5 is a side-effect of the mathematical notation: cycles of length one are left out. Thus, up to conjugation, the permutation of interest is (1..4)(5..9)(10..16)(17..25). At least, that's how we'd write it in group theory.
So, IOW, if we have at least four distinct letters we can put one in each of those cycles, producing a game that lasts 1260 rounds. That the fifth, single-element cycle is left unfilled has no impact, as you said.
As for the name, I got it from Facebook. Blame them. :P
http://www.google.com/search?q=0xFACEB00C+%2F+4...
Your solution makes for interesting reading -- thanks for writing it up.
Here's my own page on 0xFACEB00C >> 2 in decimal.
I thought I found a solution that didn't require a full search of the problem space. Guess I was too clever.
Know of any papers that outline an efficient algorithm for calculating Landau's function?