## Official xkcd puzzle, free shirts for solutions

A forum for good logic/math puzzles.

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 one-to-one mapping.)

xkcd
Site Ninja

Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC

Hm... no offense, but I wouldn't use the words one-to-one mapping, since doesn't that imply only an injection? Or am I mixing my terms up again?

-java
java

Posts: 33
Joined: Wed Aug 30, 2006 4:57 pm UTC

"One-to-one" and "one-one" generally mean injective and bijective, but which is which depends entirely upon to whom you are talking, and it makes much more sense to use neither term but to explicitly state whether you mean injective or bijective.
Token

Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

"One-to-one function" does mean only injection, yes, but "complete one-to-one function" must mean bijection, right? Although I guess the normal term is "onto", what else can "complete" mean?

Cosmologicon

Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

So..... who won?

Posts: 81
Joined: Fri Nov 24, 2006 11:32 pm UTC

### 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 one-to-one 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.
Erasmus

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

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

Toeofdoom
The (Male) Skeleton Guitarist

Posts: 3444
Joined: Wed Jan 10, 2007 10:06 am UTC
Location: Melbourne, Australia

### 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 one-to-one 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'.

jestingrabbit

Posts: 5185
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### 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?
Erasmus

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

Well considering xkcd explicitly said it was injective (one-to-one), I'd say it's safe to assume it's injective.

Cosmologicon

Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

### 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

beard0

Posts: 21
Joined: Wed Jan 17, 2007 5:17 am UTC
Location: Ottawa

### 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
kmill31415

Posts: 2
Joined: Fri Oct 05, 2007 7:17 am UTC

### Re: Official xkcd puzzle, free shirts for solutions

Spoiler:
Code: Select all
`0:   00 00 00:   00 00 00:   0:   B A B A1:   00 00 01:   00 00 01:   1:   B A B A2:   00 00 10:   00 00 11:   3:   B A B A3:   00 00 11:   00 00 10:   2:   B A B A4:   00 01 00:   00 10 00:   8:   B A B A5:   00 01 01:   00 10 10:   10:   B A B A6:   00 01 10:   00 10 11:   11:   B A B A7:   00 01 11:   00 10 01:   9:   B A B A8:   00 10 00:   00 11 00:   12:   B A B A9:   00 10 01:   00 11 10:   14:   B A B A10:   00 10 10:   00 11 11:   15:   B A B A11:   00 10 11:   00 11 01:   13:   B A B A12:   00 11 00:   00 01 11:   7:   B A B C13:   00 11 01:   00 01 10:   6:   B A B C14:   00 11 10:   00 01 00:   4:   B A B C15:   00 11 11:   00 01 01:   5:   B A B C16:   01 00 00:   01 00 00:   16:   B A A A17:   01 00 01:   01 00 10:   18:   B A A A18:   01 00 10:   01 00 11:   19:   B A A A19:   01 00 11:   01 00 01:   17:   B A A A20:   01 01 00:   01 01 00:   20:   B A A A21:   01 01 01:   01 01 01:   21:   B A A A22:   01 01 10:   01 01 11:   23:   B A A A23:   01 01 11:   01 01 10:   22:   B A A A24:   01 10 00:   01 11 00:   28:   B A A A25:   01 10 01:   01 11 01:   29:   B A A A26:   01 10 10:   01 11 11:   31:   B A A A27:   01 10 11:   01 11 10:   30:   B A A A28:   01 11 00:   01 10 11:   27:   B A A C29:   01 11 01:   01 10 01:   25:   B A A C30:   01 11 10:   01 10 00:   24:   B A A C31:   01 11 11:   01 10 10:   26:   B A A C32:   10 00 00:   11 00 00:   48:   B A A A33:   10 00 01:   11 00 10:   50:   B A A A34:   10 00 10:   11 00 11:   51:   B A A A35:   10 00 11:   11 00 01:   49:   B A A A...71:   01 00 01 11:   10 00 01 10:   134:   B A A A`

Binary maps:
MapA:
00 -> 00
01 -> 01
10 -> 11
11 -> 10

MapB:
00 -> 00
01 -> 10
10 -> 11
11 -> 01

MapC:
00 -> 11
01 -> 10
10 -> 00
11 -> 10

Step 1: Convert to base 4. Each digit is a 4^N digit.

Step 2: Pick a map for each digit.
For each 4^N digit:
If N == 0 and the 4^1 digit is 3, use map C.
If there is a 4^{N+1} digit, use map A.
If there isn't a 4^{N+1} digit and N is odd, use map B.
Otherwise, use map A.

Step 3:
Run each map on each digit.

Using the above algorithm, the values of 36 .. 45 are thus:
Code: Select all
`36:   10 01 00:   11 01 00:   5237:   10 01 01:   11 01 01:   5338:   10 01 10:   11 01 11:   5539:   10 01 11:   11 01 10:   5440:   10 10 00:   11 11 00:   6041:   10 10 01:   11 11 01:   6142:   10 10 10:   11 11 11:   6343:   10 10 11:   11 11 10:   6244:   10 11 00:   11 10 00:   5645:   10 11 01:   11 10 10:   58`

And the value of 31337 is:
Code: Select all
`31337:   01 11 10 10 01 10 10 01:   01 10 11 11 01 11 11 01:   28541`

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.

Yakk

Posts: 10038
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Official xkcd puzzle, free shirts for solutions

so was there found a more elegant solution? is it still open?
charonme

Posts: 137
Joined: Sun May 18, 2008 11:18 am UTC

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

jestingrabbit

Posts: 5185
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

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

Cosmologicon

Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA