Computational Complexity

Monday, September 08, 2008

 
Three sequences

Posted by GASARCH

Here are three finite sequences. There is no next element, I give you the complete sequence. What rule did I use to form these sequences?

1. 8,5,4,9,1,7,6,3,2
2. 8,5,1,4,9,2,7,6,3
3. a,i,s,e,t,d,m,c,o,l,p,n,x,v,b,w,y,f,r,u,k,g,z,h,j,q

10:36 AM # 8 comments

1.  Anonymous says:  
   
   Sequence 1 seems to be the the numbers 1-9 in English alphabetical order. It is even listed as such in Sloane's, but I already knew this `riddle' from highschool. (Though in Holland it is 8 3 1 9 2 4 5 6 7, for ``acht drie een negen twee vier vijf zes zeven'')
   Second one doesn't show up in Sloane.
   

   10:48 AM, September 08, 2008

2.  Rani says:  
   
   Only 1 and 2 moved...
   
   8th,5th,1st,4th,9th,2nd,7th,6th,3rd.
   

   2:14 PM, September 08, 2008

3.  Aaron Sterling says:  
   
   Second sequence is ordinals alphabetized, just as first sequence is cardinals alphabetized.
   

   8:24 PM, September 08, 2008

4.  Former VDW undergrad says:  
   
   Third sequence looks vaguely like letter frequencies, although if it is, either the source text is really odd or the language isn't English... possibly Esperanto?
   

   12:18 PM, September 09, 2008

5.  Anonymous says:  
   
   Since these are finite sequences, I can always fit a polynomial and there is nothing more significant than that.
   
   So, no matter what rule you chose to generate them I can interpret that rule as a polynomial function and nothing more.
   

   6:11 PM, September 09, 2008

6.  GASARCH says:  
   
   First sequence is indeed
   the numbers in alph order.
   Second sequence is indeed
   the ordinals in alph order.
   The third sequence is
   sortof freq-- I typed
   a, b, c, ... into google
   and this is the number of
   hits in order.
   
   YES, any finite sequence
   has some poly that generates it. I was looking
   for the ``best explanation''. Not sure
   that can be rigorously defined, perhaps with
   Kolg theory.
   

   10:41 AM, September 10, 2008

7.  Shandor says:  
   
   The 3rd is pretty close to the count of results from Google. It is worth noting that since that's a moving target it doesn't make a great question. Right now, Google is reporting more results for o then c and more for b then v, and I only checked half the letters.
   

   5:28 PM, September 10, 2008

8.  Anonymous says:  
   
   What I'm curious about is this: say you type numbers at random and ask people to "explain" the sequence. What kind of answers would people come up with?
   

   9:03 PM, September 10, 2008

Comment Feeds: This Post All