## Official xkcd puzzle [solution]

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Erasmus
Posts: 26
Joined: Wed Sep 27, 2006 10:13 am UTC

### 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(n-1) }.

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 pattern-finding 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 missing-the-whole-point 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 left-hand-side 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.

Erasmus
Posts: 26
Joined: Wed Sep 27, 2006 10:13 am UTC
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 integer-sequence problems, like science, suffer from the problem of induction -- but to each his own.

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:
Erasmus wrote:I would have called that "inductive reasoning" -- obviously such integer-sequence 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 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

e-Gor
Posts: 3
Joined: Tue Jan 16, 2007 10:43 pm UTC
ok, despite all that discussion I went ahead and tried it.

 removed - I broke something. I'll try and fix it tomorrow...[/edit]

skeptical scientist
closed-minded 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 integer-sequence 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

Posts: 81
Joined: Fri Nov 24, 2006 11:32 pm UTC
Didn't mean to hash this all up again. There is already an extensive solution thread. I just wanted to know which was deemed the most elegant.

Framling
Posts: 62
Joined: Sat Dec 02, 2006 6:58 am UTC
Cosmologicon wrote:So... here's a pretty general rant about this sort of thing. Some people criticize the sort of pattern-finding 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 missing-the-whole-point 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 left-hand-side 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 sixteenth-degree polynomial (with ten- or twenty-digit coefficients, of course).

It was pretty hilarious.
you're = you are
their = belonging to them
they're = they are
there = not here

skeptical scientist
closed-minded 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 sixteenth-degree polynomial (with ten- or twenty-digit 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

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 sixteenth-degree polynomial (with ten- or twenty-digit 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
closed-minded 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

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:
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.

And I was just trying to signal that I got the reference, sorry for coming across as a meanie.

Ronfar
Posts: 132
Joined: Mon Dec 04, 2006 6:04 am UTC
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.
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:
That formula looks pretty simple to me. But it gives f(4) = g(0) + g(1) = 1, doesn't it?

Ronfar
Posts: 132
Joined: Mon Dec 04, 2006 6:04 am UTC
Cosmologicon wrote:That formula looks pretty simple to me. But it gives f(4) = g(0) + g(1) = 1, doesn't it?

Whoops! I messed up. I gotta fix that. But my idea was wrong anyway.
- Doug