Official xkcd puzzle [solution]
Moderators: jestingrabbit, Moderators General, Prelates
Official xkcd puzzle [solution]
So, this solution is more of a "I'm not happy with the requirements for success," than a serious solution.
For 0 <= n <= 35, and for n = 71, define F(n) as in the problem description.
For 35 < n < 71, and for n > 71, let F(n) = smallest positive integer not in { F(0), ..., F(n1) }.
Using this algorithm, we get
F(36) = 32
F(37) = 33
F(38) = 34
...
F(45) = 41
After a while, F turns into the identity function, and F(31337) = 31337.
The issue here is that there should be infinitely many functions F that satisfy your demands. We can generate them by picking what you think is the right answer, and then just permuting the values you didn't specify.
So basically, I guess you shouldn't accept the first solution  if you do, then this ridiculous thing is the first solution  or, you should add stricter criteria for success.
For 0 <= n <= 35, and for n = 71, define F(n) as in the problem description.
For 35 < n < 71, and for n > 71, let F(n) = smallest positive integer not in { F(0), ..., F(n1) }.
Using this algorithm, we get
F(36) = 32
F(37) = 33
F(38) = 34
...
F(45) = 41
After a while, F turns into the identity function, and F(31337) = 31337.
The issue here is that there should be infinitely many functions F that satisfy your demands. We can generate them by picking what you think is the right answer, and then just permuting the values you didn't specify.
So basically, I guess you shouldn't accept the first solution  if you do, then this ridiculous thing is the first solution  or, you should add stricter criteria for success.
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
So... here's a pretty general rant about this sort of thing. Some people criticize the sort of patternfinding problems we see in the integer sequence posts to this forum and some intelligence tests. "There are an infinite number of possible sequences!" they claim, technically correct in a missingthewholepoint sort of way. But the object is not to find the unique solution; the object is to find the best solution.
Far from being artificial, or something people of rigorous mind would not deal with, this sort of thing comes up all the time in math and science. For instance, the value of a geometric series can be written:
1 + r + r^2 + r^3 + ... = 1 / (1  r)
What sort of mathematician would you be if you insisted that the lefthandside is not well defined, that there are an infinite number of series that start thus? Do you think other mathematicians would consider you terribly clever for pointing that out?
The search for patterns that aren't completely and uniquely specified by the data is the whole idea behind inductive reasoning. It's possibly the most important skill in all of science. So when it's obviously a crucial piece of a question that gets asked, don't go ignoring it by saying that "stricter criteria" are needed, huh?
Edit: deductive > inductive. I always get those mixed up; thanks for pointing it out!
Far from being artificial, or something people of rigorous mind would not deal with, this sort of thing comes up all the time in math and science. For instance, the value of a geometric series can be written:
1 + r + r^2 + r^3 + ... = 1 / (1  r)
What sort of mathematician would you be if you insisted that the lefthandside is not well defined, that there are an infinite number of series that start thus? Do you think other mathematicians would consider you terribly clever for pointing that out?
The search for patterns that aren't completely and uniquely specified by the data is the whole idea behind inductive reasoning. It's possibly the most important skill in all of science. So when it's obviously a crucial piece of a question that gets asked, don't go ignoring it by saying that "stricter criteria" are needed, huh?
Edit: deductive > inductive. I always get those mixed up; thanks for pointing it out!
Last edited by Cosmologicon on Fri Jan 19, 2007 7:39 pm UTC, edited 1 time in total.
Cosmologicon wrote:But the object is not to find the unique solution; the object is to find the best solution.
That's sort of the point of my post? That maybe it's inappropriate to award both the first response and the best response, since the first response is trivial.
Aside from that, I don't think my post is totally useless. It runs in O(nÂ²) time  if another proposed algorithm isn't asymptotically faster than mine, it's probably not the "best" solution. In that way, my "solution" is a benchmark for others, no?
The search for patterns that aren't completely and uniquely specified by the data is the whole idea behind deductive reasoning.
I would have called that "inductive reasoning"  obviously such integersequence problems, like science, suffer from the problem of induction  but to each his own.

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
Erasmus wrote:I would have called that "inductive reasoning"  obviously such integersequence problems, like science, suffer from the problem of induction  but to each his own.
I'd say definitely not to each his own. It's inductive reasoning, like pretty much all of science, not deductive.
GENERATION 1i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Erasmus wrote:Cosmologicon wrote:But the object is not to find the unique solution; the object is to find the best solution.
That's sort of the point of my post? That maybe it's inappropriate to award both the first response and the best response, since the first response is trivial.
Aside from that, I don't think my post is totally useless. It runs in O(nÂ²) time  if another proposed algorithm isn't asymptotically faster than mine, it's probably not the "best" solution. In that way, my "solution" is a benchmark for others, no?The search for patterns that aren't completely and uniquely specified by the data is the whole idea behind deductive reasoning.
I would have called that "inductive reasoning"  obviously such integersequence problems, like science, suffer from the problem of induction  but to each his own.
Actually, your algorithm runs in O(1) time as you need only check that your input is a least 71 (O(1) time) and if it is, you don't need to do anything to output the input. Any similar algorithm will do the same. The judge of how good a solution is should not be it's computing time, but rather how simple it is to describe the algorithm, and you should be able to describe it without breaking it down into cases, unless the cases are all infinite, and not complicated (for example do x if n<100, otherwise do y is not a good solution, but do foo if n is even, and do bar if n is odd might be),
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 BaldAdonis
 Posts: 81
 Joined: Fri Nov 24, 2006 11:32 pm UTC
Cosmologicon wrote:So... here's a pretty general rant about this sort of thing. Some people criticize the sort of patternfinding problems we see in the integer sequence posts to this forum and some intelligence tests. "There are an infinite number of possible sequences!" they claim, technically correct in a missingthewholepoint sort of way. But the object is not to find the unique solution; the object is to find the best solution.
Far from being artificial, or something people of rigorous mind would not deal with, this sort of thing comes up all the time in math and science. For instance, the value of a geometric series can be written:
1 + r + r^2 + r^3 + ... = 1 / (1  r)
What sort of mathematician would you be if you insisted that the lefthandside is not well defined, that there are an infinite number of series that start thus? Do you think other mathematicians would consider you terribly clever for pointing that out?
The search for patterns that aren't completely and uniquely specified by the data is the whole idea behind inductive reasoning. It's possibly the most important skill in all of science. So when it's obviously a crucial piece of a question that gets asked, don't go ignoring it by saying that "stricter criteria" are needed, huh?
Edit: deductive > inductive. I always get those mixed up; thanks for pointing it out! :)
So in my final year of college, I took a math elective on Knot Theory. One day we were talking about crossing numbers, particularly the number of distinct prime knots with a given crossing number. Our book had a table giving the counts up through seventeen or something (I really don't remember specifics) and a few of us got on the subject of trying to determine the next in the series.
There was a group of freshmen that decided to try to tackle the exercise by doing some kind of statistical analysis of some sort, I don't really remember. But I was taking a numerical analysis class that semester, so I interpolated all the data points and the next day at class, told everyone about how I had "noticed" that all the data points happened to conform exactly to a simple sixteenthdegree polynomial (with ten or twentydigit coefficients, of course).
It was pretty hilarious.
your = belonging to you
you're = you aretheir = belonging to them
they're = they are
there = not here
you're = you aretheir = belonging to them
they're = they are
there = not here
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Framling wrote:There was a group of freshmen that decided to try to tackle the exercise by doing some kind of statistical analysis of some sort, I don't really remember. But I was taking a numerical analysis class that semester, so I interpolated all the data points and the next day at class, told everyone about how I had "noticed" that all the data points happened to conform exactly to a simple sixteenthdegree polynomial (with ten or twentydigit coefficients, of course).
It was pretty hilarious.
Indeed, that is quite an observation you made about that particular sequence. I'm not surprised they were astonished.
On the subject of astonishing mathematical properties, did you know that the French Curve, which is commonly used in drawing, has the interesting property that the tangent at the lowest point, however it is oriented, is horizontal?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
skeptical scientist wrote:Framling wrote:There was a group of freshmen that decided to try to tackle the exercise by doing some kind of statistical analysis of some sort, I don't really remember. But I was taking a numerical analysis class that semester, so I interpolated all the data points and the next day at class, told everyone about how I had "noticed" that all the data points happened to conform exactly to a simple sixteenthdegree polynomial (with ten or twentydigit coefficients, of course).
It was pretty hilarious.
Indeed, that is quite an observation you made about that particular sequence. I'm not surprised they were astonished.
On the subject of astonishing mathematical properties, did you know that the French Curve, which is commonly used in drawing, has the interesting property that the tangent at the lowest point, however it is oriented, is horizontal?
Hey! Stop plagiarising Feynman!!
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
jestingrabbit wrote:Hey! Stop plagiarising Feynman!!
That wasn't plagiarism, it was a deliberate reference that I figured about 90% of this forum would get.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
I see the pattern; I don't know if it has a simple formula, though.
Here's a complex formula:
Define ancillary function g(x) as:
If (int(x)) modulo 4 = 0, then g(x) = 0.
If (int(x)) modulo 4 = 1, then g(x) = 1.
If (int(x)) modulo 4 = 2, then g(x) = 3.
If (int(x)) modulo 4 = 3, then g(x) = 2.
Then f(x) = g(x) + 4g(x/4) + (4^2)g(x/4^2) + (4^3)g(x/4^3) + ...
Edit: Never mind, I misread the sequence. Gotta work harder.
Here's a complex formula:
Define ancillary function g(x) as:
If (int(x)) modulo 4 = 0, then g(x) = 0.
If (int(x)) modulo 4 = 1, then g(x) = 1.
If (int(x)) modulo 4 = 2, then g(x) = 3.
If (int(x)) modulo 4 = 3, then g(x) = 2.
Then f(x) = g(x) + 4g(x/4) + (4^2)g(x/4^2) + (4^3)g(x/4^3) + ...
Edit: Never mind, I misread the sequence. Gotta work harder.
Last edited by Ronfar on Mon Jan 22, 2007 6:56 am UTC, edited 1 time in total.
 Doug
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Who is online
Users browsing this forum: No registered users and 5 guests