Official xkcd puzzle, free shirts for solutions

[xkcd]

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

[java]

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

[Token]

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

[Cosmologicon]

"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?

[BaldAdonis]

So..... who won?

[Erasmus]

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

[Toeofdoom]

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

[jestingrabbit]

(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'.

[Erasmus]

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]

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

[beard0]

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?

[kmill31415]

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.

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]

Spoiler:

Code: Select all

0:   00 00 00:   00 00 00:   0:   B A B A
1:   00 00 01:   00 00 01:   1:   B A B A
2:   00 00 10:   00 00 11:   3:   B A B A
3:   00 00 11:   00 00 10:   2:   B A B A

4:   00 01 00:   00 10 00:   8:   B A B A
5:   00 01 01:   00 10 10:   10:   B A B A
6:   00 01 10:   00 10 11:   11:   B A B A
7:   00 01 11:   00 10 01:   9:   B A B A

8:   00 10 00:   00 11 00:   12:   B A B A
9:   00 10 01:   00 11 10:   14:   B A B A
10:   00 10 10:   00 11 11:   15:   B A B A
11:   00 10 11:   00 11 01:   13:   B A B A

12:   00 11 00:   00 01 11:   7:   B A B C
13:   00 11 01:   00 01 10:   6:   B A B C
14:   00 11 10:   00 01 00:   4:   B A B C
15:   00 11 11:   00 01 01:   5:   B A B C

16:   01 00 00:   01 00 00:   16:   B A A A
17:   01 00 01:   01 00 10:   18:   B A A A
18:   01 00 10:   01 00 11:   19:   B A A A
19:   01 00 11:   01 00 01:   17:   B A A A

20:   01 01 00:   01 01 00:   20:   B A A A
21:   01 01 01:   01 01 01:   21:   B A A A
22:   01 01 10:   01 01 11:   23:   B A A A
23:   01 01 11:   01 01 10:   22:   B A A A

24:   01 10 00:   01 11 00:   28:   B A A A
25:   01 10 01:   01 11 01:   29:   B A A A
26:   01 10 10:   01 11 11:   31:   B A A A
27:   01 10 11:   01 11 10:   30:   B A A A

28:   01 11 00:   01 10 11:   27:   B A A C
29:   01 11 01:   01 10 01:   25:   B A A C
30:   01 11 10:   01 10 00:   24:   B A A C
31:   01 11 11:   01 10 10:   26:   B A A C

32:   10 00 00:   11 00 00:   48:   B A A A
33:   10 00 01:   11 00 10:   50:   B A A A
34:   10 00 10:   11 00 11:   51:   B A A A
35:   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:   52
37:   10 01 01:   11 01 01:   53
38:   10 01 10:   11 01 11:   55
39:   10 01 11:   11 01 10:   54
40:   10 10 00:   11 11 00:   60
41:   10 10 01:   11 11 01:   61
42:   10 10 10:   11 11 11:   63
43:   10 10 11:   11 11 10:   62
44:   10 11 00:   11 10 00:   56
45:   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.

[charonme]

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

[jestingrabbit]

Its closed. The solution was pretty ugly.

[Cosmologicon]

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.