Official xkcd puzzle, free shirts for solutions
Moderators: jestingrabbit, Moderators General, Prelates
Official xkcd puzzle, free shirts for solutions
N, F(N) in binary, F(N) in decimal
0 000000 0
1 000001 1
2 000011 3
3 000010 2
4 001000 8
5 001010 10
6 001011 11
7 001001 9
8 001100 12
9 001110 14
10 001111 15
11 001101 13
12 000111 7
13 000110 6
14 000100 4
15 000101 5
16 010000 16
17 010010 18
18 010011 19
19 010001 17
20 010100 20
21 010101 21
22 010111 23
23 010110 22
24 011100 28
25 011101 29
26 011111 31
27 011110 30
28 011011 27
29 011001 25
30 011000 24
31 011010 26
32 110000 48
33 110010 50
34 110111 51 (not 55)
35 110101 49 (not 53)
. . .
71 10000110 134
edit: Crap. The last two numbers were indeed wrong. Thanks for catching that, all, and sorry if you were led down the wrong track. I'm not sure how it happened  I did this on paper/in notepad, but I did the same thing everywhere. Must've hit a key wrong somewhere :/
Come up with an algorithm to generate the Nth number in this sequence. Post the algorithm, along with the next 10 numbers and the 31337th number why not. If multiple algorithms are posted that work, the one that is the most elegant wins.
The free xkcd shirts will be given out for the first and the best solution. They will depend on me having shirts you want in stock, so they may be slightly delayed what with the holidays. (This is a pretty informal thing. We're all friends here?)
Feel free to pass this around. I'd really like to see a simple, iterative solution.
(Technical note  the function is a bijection. That is, every positive integer N has one F(N) and every integer is evenutally generated by this function  it's a complete onetoone mapping.)
0 000000 0
1 000001 1
2 000011 3
3 000010 2
4 001000 8
5 001010 10
6 001011 11
7 001001 9
8 001100 12
9 001110 14
10 001111 15
11 001101 13
12 000111 7
13 000110 6
14 000100 4
15 000101 5
16 010000 16
17 010010 18
18 010011 19
19 010001 17
20 010100 20
21 010101 21
22 010111 23
23 010110 22
24 011100 28
25 011101 29
26 011111 31
27 011110 30
28 011011 27
29 011001 25
30 011000 24
31 011010 26
32 110000 48
33 110010 50
34 110111 51 (not 55)
35 110101 49 (not 53)
. . .
71 10000110 134
edit: Crap. The last two numbers were indeed wrong. Thanks for catching that, all, and sorry if you were led down the wrong track. I'm not sure how it happened  I did this on paper/in notepad, but I did the same thing everywhere. Must've hit a key wrong somewhere :/
Come up with an algorithm to generate the Nth number in this sequence. Post the algorithm, along with the next 10 numbers and the 31337th number why not. If multiple algorithms are posted that work, the one that is the most elegant wins.
The free xkcd shirts will be given out for the first and the best solution. They will depend on me having shirts you want in stock, so they may be slightly delayed what with the holidays. (This is a pretty informal thing. We're all friends here?)
Feel free to pass this around. I'd really like to see a simple, iterative solution.
(Technical note  the function is a bijection. That is, every positive integer N has one F(N) and every integer is evenutally generated by this function  it's a complete onetoone mapping.)
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Official xkcd puzzle, free shirts for solutions
xkcd wrote:(Technical note  the function is a bijection. That is, every positive integer N has one F(N) and every integer is evenutally generated by this function  it's a complete onetoone mapping.)
Sounds like you've described it to be a surjection, not a bijection. For any function f, for any x in the domain of f, there is only one value of f(x)  that's what makes it a function. The fact that every integer is generated by F makes F surjective. If F is also injective  every F(N) has one N  then it's bijective.
 Toeofdoom
 The (Male) Skeleton Guitarist
 Posts: 3446
 Joined: Wed Jan 10, 2007 10:06 am UTC
 Location: Melbourne, Australia
 Contact:
So, the idea is we basically make a function F(N) that fits all the criteria and what, uses one general rule? not some thing where it treats different values of N differently?
Also im wondering why theres binary :p hmmm...
K... looking at a bit of a pattern here... or multiple patterns. still dont get it though.
EDIT: k, i think me and my brother have got F(40) and F(42)... (mainly my work of course ... )
and we will continue to poke this puzzle alot.
Do you actually have an answer to this btw? I mean it would be cool if we could atleast check those 2 answers... heh
Also im wondering why theres binary :p hmmm...
K... looking at a bit of a pattern here... or multiple patterns. still dont get it though.
EDIT: k, i think me and my brother have got F(40) and F(42)... (mainly my work of course ... )
and we will continue to poke this puzzle alot.
Do you actually have an answer to this btw? I mean it would be cool if we could atleast check those 2 answers... heh
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5950
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Official xkcd puzzle, free shirts for solutions
Erasmus wrote:xkcd wrote:(Technical note  the function is a bijection. That is, every positive integer N has one F(N) and every integer is evenutally generated by this function  it's a complete onetoone mapping.)
Sounds like you've described it to be a surjection, not a bijection. For any function f, for any x in the domain of f, there is only one value of f(x)  that's what makes it a function. The fact that every integer is generated by F makes F surjective. If F is also injective  every F(N) has one N  then it's bijective.
It sounds like a bijection to me, especially given the use of the word 'one'.
Re: Official xkcd puzzle, free shirts for solutions
jestingrabbit wrote:It sounds like a bijection to me, especially given the use of the word 'one'.
Consider f(x) = x^2. For every x, there is exactly one f(x); but f is not a bijection.
This isn't just pedantic (even though it is mostly pedantic). Certainly the function is injective in the places it's defined for us, so perhaps it's safe to assume that it's injective on its entire domain... but perhaps not?
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Official xkcd puzzle, free shirts for solutions
xkcd wrote:34 110111 51 (not 55)
35 110101 49 (not 53)
I just wanted to check that when you made the correction, you just forgot to change the binary  the discrepancy isn't part of the problem, is it?
Who has been making grilled cheese sandwiches with the defibrillator paddles?
Delores Herbig
Delores Herbig

 Posts: 2
 Joined: Fri Oct 05, 2007 7:17 am UTC
Re: Official xkcd puzzle, free shirts for solutions
beard0 wrote:xkcd wrote:34 110111 51 (not 55)
35 110101 49 (not 53)
I just wanted to check that when you made the correction, you just forgot to change the binary  the discrepancy isn't part of the problem, is it?
No, he just made a mistake. The binary should be 110011 and 110001 otherwise the sequence makes no sense.
Toeofdoom wrote:EDIT: k, i think me and my brother have got F(40) and F(42)... (mainly my work of course ... )
I believe I found an actual function for evaluating the sequence, and I found that F(40) = 60 and F(42) = 63
 Yakk
 Poster with most posts but no title.
 Posts: 10896
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Official xkcd puzzle, free shirts for solutions
Spoiler:
Now I have no idea if this is what you where aiming for, but heck, it matches the displayed stuff, and is pretty simple to implement.
It also lines up with kmill's claims about 40 and 42. Interesting.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Official xkcd puzzle, free shirts for solutions
so was there found a more elegant solution? is it still open?
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5950
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Official xkcd puzzle, free shirts for solutions
Its closed. The solution was pretty ugly.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Official xkcd puzzle, free shirts for solutions
There's a solution thread. I don't know if anybody won per se.... I got a shirt out of it, but I don't know how many other people did.
Who is online
Users browsing this forum: No registered users and 4 guests