## Thursday, October 14, 2010

### How hard is this problem?- I ask this non-rhetorically

I recently saw the following puzzle:

Which two numbers come at the end of this sequence? (That is, what are x and y?)
2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62,64,x,y
(NOTE ADDED LATER- I had a typo in this post, the worst kind of typo one could have- I had a 5 instead of a 6. I looked up the original source and they had the same typo. SORRY!)

I could not figure it out. I went to the sequence-website which gave me the answer. Before the web I would not have been able to do this and I may have had to wait until there was a web to look it up on in order to solve it. Or maybe I could have solved it, though seeing the solution I doubt that.

How hard is this problem? How to tell how hard it is? How well known is this puzzle? YOU can help me!
1. Try to solve it without using any other resources.
2. Leave a comment either saying either I solved it without any help OR I was unable to solve it OR I knew how to solve it since I already saw it.
3. Please do not include the solution. I will not post a solution--- if you are curious just type it into the sequence website.
4. Please do not lie. I want to use this to judge how hard this problem is.

1. Shouldn't the 5 be a six? I was not able to solve it, but I only spend about 20 sec. on it, before looking up the solution.

1. Help me with this sequences. Series 10,12,13,50,46

2. These kind of problems are not hard, they are stupid.You can give a reasonable explanation for all values of x,y.

My favourite example is 1,2,4,8,16,x, where x=31 (A000127 in sloane's encyclopedia) is as good as x=32.

3. I solved it.

I disagree with Anonymous 2: recognising patterns is an important part of being human, even if you can come up with alternative suggestions.

There is something called science: you come up with a hypothesis for the next term and test whether it works. If not, you know you're wrong.

4. Groan. I hate puzzles that lie about their own rules.

5. I don't know but it reminds of another difficult one:

10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, ?, 100, 121, 10000

6. Here is a good one:
125, 116, 110, 103, 96, 86, 79, 72, x, y.

What are x and y?

x = Lincoln Center
y = Columbus Circle

7. I agree with anon 2. Look, there are infinitely many functions which go through these points. What are we trying to do? Are we trying to come up with the function which has the smallest or simplest description and run it to see what are the next points?

What does a pattern mean here? Do you want me to train a numeral network based on so little data? These kind of questions are just not questions, and there is not much fun in trying to guess what another person has in her mind.

ps: Bill, it would be nice if you include a link to this "the sequence website". It seems that Google has a different opinion about what is *the* sequence website.

8. Um, dude? Before the web? There were sequence *books*. They were in lexicographic order and you could find hundreds of sequences.

9. i'm finding harder to find THE sequence website.

10. Agree with Anon 2 -- you can find formulas to justify any number as the solution to x and y. In which case, these kinds of sequence-completion problems should say, "Find the next number in the sequence with the easiest explanation", Which is itself fraught with all kinds of problems. For one thing, if the problem is too "hard", then you're perfectly justified to simply give up and say your favorite number as the next value.

11. "The Sequence Website" is the next blockbuster movie to cash in on the success of "The Social Network". It shows the true origins and motivations behind the web phenomenon that we all use every day. Apparently Neil Sloan is really not happy with John Malkovich's portrayal of him.

13. I couldn't "solve" it (only tried for 10s) OR find "THE sequence website"

OEIS does not recognize this sequence.

14. The sequence website is "The On-Line Encyclopedia of Integer Sequences™". If you haven't seen it before, you are about to waste some time there.

15. Yes, I'm pretty sure the 5 should be a 6.

16. YES- the 5 should be a 6.

MUCH apologies about that- this is the worst typo I have ever made.

17. I couldn't think of it in sixty clock-ticks, so I found it via yahoo. Contrary to anonymous 2, (who said it's "stupid") and 3 ("not much fun"), it was fun for this math guy to find out about.

P.S. This post fits with that run of digits in a particular way... What is it?

18. The pattern was super easy.
I had the next two numbers in less
than a minute.

Then I looked up the solution just to verify and of course I was completely wrong and there's nobody around here to argue with so that's that.

19. I couldn't find it, which did not surprise me when I saw the solution.

In the other had, Euclid would never be able to solve it, therefore...

20. Micki- I would be curious what you
THOUGHT it was- please email me
so as to not give the answer away
may still give things away).

GASARCH

21. I could not solve it and looked for the solution. I do love to solve sequence, but these types of sequence frankly I dont like, where the rule is not "entirely" mathematical. In short I prefer if the terms comes out of some mathematical operations.

22. x = sqrt{2} i, y is the tuple (matrix,graph): ((0,1),(12,3i)), K_15

Sorry, but this is one of my favorite sequences. I couldn't help posting the answer!

23. any finite prefix of an infinite sequence is irrelevant so x and y can be anything

24. Recognizing patterns is one thing, but saying that one of them is right and others wrong seems absolutely inappropriate.

25. For an analytic solution: http://www.wolframalpha.com/input/?i=2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62

26. Re Anonymous #6:

I liked your puzzle, but I think it's a bit wrong. It could easily continue 66 and then 59. If you take every station that has a "name", then 116 would be "Columbia University". If you take every station where the name is more prominent than the street number, then 110 would be "Cathedral Parkway" and every other station would be the number.

There's surely a good, valid sequence along these (subway) lines.

27. These sequence puzzles are about Kolmogorov complexities, i.e. what would x & y have to be so that the whole string is compressible.

(Of course there's an additive constant depending on the chosen TM, and when you require knowledge of radiology or street numbers in Manhattan, people do get mad.)

I also hate these puzzles.

28. x%2=0,030(base 8).

I think it's just as good an answer as the official one.

29. Think the comments mistook the symbols for tags. In text:

x%2=0, x between (0,7) or greater than 20 (in base 8)

30. Glad to see my eban number sequence getting some press. This is A006933 in the OEIS, and the best URL is http://oeis.org/classic/
Neil Sloane

31. Thought about it for 10 minutes and generate lots of wrong ideas that weren't even close. Looked it up. Never would've thought of that; brain was in a different zone.

32. I've seen similar things before, and was on the right track, but got annoyed and gave up before I actually solved it because I don't like word problems.

33. Shouldn't math transcend the limitations of the English language (or any other arbitrary language?)

34. As a non-native English speaker this was impossible to have guessed. I spent about 10 minutes on it before falling to my knees.

35. I got x, but was very wrong with y. Looking at the answer, I was no where on the right track.

However, I spent the most time on trying to find the so-called Sequence site.

36. I couldn't solve it, but after looking at the solution I think it's a fair and interesting problem.

37. 66, 70

without looking anything up.
I'm seeing the first group as 0,2 4 6, then jumps to 30, 32, 34,36, but then goes 40... 50...60... so i'm not sure for the jump from 0x to 3x
so now that I post this i'll look at comments

38. My experience was similar to other posters: I had a guess that worked in about 30 seconds, but it was not the 'correct' one.

I don't think I ever would have come to the 'correct' answer. I automatically assume the pattern sought in an integer sequence is based on the numbers' numerical properties. As such I would wager the 'problem' is impossible.

Personally, I abhor these kind of 'math' riddles. They are about as clever as Joy Buzzers.

2,3,10,12,13,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,200,201,202...

7,13,14,15,16,18,19,20,30,40,50...

11,17,21,22,23,24,25,26,28,29,31,32,33,34,35,36,38,39,41...

1,2,4,5,8,40,1000,1001,1002,1004...

39. Solved it without any help.

40. I am a non-native speaker and I could solve it immediately - although I have seen similar puzzles.

41. I could not figure out it out.

42. I could only solve it the way wolfram alpha did (without looking it up there).

43. wait so why shouldn't we invest into china and why should be avoid itcs tsinghua for postdocs again ?

coz it violates every definition of human rights ?
coz ppl there are hippo-crits

44. My name is Vinay and I could istantly solve it. Trust me, I work for HP! I am a honourable, trustworthy man.

45. Are these all numbers that don't have an "e" in English spelling?

46. I was unable to solve it.

47. I was unable to solve it.
I know an interesting anecdote related to the problem. Warning:
It contains MAJOR SPOILERS about the problem. I posted it as a comment here:

http://blog.computationalcomplexity.org/2002/08/complexity-class-of-week-s2p.html

48. I solved it without any help

49. Could not figure it out in five minutes ... was annoyed when I looked up the "algorithm" ... (because it was unlikely to be of further utility in the enterprises that I care about).

On the other hand, certainly there are some mathematical jobs where this problem (or a similar one) might legitimately be posed on a job interview or aptitude test.

Within the context of such an aptitude examination, pretty much any mathematician's chances of solving this particular problem would be enhanced ...

... and so perhaps this is one of the (many) mathematical questions regarding which a diversity of opinion is to be expected and welcomed.

50. Laslo Lovasz wins the Kyoto prize!

51. I couldn't solve it.
Never seen this type of puzzle! Was on a completely wrong track!

52. 66,70.

look at the last digts always. 0 2 4 6
the first digits increase from one to one.

60,62,64,66,70

if this is really the answer, I saw it in 10 sec :)

53. "if this is really the answer, I saw it in 10 sec :)"

54. I have a general question.

Why does the overall quality of a blog decline as time progresses ? I mean, look at this block, some of the comments are funny while others are clearly meant to instigate chaos in my home country china. WE CHINESE DO NOT ALLOW FOREIGNERS TO INTERVENE IN OUR INTERNAL AFFAIRS, DONT U UNDERSTAND ? IT IS OUR COUNTRY AND FOREIGNERS DONT UNDERSTAND US.

I mean how could they understand tian-an-men square incident where we gave orders to wheel tanks over our very own children and then are ashamed to admit such an incidence thus eradicate any documents pertaining to that event. How could foreigners understand this ? They don't. Tiananmen Square never happened. Taiwan is part of mainland china and the U.S. can't do anything about it. We will lurke the Taiwanese into mainland china. We have our own devilous tactics.

And Tibet will always be suppressed by china, coz we are the stronger nation. We will never grant them any human rights. It's own triple T secret society.

55. bravo, to moderation! now we will have to wait decades for comments to appear.

moderation hampers the natural flow of evolution.

56. moderation is not free market oriented i am unsure whether this will be as good as it is believed to be.

57. lance and bill are a mathematician so obviously he knows what he id doing when he moderates aka they are objective either way.

but please bill, can you block more or tell us whether you are busy nowadays. what's going on ? and lance has promised us updates on his book progresss .... wat's going on there ?

58. x=1/3
y=pi

What do you mean it's not an 18th-degree polynomial?

59. My great Niece guessed 2000 (the correct next value) and 2002 (the correct next
value after that).

How did she do that?

I do not know.

GASARCH

60. I guessed right, but after considerable trial and error. I tried virtually everything I could think of before I started writing the numbers out in English..I am not entirely sure what is the use of this I am also not sure how this problem could be classified as hard/easy? This problem may be extraordinarily hard
(if we are only looking at eban) for someone who is not familiar with English.

61. I cant solve it.

62. One of my bright High School Students
got it right with the hint
`This puzzle is really stupid.''

ANYWAY, based on all of your responses
I think we conclude that this is a hard puzzle. Whether or not it is a stupid one is a matter of opinion.

63. When I first saw this puzzle, my mathematical mind was stumped -- I couldn't even think of a hypothesis to try. Two hours later, I happened to think of it again, and the right idea popped into my head. Sometimes it helps to take a break.

Some people would call this an exercise in creative thinking. In my case, I think it was more a function of what kinds of similar puzzles I had been exposed to in the past.

64. I think the difficulty of this problem is to some degree a question of learning theory (and then a question of human communication). The problem is one of finding a hypothesis that describes the examples that we're presented with and generalizes to unseen examples. As we all know, if the complexity of the hypothesis space is virtually unbounded, the problem is virtually impossible.

Here the problem can be posed in a natural and simple hypothesis space. After all there is a very small FSA that decides membership in the sequence, were the sequence written out in English. The difficulty comes from subtly suggesting the wrong hypothesis space. The problem is posed in a mathematical language and in a mathematical context, which suggests the usual hypothesis space for these sequence problems: simple algebraic functions. Even extensions of this space however will lead you nowhere - any valid description is ridiculously complicated. Were the problem posed as a membership question in a sequence of strings, then we would have the right hint as to what kind of pattern we're looking for.

So in a few words, the difficulty comes from posing the question in one language (by writing out the sequence in digits) even though the simplest correct hypothesis works on a "translation" (and an entirely human one) into another language.

65. tabish- that is not the answers the maker of the problem had in mind. The sequence is the list of all numbers that, when written in English, do not have the number e in them.