home *** CD-ROM | disk | FTP | other *** search
/ Sunny 1,000 Collection / SUNNY1000.iso / Files / Dos / Boardak / INETPUZ.ZIP / SERIES.TXT < prev    next >
Text File  |  1995-02-05  |  17KB  |  520 lines
  1. Archive-name: puzzles/archive/series
  2. Last-modified: 17 Aug 1993
  3. Version: 4
  4.  
  5.  
  6. ==> series/series.00.p <==
  7. Are "complete this series" problems well defined?
  8.  
  9. ==> series/series.00.s <==
  10. Since there are infinitely many formulas that will fit any finite
  11. series, many people object that such problems have no good answer.
  12. But isn't this a special case of the general observation that theory
  13. is underdetermined by experience (in other words, that there are a
  14. lot of world views that are consistent with all the facts that we
  15. know)?  And if so, doesn't this objection really apply to all puzzles?
  16. Isn't it just more obvious in the case of series puzzles?
  17.  
  18. As a long-time observer of rec.puzzles nit-picking, I have never seen
  19. a puzzle answer that could not be challenged.  The list of assumptions
  20. made in solving any puzzle is neverending.  Luckily, most of us share
  21. all or nearly all of these assumptions, so that we can agree on an
  22. answer when we see it.
  23.  
  24. All of this has a lot to do with topics such as computational
  25. complexity, algorithmic compressibility, Church's thesis, intelligence
  26. and life.
  27.  
  28.  
  29. ==> series/series.01.p <==
  30. M, N, B, D, P ?
  31.  
  32. ==> series/series.01.s <==
  33. T.  If you say the sounds these letters make out loud, you will see
  34. that the next letter is T.  The letters are in the order of where the
  35. sounds are formed in the mouth, from back to front.
  36.  
  37. ==> series/series.02.p <==
  38. H, H, L, B, B, C, N, O, F ?
  39.  
  40. ==> series/series.02.s <==
  41. Answer 1:  N, N, M, A  The first letters of the symbols for the elements.
  42. Answer 2:  N, S, M, A  The first letters of the names of the elements.
  43.  
  44. ==> series/series.03.p <==
  45. W, A, J, M, M, A, J?
  46.  
  47. ==> series/series.03.s <==
  48. J, V, H, T, P, T, F, P, B, L.  Presidents of the US.
  49.  
  50. ==> series/series.03a.p <==
  51. G, J, T, J, J, J, A, M, W, J, J, Z, M, F, J, ?
  52.  
  53.  
  54. ==> series/series.03a.s <==
  55. G, J, T, J, J, J, A, M, W, J, J, Z, M, F, J, A.  US Presidents' first names.
  56.  
  57. ==> series/series.03b.p <==
  58. A, J, B, C, G, T, C, V, J, T, D, F, K, B, H, ?
  59.  
  60.  
  61. ==> series/series.03b.s <==
  62. A, J, B, C, G, T, C, V, J, T, D, F, K, B, H, J.  US Vice Presidents.
  63.  
  64. ==> series/series.03c.p <==
  65. M, A, M, D, E, L, R, H, ?
  66.  
  67.  
  68. ==> series/series.03c.s <==
  69. M, A, M, D, E, L, R, H, A.  US Presidents' wives' first names.
  70.  
  71. ==> series/series.04.p <==
  72. A, E, H, I, K, L, ?
  73.  
  74. ==> series/series.04.s <==
  75. M, N, O, P, U, W.  Letters in the Hawaiian alphabet.
  76.  
  77. ==> series/series.05.p <==
  78. A B C D E F G H?
  79.  
  80. ==> series/series.05.s <==
  81. M.  The names of the cross-streets travelling west on (say)
  82. Commonwealth Avenue from Boston's Public Garden: Arlington, Berkeley,
  83. Clarendon, Dartmouth, Exeter, Fairfield, Gloucester, Hereford,
  84. Massachusetts Ave.  The alphabet does continue in the Fenway; after
  85. Massachuetts Ave., there is Charlesgate, and then Ipswich, Jersey,
  86. Kilmarnock.
  87.  
  88. ==> series/series.06.p <==
  89. Z, O, T, T, F, F, S, S, E, N?
  90.  
  91. ==> series/series.06.s <==
  92. T.  The name of the integers starting with zero.
  93.  
  94. ==> series/series.06a.p <==
  95. F, S, T, F, F, S, ?
  96.  
  97. ==> series/series.06a.s <==
  98. The words "first", "second", "third", etc.  The same as the previous from this
  99. point on.
  100.  
  101. ==> series/series.07.p <==
  102. 1, 1 1, 2 1, 1 2 1 1, ...
  103.  
  104. What is the pattern and asymptotics of this series?
  105.  
  106. ==> series/series.07.s <==
  107. Each line is derived from the last by the transformation (for example)
  108.  
  109. ... z z z x x y y y ... ->
  110. ... 3 z 2 x 3 y ...
  111.  
  112. John Horton Conway analyzed this in "The Weird and Wonderful Chemistry
  113. of Audioactive Decay" (T M Cover & B Gopinath (eds) OPEN PROBLEMS IN
  114. COMMUNICATION AND COMPUTATION, Springer-Verlag (1987)).  You can also
  115. find his most complete FRACTRAN paper in this collection.
  116.  
  117. First, he points out that under this sequence, you frequently get
  118. adjacent subsequences XY which cannot influence each other in any
  119. future derivation of the sequence rule.  The smallest such are
  120. called "atoms" or "elements".  As Conway claims to have proved,
  121. there are 92 atoms which show up eventually in every sequence, no
  122. matter what the starting value (besides <> and <22>), and always in
  123. the same non-zero limiting proportions.
  124.  
  125. Conway named them after some other list of 92 atoms.  As a puzzle,
  126. see if you can recreate the list from the following, in decreasing
  127. atomic number:
  128.  
  129. U Pa Th Ac Ra Fr Rn Ho.AT Po Bi Pm.PB Tl Hg Au Pt Ir Os Re Ge.Ca.W Ta
  130. HF.Pa.H.Ca.W Lu Yb Tm ER.Ca.Co HO.Pm Dy Tb Ho.GD EU.Ca.Co Sm PM.Ca.Zn
  131. Nd Pr Ce LA.H.Ca.Co Ba Cs Xe I Ho.TE Eu.Ca.SB Pm.SN In Cd Ag Pd Rh
  132. Ho.RU Eu.Ca.TC Mo Nb Er.ZR Y.H.Ca.Tc SR.U Rb Kr Br Se As GE.Na Ho.GA
  133. Eu.Ca.Ac.H.Ca.ZN Cu Ni Zn.CO Fe Mn CR.Si V Ti Sc Ho.Pa.H.CA.Co K Ar
  134. Cl S P Ho.SI Al Mg Pm.NA Ne F O N C B Be Ge.Ca.LI He Hf.Pa.H.Ca.Li
  135.  
  136. Uranium is 3, Protactinium is 13, etc.  Rn => Ho.AT means the following:
  137. Radon forms a string that consists of two atoms, Holmium on the left,
  138. and Astatine on the right.  I capitalize the symbol for At to remind
  139. you that Astatine, and not Holmium, is one less than Radon in atomic
  140. number.  As a check, against you or me making a mistake, Hf is 111xx,
  141. Nd is 111xxx, In and Ni are 111xxxxx, K is 111x, and H is 22.
  142.  
  143. Next see if you can at least prove that any atom other than Hydrogen,
  144. eventually (and always thereafter) forms strings containing all 92 atoms.
  145.  
  146. The grand Conway theorem here is that every string eventually forms (within
  147. a universal time limit) strings containing all the 92 atoms in certain
  148. specific non-zero limiting proportions, and that digits N greater than 3
  149. are eventually restricted to one of two atomic patterns (ie, abc...N and
  150. def...N for some {1,2,3} sequences abc... and def...), which Conway calls
  151. isotopes of Np and Pu.  (For N=2, these are He and Li), and that these
  152. transuranic atoms have a zero limiting proportion.
  153.  
  154. The longest lived exotic element is Methuselum (2233322211N) which takes
  155. about 25 applications to reduce to the periodic table.
  156.  
  157. -Matthew P Wiener (weemba@libra.wistar.upenn.edu)
  158.  
  159. Conway gives many results on the ultimate behavior of strings under
  160. this transformation: for example, taking the sequence derived from 1
  161. (or any other string except 2 2), the limit of the ratio of length of
  162. the (n+1)th term to the length of the nth term as n->infinity is a 
  163. fixed constant, namely
  164.  
  165.             1.30357726903429639125709911215255189073070250465940...
  166.  
  167. This number is from Ilan Vardi, "Computational Recreations in Mathematica",
  168. Addison Wesley 1991, page 13.
  169.  
  170. Another sequence that is related but not nearly as interesting is:
  171.  
  172. 1, 11, 21, 1112, 3112, 211213, 312213, 212223, 114213, 31121314, 41122314,
  173.     31221324, 21322314,
  174.  
  175. and 21322314 generates itself, so we have a cycle.
  176.  
  177. ==> series/series.08a.p <==
  178. G, L, M, B, C, L, M, C, F, S, ?
  179.  
  180. ==> series/series.08a.s <==
  181. US Army officer ranks, descending.
  182.  
  183. ==> series/series.08b.p <==
  184. A, V, R, R, C, C, L, L, L, E, ?
  185.  
  186. ==> series/series.08b.s <==
  187. US Navy officer ranks, descending.
  188.  
  189. ==> series/series.09a.p <==
  190. S, M, S, S, S, C, P, P, P, ?
  191.  
  192. ==> series/series.09a.s <==
  193. Army non-comm ranks, descending.
  194.  
  195. ==> series/series.09b.p <==
  196. M, S, C, P, P, P, S, S, S, ?
  197.  
  198. ==> series/series.09b.s <==
  199. Navy non-comm ranks, descending.
  200.  
  201. ==> series/series.10.p <==
  202. D, P, N, G, C, M, M, S, ?
  203.  
  204. ==> series/series.10.s <==
  205. N, V, N, N, R.  US States in Constitution ratification order.
  206.  
  207. ==> series/series.11.p <==
  208. R O Y G B ?
  209.  
  210. ==> series/series.11.s <==
  211. V or I V.  Colors.
  212.  
  213. ==> series/series.12.p <==
  214. A, T, G, C, L, ?
  215.  
  216. ==> series/series.12.s <==
  217. V, L, S, S, C, A, P.  Zodiacal signs.
  218.  
  219. ==> series/series.13.p <==
  220. M, V, E, M, J, S, ?
  221.  
  222. ==> series/series.13.s <==
  223. U, N, P or U, P, N.  Names of the Planets.
  224.  
  225. ==> series/series.14.p <==
  226. A, B, D, O, P, ?
  227.  
  228. ==> series/series.14.s <==
  229. Q, R.  Only letters with an inside as printed. 
  230.  
  231. ==> series/series.14a.p <==
  232. A, B, D, E, G, O, P, ?
  233.  
  234. ==> series/series.14a.s <==
  235. Q.  Letters with insides in cursive form.
  236.  
  237. ==> series/series.15.p <==
  238. A, E, F, H, I, ?
  239.  
  240. ==> series/series.15.s <==
  241. L, M, N, O, R, S, U, X.  Letters whose English names start with vowels.
  242.  
  243. ==> series/series.16.p <==
  244. A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, X, Y?
  245.  
  246. ==> series/series.16.s <==
  247. Z.  Letters whose English names have one syllable.
  248.  
  249. ==> series/series.17.p <==
  250. T, P, O, F, O, F, N, T, S, F, T, F, E, N, S, N?
  251.  
  252. ==> series/series.17.s <==
  253. T, T, T, E, F, S.  Digits of Pi.
  254.  
  255. ==> series/series.18.p <==
  256. 10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, ___ , 100, 121, 10000
  257.  
  258. ==> series/series.18.s <==
  259.  10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, 31 , 100, 121, 10000
  260.  
  261. Sixteen in base n for n=16, 15, ..., 2.
  262.  
  263. ==> series/series.19.p <==
  264. 0 01 01011 0101101011011 0101101011011010110101101101011011 etc.
  265.  
  266. Each string is formed from the previous string by substituting '01' for '0'
  267. and '011' for '1' simultaneously at each occurance.
  268. Notice that each string is an initial substring of the previous string so
  269. that we may consider them all as initial substrings of an infinite string.
  270. The puzzle then is, given n, determine if the nth digit is 0 or 1 without
  271. having to construct all the previous digits.  That is, give a non-recursive
  272. formula for the nth digit.
  273.  
  274. ==> series/series.19.s <==
  275. Let G equal the limit string generated by the above process and define
  276. the string F by
  277.  
  278. F[0] = "0",
  279. F[n] = "1" if n = floor(phi*m) for some positive integer m,
  280. F[n] = "0" if n = floor(phi^2*m) for some positive integer m,
  281.  
  282. where floor(x) is the greatest integer =< x and phi = (1 + \/5)/2;
  283. I claim that F = G.
  284.  
  285.  
  286. I will try to motivate my solution.  Let g[0]="0" and define g[n+1]
  287. to be the string that results from replacing "0" in g[n] with "01"
  288. and "1" with "011"; furthermore, let s(n) and t(n) be the number of
  289. "0"'s and "1"'s in g[n], respectively.  Note that we have the
  290. following recursive formulas : s(n+1) = s(n) + t(n) and t(n+1) =
  291. s(n) + 2t(n).  I claim that s(n) = Fib(2n-1) and t(n) = Fib(2n),
  292. where Fib(m) is the mth Fibonacci number (defined by Fib(-1) = 1,
  293. Fib(0) = 0, Fib(n+1) = Fib(n) + Fib(n-1) for n>=0); this is easily
  294. established by induction.  Now noting that Fib(2n)/Fib(2n-1) -> phi
  295. as n -> infinity, we see that if the density of the "0"'s and "1"'s
  296. exists, they must be be 1/phi^2 and 1/phi, respectively.  What is
  297. the simplest generating sequence which has this property?  Answer:
  298. the one given above.
  299.  
  300.  
  301. Proof:  We start with
  302.  
  303. Beatty's Theorem: if a and b are positive irrational numbers such
  304. that 1/a + 1/b = 1, then every positive integer has a representation
  305. of the form floor(am) or floor(bm) (m a positive integer), and this
  306. representation is unique.
  307.  
  308. This shows that F is well-defined.  I now claim that
  309.  
  310. Lemma: If S(n) and T(n) (yes, two more functions; apparently today's
  311. the day that functions have their picnic) represent the number of
  312. "0"'s and "1"'s in the initial string of F of length n, then S(n)
  313. = ceil(n/phi^2) and T(n) = floor(n/phi) (ceil(x) is the smallest
  314. integer >= x).
  315.  
  316. Proof of lemma: using the identity phi^2 = phi + 1 we see that S(n)
  317. + T(n) = n, hence for a given n either S(n) = S(n-1) + 1 or T(n) =
  318. T(n-1) + 1.  Now note that if F[n-1]="1" ==> n-1 = floor(phi*m) for
  319. some positive integer m and since phi*m-1 < floor(phi*m) < phi*m ==>
  320. m-1/phi < (n-1)/phi < m ==> T(n) = T(n-1) + 1.   To finish, note that
  321. if F[n-1]="0" ==> n-1 = floor(phi^2*m) for some positive integer m
  322. and since phi^2*m-1 < floor(phi^2*m) < phi^2*m ==> m-1/phi^2 <
  323. (n-1)/phi^2 < m ==> S(n) = S(n-1) + 1.  Q.E.D.
  324.  
  325. I will now show that F is invariant under the operation of replacing
  326. "0" with "01" and "1" with "011"; it will then follow that F=G.
  327. Note that this is equivalent to showing that F[2S(n) + 3T(n)]
  328. = "0", F[2S(n) + 3T(n) + 1] = "1", and that if n = [phi*m] for some
  329. positive integer m, then F[2S(n) + 3T(n) + 2] = "1".  One could
  330. waste hours trying to prove some fiendish identities; watch how
  331. I sidestep this trap.  For the first part, note that by the above
  332. lemma F[2S(n) + 3T(n)] = F[2*ceil(n/phi^2) + 3*floor(n/phi)] =
  333. F[2n + floor(n/phi)] = F[2n + floor(n*phi-n)] = F[floor(phi*n+n)]
  334. = F[floor(phi^2*n)] ==> F[2S(n) + 3T(n)] = "0".  For the second, it
  335. is easy to see that since phi^2>2, if F[m]="0" ==> F[m]="1" hence
  336. the first part implies the second part.  Finally, note that if n =
  337. [phi*m] for some positive integer m, then F[2S(n) + 3T(n) + 3] =
  338. F[2S(n+1) + 3T(n+1)] = "0", hence by the same reasoning as above
  339. F[2S(n) + 3T(n) + 2] = "1".
  340.  
  341. Q.E.D.
  342.  
  343.     -- clong@remus.rutgers.edu (Chris Long)
  344.  
  345. ==> series/series.20.p <==
  346. 1 2 5 16 64 312 1812 12288
  347.  
  348. ==> series/series.20.s <==
  349. ANSWER: 95616
  350.         The sum of factorial(k)*factorial(n-k) for k=0,...,n.
  351.  
  352. ==> series/series.21.p <==
  353. 5, 6, 5, 6, 5, 5, 7, 5, ?
  354.  
  355. ==> series/series.21.s <==
  356. The number of letters in the ordinal numbers.
  357.  
  358. First   5
  359. Second  6
  360. Third   5
  361. Fourth  6
  362. Fifth   5
  363. Sixth   5
  364. Seventh 7
  365. Eighth  6
  366. Ninth   5
  367. etc.
  368.  
  369. ==> series/series.22.p <==
  370. 3 1 1 0 3 7 5 5 2 ?
  371.  
  372. ==> series/series.22.s <==
  373. ANSWER: 4
  374.         The digits of pi expressed in base eight.
  375.  
  376. ==> series/series.23.p <==
  377. 22 22 30 13 13 16 16 28 28 11 ?
  378.  
  379. ==> series/series.23.s <==
  380. ANSWER: 15
  381.         The birthdays of the Presidents of the United States.
  382.  
  383.  
  384. ==> series/series.24.p <==
  385. What is the next letter in the sequence: W, I, T, N, L, I, T?
  386.  
  387. ==> series/series.24.s <==
  388. S.  First letters of words in question.
  389.  
  390. ==> series/series.25.p <==
  391. 1 3 4 9 10 12 13 27 28 30 31 36 37 39 40 ?
  392.  
  393. ==> series/series.25.s <==
  394. 1 3 4 9 10 12 13 27 28 30 31 36 37 39 40 ...
  395. Positive integers in binary, treated as a base 3 number and converted
  396. to decimal.
  397.  
  398. ==> series/series.26.p <==
  399. 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 ?
  400.  
  401. ==> series/series.26.s <==
  402. 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 ...
  403. Positive integers in binary, for each 1 bit (not changed) flip the next bit.
  404. This can also be phrased in reversing sequences of numbers.
  405. More simply, just the integers in reflective-Gray-code order.
  406.  
  407. ==> series/series.27.p <==
  408. 0 1 1 2 1 2 1 3 2 2 1 3 1 2 2 4 1 3 1 3 2 2 1 4 2 ?
  409.  
  410. ==> series/series.27.s <==
  411. 2 3 3 1 3 1 5 2 2 2 4 1 2 2 4 1 3 1 3 3 2 1 5 2 3 2 3 1 4 2 4 2 2 1 ...
  412.  
  413. Number of factors in prime factorization of positive integers.
  414.  
  415. ==> series/series.28.p <==
  416. 0 2 3 4 5 5 7 6 6 7 11 7 13 9 8 8 17 8 19 9 10 13 23 9 10 ?
  417.  
  418. ==> series/series.28.s <==
  419. 15 9 11 29 10 31 10 14 19 12 10 37 21 16 11 41 12 43 15 11 25 47 11 14 12 ...
  420.  
  421. Sum of factors in prime factorization of positive integers.
  422.  
  423. ==> series/series.29.p <==
  424. 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 ?
  425.  
  426. ==> series/series.29.s <==
  427. 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 ...
  428. The number of 1s in the binary expansion of the positive integers.
  429.  
  430. ==> series/series.30.p <==
  431. I I T Y W I M W Y B M A D 
  432.  
  433. ==> series/series.30.s <==
  434. ? (first letters of "If I tell you what it means will you buy me a drink?")
  435.  
  436. ==> series/series.31.p <==
  437. 6 2 5 5 4 5 6 3 7 
  438.  
  439. ==> series/series.31.s <==
  440. 6. The number of segments on a standard calculator display it takes
  441. to represent the digits starting with 0.
  442.   _       _   _       _   _   _   _   _
  443.  | |   |  _|  _| |_| |_  |_    | |_| |_|
  444.  |_|   | |_   _|   |  _| |_|   | |_|  _|
  445.  
  446. ==> series/series.32.p <==
  447. 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1
  448.  
  449. ==> series/series.32.s <==
  450. 0 -> 1   01 -> 10   0110 -> 1001   01101001 ->  10010110
  451. Recursively append the inverse.
  452.  
  453. This sequence is known as the Morse-Thue sequence.  It can be defined
  454. non-recursively as the nth term is the mod 2 count of 1s in n written
  455. in binary:
  456.         0->0 1->1 10->1 11->0 100->1 101->0 110->0 111->1 etc. 
  457.  
  458. Reference:
  459.     Dekking, et. al., "Folds! I,II,III"
  460.     The Mathematical Intelligencer, v4,#3,#4,#4.
  461.  
  462. ==> series/series.33.p <==
  463. 2 12 360 75600
  464.  
  465. ==> series/series.33.s <==
  466. 2         = 2^1
  467. 12        = 2^2 * 3^1
  468. 360       = 2^3 * 3^2 * 5^1
  469. 75600     = 2^4 * 3^3 * 5^2 * 7^1
  470. 174636000 = 2^5 * 3^4 * 5^3 * 7^2 * 11^1
  471.  
  472. ==> series/series.34.p <==
  473. 3 5 4 4 3 5 5 4 3
  474.  
  475. ==> series/series.34.s <==
  476. The number of letters in the English words for the counting numbers.
  477.  
  478. ==> series/series.35.p <==
  479. 1 2 3 2 1 2 3 4 2 1 2 3 4 2 2 3
  480.  
  481. ==> series/series.35.s <==
  482. The number of letters in the Roman numeral representation of the numbers.
  483.  
  484. ==> series/series.36.p <==
  485. ETIANMSURWDKGO
  486.  
  487. ==> series/series.36.s <==
  488. HVF and U with an umlaut.
  489.  
  490. The letters are sorted by their international Morse code representations:
  491.  
  492. E .
  493. T -
  494.  
  495. I ..
  496. A .-
  497. N -.
  498. M --
  499.  
  500. S ...
  501. U ..-
  502. etc.
  503.  
  504.  
  505. ==> series/series.37.p <==
  506. 10^3 10^9 10^27 10^2 0 4 8 3
  507.  
  508.  
  509. ==> series/series.37.s <==
  510. 10^3  = one thousAnd
  511. 10^9  = one Billion
  512. 10^27 = one oCtillion
  513. 10^2  = one hunDreD
  514. 0     = zEro 
  515. 4     = Four
  516. 8     = eiGht
  517. 3     = tHree 
  518. 5     = fIve
  519.  
  520.