home *** CD-ROM | disk | FTP | other *** search
/ Sunny 1,000 Collection / SUNNY1000.iso / Files / Dos / Boardak / INETPUZ.ZIP / ARITHMET.TXT < prev    next >
Text File  |  1995-02-05  |  91KB  |  2,437 lines

  1. Archive-name: puzzles/archive/arithmetic/part1
  2. Last-modified: 17 Aug 1993
  3. Version: 4
  4.  
  5.  
  6. ==> arithmetic/7-11.p <==
  7. A customer at a 7-11 store selected four items to buy, and was told
  8. that the cost was $7.11.  He was curious that the cost was the same
  9. as the store name, so he inquired as to how the figure was derived.
  10. The clerk said that he had simply multiplied the prices of the four
  11. individual  items.  The customer  protested  that  the four  prices     
  12. should have been ADDED,  not MULTIPLIED.  The  clerk said that that
  13. was OK with him, but, the result was still the same: exactly $7.11.
  14.  
  15. What were the prices of the four items?
  16.  
  17. ==> arithmetic/7-11.s <==
  18. The prices are: $1.20, $1.25, $1.50, and $3.16
  19.  
  20. $7.11 is not the only number which works.  Here are the first 160 such
  21. numbers, preceded by a count of distinct solutions for that price.
  22. Note that $7.11 has a single, unique solution.
  23.  
  24.        1 -  $6.44      1 -  $7.83      2 -  $9.20      3 - $10.89 
  25.        1 -  $6.51      1 -  $7.86      1 -  $9.23      1 - $10.95 
  26.        1 -  $6.60      3 -  $7.92      1 -  $9.24      2 - $11.00 
  27.        1 -  $6.63      1 -  $8.00      1 -  $9.27      1 - $11.07 
  28.        1 -  $6.65      1 -  $8.01      2 -  $9.35      1 - $11.13 
  29.        1 -  $6.72      1 -  $8.03      3 -  $9.36      1 - $11.16 
  30.        2 -  $6.75      5 -  $8.10      1 -  $9.38      1 - $11.22 
  31.        1 -  $6.78      1 -  $8.12      5 -  $9.45      2 - $11.25 
  32.        1 -  $6.80      1 -  $8.16      2 -  $9.48      2 - $11.27 
  33.        2 -  $6.84      2 -  $8.19      1 -  $9.54      1 - $11.30 
  34.        1 -  $6.86      1 -  $8.22      1 -  $9.57      1 - $11.36 
  35.        1 -  $6.89      1 -  $8.25      1 -  $9.59      1 - $11.40 
  36.        2 -  $6.93      3 -  $8.28      2 -  $9.60      2 - $11.43 
  37.        1 -  $7.02      3 -  $8.33      1 -  $9.62      2 - $11.52 
  38.        1 -  $7.05      1 -  $8.36      2 -  $9.63      2 - $11.55 
  39.        2 -  $7.07      1 -  $8.37      1 -  $9.66      2 - $11.61 
  40.        1 -  $7.08      2 -  $8.40      1 -  $9.68      1 - $11.69 
  41.        1 -  $7.11      1 -  $8.45      2 -  $9.69      1 - $11.70 
  42.        1 -  $7.13      2 -  $8.46      1 -  $9.78      1 - $11.88 
  43.        2 -  $7.14      1 -  $8.52      2 -  $9.80      1 - $11.90 
  44.        3 -  $7.20      5 -  $8.55      1 -  $9.81      1 - $11.99 
  45.        1 -  $7.25      1 -  $8.60      1 -  $9.87      1 - $12.06 
  46.        1 -  $7.26      4 -  $8.64      4 -  $9.90      1 - $12.15 
  47.        2 -  $7.28      1 -  $8.67      1 -  $9.92      1 - $12.18 
  48.        1 -  $7.29      1 -  $8.69      2 -  $9.99      1 - $12.24 
  49.        3 -  $7.35      1 -  $8.73      1 - $10.01      1 - $12.30 
  50.        1 -  $7.37      2 -  $8.75      1 - $10.05      1 - $12.32 
  51.        1 -  $7.47      1 -  $8.76      2 - $10.08      1 - $12.35 
  52.        1 -  $7.50      1 -  $8.78      1 - $10.17      2 - $12.42 
  53.        1 -  $7.52      5 -  $8.82      1 - $10.20      1 - $12.51 
  54.        4 -  $7.56      1 -  $8.85      2 - $10.26      1 - $12.65 
  55.        1 -  $7.62      1 -  $8.88      3 - $10.29      2 - $12.69 
  56.        4 -  $7.65      2 -  $8.91      3 - $10.35      1 - $12.75 
  57.        1 -  $7.67      1 -  $8.94      2 - $10.44      1 - $12.92 
  58.        2 -  $7.70      1 -  $8.96      1 - $10.53      1 - $12.96 
  59.        3 -  $7.74      3 -  $9.00      1 - $10.56      1 - $13.23 
  60.        1 -  $7.77      1 -  $9.02      1 - $10.64      1 - $13.41 
  61.        1 -  $7.79      2 -  $9.03      2 - $10.71      1 - $13.56 
  62.        2 -  $7.80      1 -  $9.12      3 - $10.80      1 - $14.49 
  63.        1 -  $7.82      2 -  $9.18      1 - $10.85      1 - $15.18 
  64.  
  65.  
  66. There are plenty of solutions for five summands.  Here are a few:
  67.  
  68.          $8.28  -- at least two solutions
  69.          $8.47  -- at least two solutions
  70.          $8.82  -- at least two solutions
  71. --
  72.      Mark Johnson       mark@microunity.com       (408) 734-8100
  73.  
  74. There may be many approximate solutions, for example: $1.01, $1.15, $2.41,
  75. and $2.54.  These sum to $7.11 but the product is 7.1100061.
  76.  
  77. ==> arithmetic/arithmetic.progression.p <==
  78. Is there an arithmetic progression of 20 or more primes?
  79.  
  80. ==> arithmetic/arithmetic.progression.s <==
  81. There is an arithmetic progression of 21 primes:
  82.     142072321123 + 1419763024680 i, 0 <= i < 21.
  83.  
  84. It was discovered on 30 November 1990, by programs running in the background
  85. on a network of Sun 3 workstations in the Department of Computer Science,
  86. University of Queensland, Australia.
  87.  
  88. See: Andrew Moran and Paul Pritchard, The design of a background job
  89. on a local area network, Procs. 14th Australian Computer Science Conference,
  90. 1991, to appear.
  91.  
  92. ==> arithmetic/clock/day.of.week.p <==
  93. It's restful sitting in Tom's cosy den, talking quietly and sipping
  94. a glass of his Madeira.
  95.  
  96. I was there one Sunday and we had the usual business of his clock.
  97. When the radio gave the time at the hour, the Ormolu antique was 
  98. exactly 3 minutes slow.
  99.  
  100. "It loses 7 minutes every hour", my old friend told me, as he had done
  101. so many times before.  "No more and no less, but I've gotten used to
  102. it that way."
  103.  
  104. When I spent a second evening with him later that same month, I remarked
  105. on the fact that the clock was dead right by radio time at the hour.
  106. It was rather late in the evening, but Tom assured me that his treasure
  107. had not been adjusted nor fixed since my last visit.
  108.  
  109. What day of the week was the second visit?
  110.  
  111. From "Mathematical Diversions" by Hunter + Madachy
  112.  
  113. ==> arithmetic/clock/day.of.week.s <==
  114. The answer is 17 days and 3 hours later, which would have been a Wednesday.
  115. This is the only other time in the same month when the two would agree at all.
  116.  
  117. In 17 days the slow clock loses 17*24*7 minutes = 2856 minutes,
  118. or 47 hours and 36 minutes.  In 3 hours more it loses 21 minutes, so
  119. it has lost a total of 47 hours and 57 minutes.  Modulo 12 hours, it
  120. has *gained* 3 minutes so as to make up the 3 minutes it was slow on
  121. Sunday.  It is now (fortnight plus 3 days) exactly accurate.
  122.  
  123. Since the clock was not adjusted since the last visit, it's also
  124. possible that the radio time shifted by one hour due to a change to or
  125. from summer daylight saving time.  However, it turns out that the only
  126. additional possibilities that need to be considered are those of 4 days
  127. 15 hours later, when the clock would have lost 12 hours 57 minutes, and
  128. 29 days 15 hours later, when the clock would have lost 3 days 10 hours
  129. 57 minutes.  Without even considering the rules for when in the month the
  130. clock is changed, these possible solutions are ruled out because we know
  131. that both visits were in the evening ("I spent a second evening with him").
  132. and they involve times in a different part of the day.
  133.  
  134.  
  135. ==> arithmetic/clock/palindromic.p <==
  136. How many times per day does a digital clock display a palindromic number?
  137.  
  138.  
  139. ==> arithmetic/clock/palindromic.s <==
  140. The problem is underspecified.  Digital clocks may run from
  141.  
  142.         (a) 1:00 to 12:59
  143.         (b) 01:00 to 12:59
  144.         (c) 0:00 to 23:59
  145.         (d) 00:00 to 23:59
  146.         (e-h) any of the above with seconds appended, :00 to :59.
  147.  
  148. I agree that not all of these are common, but I have seen some uncommon
  149. ones.  For that matter, I've seen ones not on the above list -- the Toronto
  150. subway stations used to contain digital clocks that ran from 0:00 to 12:59
  151. (pm), then from 1:00 (pm) to 11:59 (pm), while a computer that I used to
  152. use had the inverse anomaly -- its time of day command displayed times
  153. from 12:00:00 to 12:59:59 (am), then 01:00:00 to 23:59:59!
  154.  
  155. I get the following results for the 8 cases.
  156.  
  157.         CASE    AM+PM   HOURS pals/hr  TOTAL    OVERALL TOTAL
  158.         (a)     yes     1-9      6       54
  159.                         10-12    1        3     114
  160.   
  161.         (b)     yes     01-05    1        5
  162.                         06-09    0        0
  163.                         10-12    1        3     16
  164.  
  165.         (c)     no      0-9      6       60
  166.                         10-15    1        6
  167.                         16-19    0        0
  168.                         20-23    1        4     70
  169.  
  170.         (d)     no      00-05    1        6
  171.                         06-09    0        0
  172.                         10-15    1        6
  173.                         16-19    0        0
  174.                         20-23    1        4     16
  175.  
  176.         (e)     yes     1-9     60      540
  177.                         10-12    6       18     1116
  178.  
  179.         (f)     yes     01-05    6       30
  180.                         06-09    0        0
  181.                         10-12    6       18     96
  182.  
  183.         (g)     no      0-9     60      600
  184.                         10-15    6       36
  185.                         16-19    0        0
  186.                         20-23    6       24     660
  187.  
  188.         (h)     no      00-05    6       36
  189.                         06-09    0        0
  190.                         10-15    6       36
  191.                         16-19    0        0
  192.                         20-23    6       24     96
  193.  
  194. --Mark Brader (msb@sq.com)
  195.  
  196. ==> arithmetic/clock/reversible.p <==
  197. How many times per day can the hour and minute hands on an analog clock switch
  198. roles and still signify a valid time, ignoring the second hand?
  199.  
  200. ==> arithmetic/clock/reversible.s <==
  201. Have 12 clocks C1, C2 ... C12 show 1:00, 2:00, ..., 12:00.  Have a
  202. clock C0 show 12:00
  203.  
  204. Now turn C0 around 12 hours, simultaneously turning C1-C12 so their
  205. hour hands always coincide with the minute hand of C0, i.e., as C0
  206. spans 12 hours, C1-C12 will span 1 hour, but for each possible placing
  207. of the hour hand, all 12 possible 'true' placings of the minute hand
  208. will be represented by one of the 12 clocks.
  209.  
  210. Each time the hour hand of C0 coincides with the minute hand of a
  211. C1-C12 clock we have a reversible valid time.  This happens regularly
  212. 12 times each C0 hour, but the first and last time is equal (12:00), so
  213. the number of reversible true times is 12*12-1 = 143 spaced regularly
  214. in the 12-hour interval, ie. each 5 min 2.0979+ sec
  215.  
  216. -- 
  217. stein.kulseth@tf.tele.no [X.400] stein.kulseth@nta.no [internet]
  218.  
  219. ==> arithmetic/clock/right.angle.p <==
  220. How many times per day do the hour and minute hands of a clock form a
  221. right angle?
  222.  
  223.  
  224. ==> arithmetic/clock/right.angle.s <==
  225. 44.  Twice each hour equals 48, less one between 2:00 and 4:00 and one between
  226. 8:00 and 10:00 for both A.M. and P.M.
  227.  
  228. ==> arithmetic/clock/thirds.p <==
  229. Do the 3 hands on a clock ever divide the face of the clock into 3
  230. equal segments, i.e. 120 degrees between each hand?       
  231.  
  232. ==> arithmetic/clock/thirds.s <==
  233. First let us assume that our clock has 60 divisions.  We will show that
  234. any time the hour hand and the minute hand are 20 divisions (120 degrees)
  235. apart, the second hand cannot be an integral number of divisions from the
  236. other hands, unless it is straight up (on the minute).
  237.  
  238. Let us use h for hours, m for minutes, and s for seconds.
  239. We will use =n to mean congruent mod n, thus 12 =5 7.
  240.  
  241. We know that m =60 12h, that is, the minute hand moves 12 times as fast
  242. as the hour hand, and wraps around at 60.
  243. We also have s =60 60m. This simplifies to s/60 =1 m, which goes to
  244. s/60 = frac(m) (assuming s is in the range 0 <= s < 60), which goes to
  245. s = 60 frac(m).  Thus, if m is 5.5, s is 30.
  246.  
  247. Now let us assume the minute hand is 20 divisions ahead of the hour hand.
  248. So m =60 h + 20, thus 12h =60 h + 20, 11h =60 20, and, finally,
  249. h =60/11 20/11 (read 'h is congruent mod 60/11 to 20/11').
  250. So all values of m are k + n/11 for some integral k and integral n,
  251. 0 <= n < 11.  s is therefore 60n/11.  If s is to be an integral number of
  252. units from m and h, we must have 60n =11 n.  But 60 and 11 are relatively
  253. prime, so this holds only for n = 0.  But if n = 0, m is integral, so
  254. s is 0.
  255.  
  256. Now assume, instead, that the minute hand is 20 divisions behind the hour hand.
  257. So m =60 h - 20, 12h =60 h - 20, 11h =60 -20, h =60/11 -20/11.
  258. So m is still k + n/11.  Thus s must be 0.
  259.  
  260. But if s is 0, h must be 20 or 40.  But this translates to 4 o'clock or
  261. 8 o'clock, at both of which the minute hand is at 0, along with the second
  262. hand.
  263.  
  264. Thus the 3 hands can never be 120 degrees apart, Q.E.D.
  265.  
  266. This assumes, of course, that the second hand is synchronized with the
  267. minute hand.  This is not true on some inexpensive analog watches.  This
  268. also assumes that the watch is not broken (:^)).
  269.  
  270. ==> arithmetic/consecutive.composites.p <==
  271. Are there 10,000 consecutive non-prime numbers?
  272.  
  273. ==> arithmetic/consecutive.composites.s <==
  274. 9973!+2 through 9973!+10006 are composite.
  275.  
  276. ==> arithmetic/consecutive.product.p <==
  277. Prove that the product of three or more consecutive positive integers cannot
  278. be a perfect square.
  279.  
  280. ==> arithmetic/consecutive.product.s <==
  281. Three consecutive numbers:
  282.   If a and b are relatively prime, and ab is a square,
  283.   then a and b are squares. (This is left as an exercise.)
  284.  
  285.   Suppose (n - 1)n(n + 1) = k^2, where n > 1.  
  286.   Then n(n^2 - 1) = k^2.  But n and (n^2 - 1) are relatively prime.
  287.   Therefore n^2 - 1 is a perfect square, which is a contradiction.
  288.  
  289. Four consecutive numbers:
  290.   n(n + 1)(n + 2)(n + 3) = (n^2 + 3n + 1)^2 - 1
  291.  
  292. Five consecutive numbers:
  293.   Assume the product is a integer square, call it m.
  294.  
  295.   The prime factorization of m must have even numbers of each prime factor.
  296.  
  297.   For each prime factor, p, of m, p >= 5, p^2k must divide one of the
  298. consecutive naturals in the product.  (Otherwise, the difference between two
  299. of the naturals in the product would be a positive multiple of a prime >= 5.
  300. But in this problem, the greatest difference is 4.) So we need only consider
  301. the primes 2 and 3.
  302.  
  303.   Each of the consecutive naturals is one of:
  304.         1)      a perfect square
  305.         2)      2 times a perfect square
  306.         3)      3 times a perfect square
  307.         4)      6 times a perfect square.
  308.  
  309.   By the shoe box principle, two of the five consecutive numbers must fall into
  310. the same category.
  311.  
  312.   If there are two perfect squares, then their difference being less than five
  313. limits their values to be 1 and 4.  (0 is not a natural number, so 0 and 1
  314. and 0 and 4 cannot be the perfect squares.)  But 1*2*3*4*5=120!=x*x where x
  315. is an integer.
  316.  
  317.   If there are two numbers that are 2 times a perfect square, then their
  318. difference being less than five implies that the perfect squares (which are
  319. multiplied by 2) are less than 3 apart, and no two natural squares differ by
  320. only 1 or 2.
  321.  
  322.   A similar argument holds for two numbers which are 3 times a perfect square.
  323.  
  324.   We cannot have the case that two of the 5 consecutive numbers are multiples
  325. (much less square multiples) of 6, since their difference would be >= 6, and
  326. our span of five consecutive numbers is only 4.
  327.  
  328.   Therefore the assumption that m is a perfect square does not hold.
  329.  
  330.   QED.
  331.  
  332. In general the equation:
  333.  
  334. y^2 = x(x+1)(x+2)...(x+n),    n > 3
  335.  
  336. has only the solution corresponding to y = 0.
  337.  
  338. This is a theorem of Rigge [O. Rigge, ``Uber ein diophantisches Problem'',
  339. IX Skan. Math. Kong. Helsingfors (1938)] and Erdos [P. Erdos, ``Note on
  340. products of consecutive integers,'' J. London Math. Soc. #14 (1939),
  341. pages 194-198].
  342.  
  343. A proof can be found on page 276 of [L. Mordell, ``Diophantine
  344. Equations'', Academic Press 1969].
  345.  
  346. ==> arithmetic/consecutive.sums.p <==
  347. Find all series of consecutive positive integers whose sum is exactly 10,000.
  348.  
  349. ==> arithmetic/consecutive.sums.s <==
  350. Generalize to find X (and I) such that
  351.     (X + X+1 + X+2 + ... + X+I) = T
  352. for any integer T.
  353.  
  354. You are asking for all (X,I) s.t. (2X+I)(I+1) = 2T.  The problem is
  355. (very) slightly easier if we don't restrict X to being positive, so
  356. we'll solve this first.
  357.  
  358. Note that 2X+I and I+1 must have different parities, so the answer
  359. to the relaxed question is N = 2*(o_1+1)*(o_2+1)*...*(o_n+1), where
  360. 2T = 2^o_0*3^o_1*...*p_n^o_n (the prime factorization); this is easily
  361. seen to be the number of ways we can break 2T up into two positive
  362. factors of differing parity (with order).
  363.  
  364. In particular, 20000 = 2^5*5^4, hence there are 2*(4+1) = 10 solutions
  365. for T = 10000.  These are (2X+I,I+1):
  366.  
  367. (32*1,5^4)   (32*5,5^3)   (32*5^2,5^2)   (32*5^3,5)   (32*5^4,1)
  368. (5^4,32*1)   (5^3,32*5)   (5^2,32*5^2)   (5,32*5^3)   (1,32*5^4)
  369.  
  370. And they give rise to the solutions (X,I):
  371.  
  372. (-296,624)   (28,124)   (388,24)   (1998,4)     (10000,0)
  373. (297,31)     (-27,179)  (-387,799) (-1997,3999) (-9999,19999)
  374.  
  375. If you require that X>0 note that this is true iff 2X+I > I+1 and
  376. hence the number of solutions to this problem is N/2 (due to the
  377. symmetry of the above ordered pairs).
  378.  
  379. ==> arithmetic/conway.p <==
  380. Describe the sequence a(1)=a(2)=1, a(n) = a(a(n-1)) + a(n-a(n-1)) for n>2.
  381.  
  382. ==> arithmetic/conway.s <==
  383. This sequence and its remarkable properties were discovered, apparently
  384. independently, by Douglas Hofstadter (circa 1975), John Conway (in the
  385. early 1980's), B.W. Connoly, and others. Since Conway discovered many of
  386. the deeper properties, and is the one responsible for popularizing the
  387. sequence, it seems appropriate to name the sequence after him.
  388.  
  389. Some properties of a(n):
  390.  
  391. --  a(n+1) - a(n) = 0 or 1
  392.  
  393. --  a(2^n) = 2^(n-1)
  394.  
  395. --  n/2 <= a(n) <= n
  396.  
  397. --  A(n)= 2a(n) - n    has zeros at the powers of 2 and 
  398.      positive "humps" in between
  399.  
  400. --  A(2^n + t) = A(2^(n+1) - t)  for t between 0 and 2^n,
  401.      i.e. the humps are symmetric
  402.  
  403. -- a(2n) <= 2a(n)
  404.  
  405. -- a(n)/n --> 1/2  as  n --> infinity
  406.  
  407. -- a(n) and A(n) are self-similar, in the sense that their values on the
  408.    (N+1)'st hump can be obtained by a "magnification" process applied
  409.    to the values on the N'th hump. They are *not* chaotic sequences,
  410.    since their asymptotics and combinatorial structure are very regular
  411.    and rigid.
  412.  
  413. In a lecture at Bell Labs in 1988, Conway asked for the rate at
  414. which  a(n)/n converges to 1/2.  In particular, he asked for
  415. N(epsilon), the last value of  n  such that  |a(n)/n - 1/2|
  416. exceeds epsilon, in the case  epsilon=1/20.  This problem was
  417. solved by Colin Mallows of Bell Labs: he found that  N(1/20)=1489
  418. and N(1/40)=6083008742. These values are reported in his article
  419. in the American Mathematical Monthly, January 1991, p. 5.
  420.  
  421. Conway's sequence has a deep combinatorial structure, and is intimately
  422. connected with all of the following: variants of Pascal's triangle, the
  423. Gaussian distribution, combinatorial operations on finite sets,
  424. coin-pushing games, and Fibonacci and Catalan numbers.  All of this is
  425. explained in my joint paper with Ravi Vakil; anyone who would like to
  426. receive a copy in LaTex format should contact me at the e-mail address
  427. listed below.
  428.  
  429. One byproduct of our work is an algorithm to determine  N(epsilon) for
  430. given positive epsilon.  Here are some particular values:
  431.  
  432.  e      Last  n  such that   |a(n)/n - 1/2| > e
  433. ----    ----------------------------------------------------------
  434. 1/20    1489  (found by Mallows in 1988)
  435. 1/30    758765
  436. 1/40    6083008742  (found by Mallows in 1988)
  437. 1/50    809308036481621
  438. 1/60    1684539346496977501739
  439. 1/70    55738373698123373661810220400
  440. 1/80    15088841875190938484828948428612052839
  441. 1/90    127565909103887972767169084026274554426122918035
  442. 1/100   8826608001127077619581589939550531021943059906967127007025
  443.  
  444. These values were computed by the Mathematica program listed below; the
  445. algorithm is explained in our paper.  To use the program, load it into
  446. Mathematica and type   neps[t]  for some numerical value of  t  (which
  447. should probably be smaller than 1/5 or so). The program will output  N(t),
  448. e.g.  neps[1/20] = 1489. These numbers grow very fast: N(epsilon) will be
  449. about 2^((0.138015/epsilon)^2), so  N(1/1000) will have about 5735 digits.
  450. The program requires very little memory space, but its runtime appears to
  451. grow rapidly as epsilon decreases (on a Sun 3, it took about one second to
  452. find the first value listed, and several minutes to find the last).
  453.  
  454. neps[eps_] := Block[{W}, L = 1 + Floor[(0.138015/eps)^2]; e = eps*2; 
  455.     W = processvector[L]; While[Length[W] > 0, 
  456.      nmax = 1 + Last[W][[4]]; L++; W = processvector[L]]; nmax]
  457.  
  458. processvector[L_] := 
  459.   Block[{V}, V = startvector[L]; While[notfound[V], V = newbody[V]]; V]
  460.  
  461. startvector[L_] := Select[initialvector[L], gt]
  462.  
  463. initialvector[L_] := 
  464.   Table[{L, b, Binomial[L - 1, b - 1], 
  465.     2^(L + 1) - Sum[Binomial[L, c], {c, b, L}]}, {b, 0, L - 1}]
  466.  
  467. c[0] = 0
  468.  
  469. c[n_] := c[n] = Sum[Binomial[2*a, a]/(a + 1), {a, 0, n - 1}]
  470.  
  471. gt[x_] := U[x] > e
  472.  
  473. U[x_] := (x[[3]] + M[x[[1]], x[[2]]])/(x[[4]] + incp[x[[1]], x[[2]]])
  474.  
  475. M[n_, n_] = -1
  476.  
  477. M[n_, k_] := Binomial[n - 1, K[n, k]] - Binomial[n - 1, k - 1] + c[K[n, k]]
  478.  
  479. K[n_, k_] := Min[k, n - k]
  480.  
  481. incp[n_, k_] := Max[M[n, k], 1]
  482.  
  483. notfound[V_] := 
  484.   Length[V] > 0 && Last[V][[2]] > 0 && Last[V][[1]] > Last[V][[2]]
  485.  
  486. newbody[V_] := Join[Drop[V, -1], newtail[V]]
  487.  
  488. newtail[V_] := Select[{vleft[Last[V]], vright[Last[V]]}, gt]
  489.  
  490. vleft[x_] := {x[[1]] - 1, x[[2]] - 1, x[[3]], x[[4]]}
  491.  
  492. vright[x_] := {x[[1]] - 1, x[[2]], x[[3]] + S[x[[1]] - 1, x[[2]] - 1], 
  493.    x[[4]] + Binomial[x[[1]] - 1, x[[2]] - 1]}
  494.  
  495. S[n_, k_] := Binomial[n - 1, k] - Binomial[n - 1, k - 1]
  496.  
  497.  
  498. -Tal Kubo     kubo@math.harvard.edu  or   kubo@zariski.harvard.edu
  499.  
  500. ==> arithmetic/digits/6.and.7.p <==
  501. Does every number which is not divisible by 5 have a multiple whose
  502. only digits are 6 and 7?
  503.  
  504. ==> arithmetic/digits/6.and.7.s <==
  505. Yes.  My proof follows:
  506.  
  507. Claim 1: For every k, there is a k-digit number whose only digits
  508. are 6 and 7, which is divisible by 2^k.
  509.  
  510. The proof is by induction.  Suppose N is a k-digit number 
  511. satisfying the above condition.  Then either N = 0 (mod 2^(k+1))
  512. or N = 2^k (mod 2^(k+1)). Note that 6(10^k) = 0 (mod 2^(k+1)),
  513. and 7(10^k) = 2^k (mod 2^(k+1)).  So, either 6*10^k + N or
  514. 7*10^k + N is divisible by 2^(k+1).
  515.  
  516. Claim 2:  If m and 10 are relatively prime, then for any r,
  517. there is a number N whose only digits are 6 and 7 such that
  518. N = r (mod m). 
  519.  
  520. Proof:  Let K be the (m^2)-digit number whose only digit is 6.
  521. There is an s, 0 <= s < m, so that K + s = r (mod m).
  522. Let N = K + 10^(m - 1) + 10^(2m - 2) + . . . + 10^(sm - s).
  523. Since 10^(im - i) = 1 (mod m), N = K + s (mod m) = r (mod m).
  524. Clearly, every digit of N is either 6 or 7. 
  525.  
  526. Claim 3: If n is not divisible by 5, then there is a number N whose
  527. only digits are 6 and 7, so that N is divisible by n. 
  528.  
  529. Proof:  We can write n = (2^k)m, with gcd(m,10)=1.
  530. Use claim 1 to find a k-digit number M, whose only digits are 6 and 7,
  531. which is divisible by 2^k.  Choose an integer r so that
  532. (10^k)r + M = 0 (mod m).  Use claim 2 to find a number K whose
  533. only digits are 6 and 7, so that K = r (mod m).  Let N = 10^k K + M.
  534. Then N = 0 (mod m) and N = 0 (mod 2^k), so N is divisible by n.
  535. Finally, the only digits of N are 6 and 7, so we are done.
  536.  
  537. --
  538. David Radcliffe                                radcliff@csd4.csd.uwm.edu
  539.  
  540. ==> arithmetic/digits/all.ones.p <==
  541. Prove that some multiple of any integer ending in 3 contains all 1s.
  542.  
  543. ==> arithmetic/digits/all.ones.s <==
  544. Let n be our integer; one such desired multiple is then
  545. (10^(phi(n))-1)/9.  All we need is that (n,10) = 1, and if the last
  546. digit is 3 this must be the case.  A different proof using the
  547. pigeonhole principle is to consider the sequence 1, 11, 111, ..., (10^n
  548. - 1)/9.  We must have at some point that either some member of our
  549. sequence = 0 (mod n) or else some value (mod n) is duplicated.  Assume
  550. the latter, with x_a and x_b, x_b>x_a,  possesing the duplicated
  551. remainders.  We then have that x_b - x-a = 0 (mod n).  Let m be the
  552. highest power of 10 dividing x_b - x_a.  Now since (10,n) = 1, we can
  553. divide by 10^m and get that (x_b - x_a)/10^m = 0 (n).  But (x_b -
  554. x_a)/10^m is a number containing only the digit 1.
  555.  
  556. Q.E.D.
  557.  
  558. ==> arithmetic/digits/arabian.p <==
  559. What is the Arabian Nights factorial, the number x such that x! has 1001
  560. digits?  How about the prime x such that x! has exactly 1001 zeroes on
  561. the tail end.  (Bonus question, what is the 'rightmost' non-zero digit in x!?)
  562.  
  563. ==> arithmetic/digits/arabian.s <==
  564. The first answer is 450!.
  565.  
  566. Determining the number of zeroes at the end of x! is relatively easy once
  567. you realize that each such zero comes from a factor of 10 in the product
  568.  
  569.    1 * 2 * 3 * ... * x
  570.  
  571. Each factor of 10, in turn, comes from a factor of 5 and a factor of 2.
  572. Since there are many more factors of 2 than factors of 5, the number of 5s
  573. determines the number of zeroes at the end of the factorial.
  574.  
  575. The number of 5s in the set of numbers 1 .. x (and therefore the number
  576. of zeroes at the end of x!) is:
  577.  
  578.   z(x) = int(x/5) + int(x/25) + int(x/125) + int(x/625) + ...
  579.  
  580. This series terminates when the powers of 5 exceed x.
  581.  
  582. I know of no simple way to invert the above formula (i.e., to find x for
  583. a given z(x)), but I can approximate it by noting that, except for the "int"
  584. function,
  585.  
  586.    5*z(x) - x = z(x)
  587.  
  588. which gives:
  589.  
  590.    x = 4*z(x) (approximately).
  591.  
  592. The given problem asked, "For what prime x is z(x)=1001".  By the above forumla
  593. ,
  594. this is approximately 4*1001=4004.  However, 4004! has only
  595.  
  596.   800 + 160 + 32 + 6 + 1 = 999 zeroes at the end of it.
  597.  
  598. The numbers 4005! through 4009! all have 1000 zeroes at their end and
  599. the numbers 4010! through 4014! all have 1001 zeroes at their end.
  600.  
  601. Since the problem asked for a prime x, and 4011 = 3*7*191, the only solution
  602. is x=4013.
  603.  
  604. The problem of determining the rightmost nonzero digit in x! is somewhat more
  605. difficult.  If we took the numbers 1, 2, ... , x and removed all factors of 5
  606. (and an equal number of factors of 2), the remaining numbers multiplied
  607. together modulo 10 would be the answer.  Note that since there are still many
  608. factors of 2 left, the rightmost nonzero digit must be 2, 4, 6, or 8 (x > 1).
  609.  
  610. Letting r(x) be the rightmost nonzero digit in x!, an expression for r(x) is:
  611.  
  612.   r(x) = (r(int(x/5)) * w * r(x mod 10)) mod 10, x >= 10.
  613.  
  614. where w is 4 if int(x/10) is odd and 6 if it is even.
  615.  
  616. The values of r(x) for 0 <= x <= 9 are 1, 1, 2, 6, 4, 2, 2, 4, 2, and 8.
  617.  
  618. The way to see this is true is to take the numbers 1, 2, ..., x in groups
  619. of 10.  In each group, remove 2 factors of 10.  For example, from the
  620. set 1, 2, ..., 10, choose a factor of 2 from 2 and 6 and a factor of 5 from
  621. 5 and 10.  This leaves 1, 1, 3, 4, 1, 3, 7, 8, 9, 2.  Next, separate all the
  622. factors that came from multiples of 5.  The rightmost nonzero digit of x!
  623. can now (hopefully) be seen to be:
  624.  
  625.   r(x) = (r(int(x/5)) * w * r(x mod 10)) mod 10
  626.  
  627. where w is the rightmost digit in the number formed by multiplying the numbers
  628. 1, 2, 3, ..., 10*int(x/10) after the factors of 10 and the factors left over
  629. by the multiples of 5 have been removed.  In the example with x = 10, this
  630. would be (1 * 1 * 3 * 4 * 3 * 7 * 8 * 9) mod 10 = 4.  The "r(x mod 10)" term
  631. takes care of the numbers from 10*int(x/10)+1 up to x.
  632.  
  633. The "w" term can be seen to be 4 or 6 depending on whether int(x/10) is odd or
  634. even since, after removing 10*n+5 and 10*n+10 and a factor of 2 each from
  635. 10*n+2 and 10*n+6 from the group of numbers 10*n+1 through 10*n+10, the
  636. remaining factors (mod 10) always equals 4 and 4^t mod 10 = 4 if t is odd and
  637. 6 when t is even (t != 0).
  638.  
  639. So, finally, the rightmost nonzero digit in 4013! is found as follows:
  640.  
  641.   r(4013) = (r(802) * 4 * 6) mod 10
  642.   r(802)  = (r(160) * 6 * 2) mod 10
  643.   r(160)  = (r(32)  * 6 * 1) mod 10
  644.   r(32)   = (r(6)   * 4 * 2) mod 10
  645.  
  646. Using a table of r(x) for 0 <= x <= 9, r(6) = 2.  Then,
  647.  
  648.   r(32)   = (2 * 4 * 2) mod 10 = 6
  649.   r(160)  = (6 * 6 * 1) mod 10 = 6
  650.   r(802)  = (6 * 6 * 2) mod 10 = 2
  651.   r(4013) = (2 * 4 * 6) mod 10 = 8
  652.  
  653. Thus, the rightmost nonzero digit in 4013! is 8.
  654.  
  655. ==> arithmetic/digits/circular.p <==
  656. What 6 digit number, with 6 different digits, when multiplied by all integers
  657. up to 6, circulates its digits through all 6 possible positions, as follows:
  658. ABCDEF * 1 = ABCDEF
  659. ABCDEF * 3 = BCDEFA
  660. ABCDEF * 2 = CDEFAB
  661. ABCDEF * 6 = DEFABC
  662. ABCDEF * 4 = EFABCD
  663. ABCDEF * 5 = FABCDE
  664.  
  665. ==> arithmetic/digits/circular.s <==
  666. ABCDEF=142857 (the digits of the expansion of 1/7).
  667.  
  668. ==> arithmetic/digits/divisible.p <==
  669. Find the least number using 0-9 exactly once that is evenly divisible by each
  670. of these digits.
  671.  
  672. ==> arithmetic/digits/divisible.s <==
  673. Since the sum of the digits is 45, any permutation of the digits gives a
  674. multiple of 9.  To get a multiple of both 2 and 5, the last digit must
  675. be 0, and thus to get a multiple of 8 (and 4), the tens digit must be
  676. even, and the hundreds digit must be odd if the tens digit is 2 or 6,
  677. and even otherwise.  The number will also be divisible by 6, since it is
  678. divisible by 2 and 3, so 7 is all we need to check.  First, we will look
  679. for a number whose first five digits are 12345; now, 1234500000 has a
  680. remainder of 6 when divided by 7, so we have to arrange the remaining
  681. digits to get a remainder of 1.  The possible arrangements, in
  682. increasing order, are
  683.  
  684. 78960, remainder 0
  685. 79680, remainder 6
  686. 87960, remainder 5
  687. 89760, remainder 6
  688. 97680, remainder 2
  689. 98760, remainder 4
  690.  
  691. That didn't work, so try numbers starting with 12346; this is impossible
  692. because the tens digit must be 8, and the hundreds digit cannot be even.
  693. Now try 12347, and 1234700000 has remainder 2.  The last five digits can
  694. be
  695.  
  696. 58960, remainder 6
  697. 59680, remainder 5, so this works, and the number is
  698.  
  699. 1234759680.
  700.  
  701. ==> arithmetic/digits/equations/123456789.p <==
  702. In how many ways can "." be replaced with "+", "-", or "" (concatenate) in
  703. .1.2.3.4.5.6.7.8.9=1 to form a correct equation?
  704.  
  705. ==> arithmetic/digits/equations/123456789.s <==
  706.  1-2 3+4 5+6 7-8 9 = 1
  707. +1-2 3+4 5+6 7-8 9 = 1
  708.  1+2 3+4-5+6 7-8 9 = 1
  709. +1+2 3+4-5+6 7-8 9 = 1
  710. -1+2 3-4+5+6 7-8 9 = 1
  711.  1+2 3-4 5-6 7+8 9 = 1
  712. +1+2 3-4 5-6 7+8 9 = 1
  713.  1-2 3-4+5-6 7+8 9 = 1
  714. +1-2 3-4+5-6 7+8 9 = 1
  715.  1-2-3-4 5+6 7-8-9 = 1
  716. +1-2-3-4 5+6 7-8-9 = 1
  717.  1+2-3 4+5 6-7-8-9 = 1
  718. +1+2-3 4+5 6-7-8-9 = 1
  719. -1+2 3+4+5-6-7-8-9 = 1
  720. -1 2+3 4-5-6+7-8-9 = 1
  721.  1+2+3+4-5+6+7-8-9 = 1
  722. +1+2+3+4-5+6+7-8-9 = 1
  723. -1+2+3-4+5+6+7-8-9 = 1
  724.  1-2-3+4+5+6+7-8-9 = 1
  725. +1-2-3+4+5+6+7-8-9 = 1
  726.  1+2 3+4 5-6 7+8-9 = 1
  727. +1+2 3+4 5-6 7+8-9 = 1
  728.  1+2 3-4-5-6-7+8-9 = 1
  729. +1+2 3-4-5-6-7+8-9 = 1
  730.  1+2+3+4+5-6-7+8-9 = 1
  731. +1+2+3+4+5-6-7+8-9 = 1
  732. -1+2+3+4-5+6-7+8-9 = 1
  733.  1-2+3-4+5+6-7+8-9 = 1
  734. +1-2+3-4+5+6-7+8-9 = 1
  735. -1-2-3+4+5+6-7+8-9 = 1
  736.  1-2+3+4-5-6+7+8-9 = 1
  737. +1-2+3+4-5-6+7+8-9 = 1
  738.  1+2-3-4+5-6+7+8-9 = 1
  739. +1+2-3-4+5-6+7+8-9 = 1
  740. -1-2+3-4+5-6+7+8-9 = 1
  741. -1+2-3-4-5+6+7+8-9 = 1
  742. -1+2 3+4 5-6 7-8+9 = 1
  743.  1-2 3-4 5+6 7-8+9 = 1
  744. +1-2 3-4 5+6 7-8+9 = 1
  745. -1+2 3-4-5-6-7-8+9 = 1
  746. -1+2+3+4+5-6-7-8+9 = 1
  747.  1-2+3+4-5+6-7-8+9 = 1
  748. +1-2+3+4-5+6-7-8+9 = 1
  749.  1+2-3-4+5+6-7-8+9 = 1
  750. +1+2-3-4+5+6-7-8+9 = 1
  751. -1-2+3-4+5+6-7-8+9 = 1
  752.  1+2-3+4-5-6+7-8+9 = 1
  753. +1+2-3+4-5-6+7-8+9 = 1
  754. -1-2+3+4-5-6+7-8+9 = 1
  755. -1+2-3-4+5-6+7-8+9 = 1
  756.  1-2-3-4-5+6+7-8+9 = 1
  757. +1-2-3-4-5+6+7-8+9 = 1
  758.  1-2 3+4+5+6+7-8+9 = 1
  759. +1-2 3+4+5+6+7-8+9 = 1
  760.  1+2+3+4 5-6 7+8+9 = 1
  761. +1+2+3+4 5-6 7+8+9 = 1
  762.  1 2+3 4+5-6 7+8+9 = 1
  763. +1 2+3 4+5-6 7+8+9 = 1
  764.  1+2+3-4-5-6-7+8+9 = 1
  765. +1+2+3-4-5-6-7+8+9 = 1
  766. -1+2-3+4-5-6-7+8+9 = 1
  767.  1-2-3-4+5-6-7+8+9 = 1
  768. +1-2-3-4+5-6-7+8+9 = 1
  769. -1-2-3-4-5+6-7+8+9 = 1
  770. -1-2 3+4+5+6-7+8+9 = 1
  771.  1-2+3 4-5 6+7+8+9 = 1
  772. +1-2+3 4-5 6+7+8+9 = 1
  773.  1 2-3 4+5-6+7+8+9 = 1
  774. +1 2-3 4+5-6+7+8+9 = 1
  775. Total solutions  = 69 (26 of which have a leading "+", which is redundant)
  776.  
  777. 69/19683 = 0.35 %
  778.  
  779. for those who care (it's not very elegant but it did the trick):
  780.  
  781. #include <stdio.h>
  782. #include <math.h>
  783.  
  784. main (argc,argv)
  785.      int argc;
  786.      char *argv[];
  787. {
  788.   int sresult, result, operator[10],thisop;
  789.   char buf[256],ops[3];
  790.   int i,j,tot=0,temp;
  791.   
  792.   ops[0] = ' ';
  793.   ops[1] = '-';
  794.   ops[2] = '+';
  795.  
  796.   for (i=1; i<10; i++) operator[i] = 0;
  797.   
  798.   for (j=0; j < 19683; j++) {
  799.     result = 0;
  800.     sresult = 0;
  801.     thisop = 1;
  802.     for (i=1; i<10; i++) {
  803.       switch (operator[i]) {
  804.       case 0:
  805.         sresult = sresult * 10 + i;
  806.         break;
  807.       case 1:
  808.         result = result + sresult * thisop;
  809.         sresult = i;
  810.         thisop = -1;
  811.         break;
  812.       case 2:
  813.         result = result + sresult * thisop;
  814.         sresult = i;
  815.         thisop = 1;
  816.         break;
  817.       }
  818.     }
  819.   
  820.     result  = result + sresult * thisop;
  821.     if (result == 1) {
  822.       tot++;
  823.       for  (i=1;i<10;i++) 
  824.         printf("%c%d",ops[operator[i]],i);
  825.       printf(" = %d\n",result);
  826.     }
  827.     temp = 0;
  828.     operator[1] += 1;
  829.     for (i=1;i<10;i++) {
  830.       operator[i] += temp;
  831.       if (operator[i] > 2) { operator[i] = 0; temp = 1;}
  832.       else temp = 0;
  833.     }
  834.   
  835.   }
  836.   
  837.   printf("Total solutions  = %d\n" , tot);
  838. }
  839.  
  840. cwren@media.mit.edu (Christopher Wren)
  841.  
  842. ==> arithmetic/digits/equations/1992.p <==
  843. 1 = -1+9-9+2.  Extend this list to 2 through 100 on the left side of
  844. the equals sign.
  845.  
  846. ==> arithmetic/digits/equations/1992.s <==
  847. 1 = -1+9-9+2
  848. 2 = 1*9-9+2
  849. 3 = 1+9-9+2
  850. 4 = 1+9/9+2
  851. 5 = 1+9-sqrt(9)-2
  852. 6 = 1^9+sqrt(9)+2
  853. 7 = -1+sqrt(9)+sqrt(9)+2
  854. 8 = 19-9-2
  855. 9 = (1/9)*9^2
  856. 10= 1+(9+9)/2
  857. 11= 1+9+sqrt(9)-2
  858. 12= 19-9+2
  859. 13= (1+sqrt(9))!-9-2
  860. 14= 1+9+sqrt(9)!-2
  861. 15= -1+9+9-2
  862. 16= -1+9+sqrt(9)!+2
  863. 17= 1+9+9-2
  864. 18= 1+9+sqrt(9)!+2
  865. 19= -1+9+9+2
  866. 20= (19-9)*2
  867. 21= 1+9+9+2
  868. 22= (-1+sqrt(9))*(9-2)
  869. 23= (1+sqrt(9))!-sqrt(9)+2
  870. 24= -1+9*sqrt(9)-2
  871. 25= 1*9*sqrt(9)-2
  872. 26= 19+9-2
  873. 27= 1*9+9*2
  874. 28= 1+9+9*2
  875. 29= 1*9*sqrt(9)+2
  876. 30= 19+9+2
  877. 31= (1+sqrt(9))!+9-2
  878. 32= -1+sqrt(9)*(9+2)
  879. 33= 1*sqrt(9)*(9+2)
  880. 34= (-1+9+9)*2
  881. 35= -1+(9+9)*2
  882. 36= 1^9*sqrt(9)!^2
  883. 37= 19+9*2
  884. 38= 1*sqrt(9)!*sqrt(9)!+2
  885. 39= 1+sqrt(9)!*sqrt(9)!+2
  886. 40= (1+sqrt(9)!)*sqrt(9)!-2
  887. 41= -1+sqrt(9)!*(9-2)
  888. 42= (1+sqrt(9))!+9*2
  889. 43= 1+sqrt(9)!*(9-2)
  890. 44= -1+9*(sqrt(9)+2)
  891. 45= 1*9*(sqrt(9)+2)
  892. 46= 1+9*(sqrt(9)+2)
  893. 47= (-1+sqrt(9)!)*9+2
  894. 48= 1*sqrt(9)!*(sqrt(9)!+2)
  895. 49= (1+sqrt(9)!)*(9-2)
  896. 50= (-1+9)*sqrt(9)!+2
  897. 51= -1+9*sqrt(9)!-2
  898. 52= 1*9*sqrt(9)!-2
  899. 53= -1+9*sqrt(9)*2
  900. 54= 1*9*sqrt(9)*2
  901. 55= 1+9*sqrt(9)*2
  902. 56= 1*9*sqrt(9)!+2
  903. 57= 1+9*sqrt(9)!+2
  904. 58= (1+9)*sqrt(9)!-2
  905. 59= 19*sqrt(9)+2
  906. 60= (1+9)*sqrt(9)*2
  907. 61= (1+sqrt(9)!)*9-2
  908. 62= -1+9*(9-2)
  909. 63= 1*9*(9-2)
  910. 64= 1+9*(9-2)
  911. 65= (1+sqrt(9)!)*9+2
  912. 66= 1*sqrt(9)!*(9+2)
  913. 67= 1+sqrt(9)!*(9+2)
  914. 68= -(1+sqrt(9))!+92
  915. 69= (1+sqrt(9))!+(9/.2)
  916. 70= (1+9)*(9-2)
  917. 71= -1-9+9^2
  918. 72= (1+sqrt(9))*9*2
  919. 73= -19+92
  920. 74= (-1+9)*9+2
  921. 75= -1*sqrt(9)!+9^2
  922. 76= 1-sqrt(9)!+9^2
  923. 77= (1+sqrt(9)!)*(9+2)
  924. 78= -1+9*9-2
  925. 79= 1*9*9-2
  926. 80= 1+9*9-2
  927. 81= 1*9*sqrt(9)^2
  928. 82= -1+9*9+2
  929. 83= 1*9*9+2
  930. 84= 1+9*9+2
  931. 85= -1-sqrt(9)!+92
  932. 86= -1*sqrt(9)!+92
  933. 87= 1-sqrt(9)!+92
  934. 88= (1+9)*9-2
  935. 89= -1*sqrt(9)+92
  936. 90= 1-sqrt(9)+92
  937. 91= -1^9+92
  938. 92= (1+9)*9+2
  939. 93= 1^9+92
  940. 94= -1+sqrt(9)+92
  941. 95= 19*(sqrt(9)+2)
  942. 96= -1+99-2
  943. 97= 1*99-2
  944. 98= 1+99-2
  945. 99= 1*9*(9+2)
  946. 100= -1+99+2
  947.  
  948. ==> arithmetic/digits/equations/24.p <==
  949. Form an expression that evaluates to 24 that contains two 3's, two 7's,
  950. and zero or more of the operators +, -, *, and /, and parentheses.  What
  951. about two 4's and two 7's, or three 5's and one 1, or two 3's and two 8's?
  952.  
  953. ==> arithmetic/digits/equations/24.s <==
  954. 7*(3+3/7)
  955. 7*(4-4/7)
  956. 5*(5-1/5)
  957. 8/(3-8/3)
  958.  
  959. ==> arithmetic/digits/equations/383.p <==
  960. Make 383 out of 1,2,25,50,75,100 using +,-,*,/.
  961.  
  962. ==> arithmetic/digits/equations/383.s <==
  963. You can get 383 with ((2+50)/25+1)*100+75.
  964.  
  965. Of course, if you expect / as in C, the above expression is just 375.
  966. But then you can get 383 with (25*50-100)/(1+2).  Pity there's no way
  967. to use the 75.
  968.  
  969. If we had a language that rounded instead of truncating, we could use
  970. ((1+75+100)*50)/(25-2) or (2*75*(25+100))/(50-1).
  971.  
  972. I imagine your problem lies in not dividing things that aren't
  973. divisible.
  974.  
  975. Dan Hoey
  976. Hoey@AIC.NRL.Navy.Mil
  977.  
  978. ==> arithmetic/digits/equations/find.p <==
  979. Write a program for finding expressions built out of given numbers and using
  980. given operators that evaluate to a given value, or listing all possible values.
  981.  
  982. ==> arithmetic/digits/equations/find.s <==
  983. As set up, it requires recompilation for different sets of numbers;
  984. it's currently set up for 8,8,3,3; to try in other numbers, stick 'em
  985. in the 'val' array.  To find all target numbers for which the equation
  986. is valid, uncomment the 't' loop and 'target = t', and extend the range
  987. to be checked... you might want to turn off VERBOSE.  I don't bother
  988. with eliminating symmetries if equal vals are given (like 8 8 3 3), so
  989. I normally use it like
  990.  
  991.         numop 24 | sort | uniq
  992.  
  993. As it stands, this gives the output:
  994.  
  995. 8 / (3 - (8 / 3)) = 24.0
  996. 8 / (3 - (8 / 3)) = 24.0
  997. 8 / (3 - (8 / 3)) = 24.0
  998. 8 / (3 - (8 / 3)) = 24.0
  999.  
  1000. As you can see, there are five different kinds of binary trees with
  1001. exactly four leaf nodes.  The program tries all four operators in each
  1002. place, and all four values in each of the leaves, guaranteeing that each
  1003. is used only once... a fairly quick operation.  A small extract from
  1004. 'numop 1' shows the five different shapes of trees:
  1005.  
  1006. ((3 * 8) / 3) / 8 = 1.0
  1007. (3 * (8 / 3)) / 8 = 1.0
  1008. (3 - 3) + (8 / 8) = 1.0
  1009. 3 * ((8 / 3) / 8) = 1.0
  1010. 3 * (8 / (3 * 8)) = 1.0
  1011.  
  1012. Probably FUDGE ought to be set a little lower, for more confidence that
  1013. the equality isn't fortuitous.  Extensions to other binary operators are
  1014. obvious; unary operators and more values are not.  For a more general
  1015. problem I'd go recursive, use exact rational arithmetic, and have a fine
  1016. old time.
  1017.  
  1018. Enjoy...
  1019.  
  1020.         Jim Gillogly <uunet!rand.org!James_Gillogly>
  1021.         21 Wedmath S.R. 1993, 10:58
  1022. ----------------------------------------------------------------
  1023.  
  1024. /* numop: using elementary operations on 4 numbers, find a
  1025.  * desired result; e.g. 24.
  1026.  *
  1027.  * Don't worry about symmetries resulting in multiple correct answers.
  1028.  *
  1029.  * 11 Aug 93, SCRYER
  1030.  */
  1031.  
  1032. #include <stdio.h>
  1033.  
  1034. #define VERBOSE
  1035.  
  1036.  
  1037. #define MUL 0
  1038. #define DIV 1
  1039. #define ADD 2
  1040. #define SUB 3
  1041.  
  1042. #define FUDGE 0.01
  1043.  
  1044. float val[4] = {8, 8, 3, 3};
  1045. float eval(), atof(), fabs();
  1046. char nameop();
  1047.  
  1048. int divzero;
  1049.  
  1050. main(argc, argv)
  1051. int argc;
  1052. char *argv[];
  1053. {
  1054.     int op1, op2, op3;
  1055.     int iv1, iv2, iv3, iv4;
  1056.     int used[4];
  1057.     int i;
  1058.     float target;
  1059.     float e1, e2, e3;
  1060.     int t, winner;
  1061.  
  1062.     if (argc != 2)
  1063.     {
  1064.         fprintf(stderr, "Usage: numop <target>\n");
  1065.         exit(1);
  1066.     }
  1067.     target = atof(argv[1]);
  1068.  
  1069.  
  1070. /* for (t = -1000; t < 1000; t++) */
  1071.  {
  1072. /*    target = t;*/
  1073.     winner = 0;
  1074.  
  1075.     for (i = 0; i < 4; i++) used[i] = 0;
  1076.  
  1077.     for (op1 = 0; op1 < 4; op1++)
  1078.         for (op2 = 0; op2 < 4; op2++)
  1079.             for (op3 = 0; op3 < 4; op3++)
  1080.                 for (iv1 = 0; iv1 < 4; iv1++)
  1081.                 {
  1082.                     used[iv1] = 1;
  1083.                     for (iv2 = 0; iv2 < 4; iv2++)
  1084.                     {
  1085.                         if (used[iv2]) continue;
  1086.                         used[iv2] = 1;
  1087.                         for (iv3 = 0; iv3 < 4; iv3++)
  1088.                         {
  1089.                             if (used[iv3]) continue;
  1090.                             used[iv3] = 1;
  1091.                             for (iv4 = 0; iv4 < 4; iv4++)
  1092.                             {
  1093.                                 if (used[iv4]) continue;
  1094.  
  1095.                                 /* Case 1 */
  1096.                                 divzero = 0;
  1097.                                 e3 = eval(op3, val[iv3], val[iv4]);
  1098.                                 e2 = eval(op2, val[iv1], val[iv2]);
  1099.                                 e1 = eval(op1, e2, e3);                        
  1100.  /* (u + v) * (w - x) */
  1101.                                 if (fabs(e1 - target) < FUDGE && ! divzero)
  1102. #ifdef VERBOSE
  1103.                                     printf("(%.0f %c %.0f) %c (%.0f %c %.0f) = 
  1104. %.1f\n",
  1105.                                         val[iv1], nameop(op2), val[iv2], nameop
  1106. (op1),
  1107.                                         val[iv3], nameop(op3), val[iv4], e1);
  1108. #else
  1109.                                     winner = 1;
  1110. #endif
  1111.                                 /* Case 2 */
  1112.                                 divzero = 0;
  1113.                                 e3 = eval(op3, val[iv1], val[iv2]);
  1114.                                 e2 = eval(op2, e3, val[iv3]);
  1115.                                 e1 = eval(op1, e2, val[iv4]);                  
  1116.  /* ((u + v) * w) - x */
  1117.                                 if (fabs(e1 - target) < FUDGE && ! divzero)
  1118. #ifdef VERBOSE
  1119.                                     printf("((%.0f %c %.0f) %c %.0f) %c %.0f = 
  1120. %.1f\n",
  1121.                                         val[iv1], nameop(op3), val[iv2], nameop
  1122. (op2), val[iv3], nameop(op1), val[iv4], e1);
  1123. #else
  1124.                                     winner = 1;
  1125. #endif
  1126.  
  1127.                                 /* Case 3 */
  1128.                                 divzero = 0;
  1129.                                 e3 = eval(op3, val[iv2], val[iv3]);
  1130.                                 e2 = eval(op2, val[iv1], e3);
  1131.                                 e1 = eval(op1, e2, val[iv4]);                  
  1132.  /* (u + (v * w)) - x */
  1133.                                 if (fabs(e1 - target) < FUDGE && ! divzero)
  1134. #ifdef VERBOSE
  1135.                                     printf("(%.0f %c (%.0f %c %.0f)) %c %.0f = 
  1136. %.1f\n",
  1137.                                         val[iv1], nameop(op2), val[iv2], nameop
  1138. (op3), val[iv3],
  1139.                                         nameop(op1), val[iv4], e1);
  1140. #else
  1141.                                     winner = 1;
  1142. #endif
  1143.  
  1144.                                 /* Case 4 */
  1145.                                 divzero = 0;
  1146.                                 e3 = eval(op3, val[iv2], val[iv3]);
  1147.                                 e2 = eval(op2, e3, val[iv4]);
  1148.                                 e1 = eval(op1, val[iv1], e2);                  
  1149.  /* u + ((v * w) - x) */
  1150.                                 if (fabs(e1 - target) < FUDGE && ! divzero)
  1151. #ifdef VERBOSE
  1152.                                     printf("%.0f %c ((%.0f %c %.0f) %c %.0f) = 
  1153. %.1f\n",
  1154.                                         val[iv1], nameop(op1), val[iv2], nameop
  1155. (op3), val[iv3],
  1156.                                         nameop(op2), val[iv4], e1);
  1157. #else
  1158.                                     winner = 1;
  1159. #endif
  1160.  
  1161.                                 /* Case 5 */                                   
  1162.  /* u + (v * (w - x)) */
  1163.                                 divzero = 0;
  1164.                                 e3 = eval(op3, val[iv3], val[iv4]);
  1165.                                 e2 = eval(op2, val[iv2], e3);
  1166.                                 e1 = eval(op1, val[iv1], e2);
  1167.                                 if (fabs(e1 - target) < FUDGE && ! divzero)
  1168. #ifdef VERBOSE
  1169.                                     printf("%.0f %c (%.0f %c (%.0f %c %.0f)) = 
  1170. %.1f\n",
  1171.                                         val[iv1], nameop(op1), val[iv2], nameop
  1172. (op2), val[iv3],
  1173.                                         nameop(op3), val[iv4], e1);
  1174. #else
  1175.                                     winner = 1;
  1176. #endif
  1177.  
  1178.                             }
  1179.                             used[iv3] = 0;
  1180.                         }
  1181.                         used[iv2] = 0;
  1182.                     }
  1183.                     used[iv1] = 0;
  1184.                 }
  1185. #ifndef VERBOSE
  1186.      if (winner) printf("%d\n", t), fflush(stdout);
  1187. #endif
  1188.   }
  1189. }
  1190.  
  1191. char nameop(op)
  1192. int op;
  1193. {
  1194.     switch(op)
  1195.     {
  1196.         case MUL: return '*';
  1197.         case DIV: return '/';
  1198.         case ADD: return '+';
  1199.         case SUB: return '-';
  1200.     }
  1201.     return '?';
  1202. }
  1203.  
  1204. float eval(op, val1, val2)
  1205. int op;
  1206. float val1, val2;
  1207. {
  1208.     switch(op)
  1209.     {
  1210.         case MUL: return val1 * val2;
  1211.         case DIV:
  1212.                 if (val2 == 0.)
  1213.                 {
  1214.                         divzero = 1;
  1215. #ifdef EXTREMELYVERBOSE
  1216.                         fprintf(stderr, "Division by zero.\n");
  1217. #endif
  1218.                 }
  1219.                 return val2 == 0.? 0. : val1 / val2;
  1220.         case ADD: return val1 + val2;
  1221.         case SUB: return val1 - val2;
  1222.     }
  1223.     return 0.;
  1224. }
  1225.  
  1226.  
  1227.  
  1228. ==> arithmetic/digits/extreme.products.p <==
  1229. What are the extremal products of three three-digit numbers using digits 1-9?
  1230.  
  1231. ==> arithmetic/digits/extreme.products.s <==
  1232. There is a simple procedure which applies to these types of problems (and
  1233. which can be proven with help from the arithmetic-geometric inequality).
  1234.  
  1235. For the first part we use the "first large then equal" procedure.
  1236. This means that are three numbers will be 7**, 8**, and 9**.  Now
  1237. the digits 4,5,6 get distributed so as to make our three number as
  1238. close to each other as possible, i.e. 76*, 85*, 94*.  The same goes
  1239. for the remaining three digits, and we get 763, 852, 941.
  1240.  
  1241. For the second part we use the "first small then different" procedure.
  1242. Our three numbers will be of the form 1**, 2**, 3**.  We now place
  1243. the three digits so as to make our three numbers as unequal as possible;
  1244. this gives 14*, 25*, 36*.  Finishing, we get 147, 258, 369.
  1245.  
  1246. Now, *prove* that these procedures work for generalizations of this
  1247. problem.
  1248.  
  1249. ==> arithmetic/digits/labels.p <==
  1250. You have an arbitrary number of model kits (which you assemble for
  1251. fun and profit).  Each kit comes with twenty (20) stickers, two of which
  1252. are labeled "0", two are labeled "1", ..., two are labeled "9".
  1253. You decide to stick a serial number on each model you assemble starting
  1254. with one.  What is the first number you cannot stick.  You may stockpile
  1255. unused numbers on already assembled models, but you may not crack open
  1256. a new model to get at its stickers.  You complete assembling the current
  1257. model before starting the next.
  1258.  
  1259. ==> arithmetic/digits/labels.s <==
  1260. The method I used for this problem involved first coming up with a
  1261. formula that says how many times a digit has been used in all n models.
  1262.  
  1263. n = k*10^i + m for some k,m with 0 <k <10, m < 10^i
  1264. f(d,n) = (number of d's used getting to k*10^i from digits 0 to (i-1)) +
  1265.         (number of d's used by #'s 10^i to n from digit i) + f(d,m)
  1266. f(d,n) = i*k*10^(i-1) + (if (d < k) 10^i else if (d == k) m+1 else 0) + f(d,m)
  1267.  
  1268. This doesn't count 0's, which should be ok as they are not used as often
  1269. as other digits.  From the formula, it is clear that f(1,n) is never
  1270. less than f(d,n) for 1<d<10.
  1271. So I just calculated f(1,n) for various n (with some help from bc).
  1272.  
  1273. I quickly discovered that for n = 2*10^15, f(1,n) = 2*n.  After further
  1274. trials I determined that for n = 1999919999999981, f(1,n) = 2*n + 1. 
  1275. This appears to be the smallest n with f(1,n) > 2*n.
  1276.  
  1277. ==> arithmetic/digits/least.significant/factorial.p <==
  1278. What is the least significant non-zero digit in the decimal expansion of n!?
  1279.  
  1280. ==> arithmetic/digits/least.significant/factorial.s <==
  1281. Reduce mod 10 the numbers 2..n and then cancel out the
  1282. required factors of 10. The final step then involves
  1283. computing 2^i*3^j*7^k mod 10 for suitable i,j and k. 
  1284.  
  1285. A small program that performs this calculation is appended. Like the
  1286. other solutions, it takes O(log n) arithmetic operations.
  1287.  
  1288. -kym
  1289. ===
  1290.  
  1291. #include<stdio.h>
  1292. #include<assert.h>
  1293.  
  1294. int     p[6][4]={
  1295.         /*2*/   2,      4,      8,      6,
  1296.         /*3*/   3,      9,      7,      1,
  1297.         /*4*/   4,      6,      4,      6,
  1298.         /*5*/   5,      5,      5,      5,
  1299.         /*6*/   6,      6,      6,      6,
  1300.         /*7*/   7,      9,      3,      1,
  1301.         };
  1302.  
  1303. main(){
  1304.         int     i;
  1305.         int n;
  1306.  
  1307.         for(n=2;n<1000;n++){
  1308.                 i=lsdfact(n);
  1309.                 printf("%d\n",i);
  1310.                 }
  1311.  
  1312.         exit(0);
  1313.         }
  1314.  
  1315. lsdfact(n){
  1316.         int     a[10];
  1317.         int     i;
  1318.         int     n5;
  1319.         int     tmp;
  1320.  
  1321.         for(i=0;i<=9;i++)a[i]=alpha(i,n);
  1322.  
  1323.         n5=0;
  1324. /* NOTE: order is important in following */
  1325. l5:;
  1326.         while(tmp=a[5]){        /* cancel factors of 5 */
  1327.                 n5+=tmp;
  1328.                 a[1]+=(tmp+4)/5;
  1329.                 a[3]+=(tmp+3)/5;
  1330.                 a[5]=(tmp+2)/5;
  1331.                 a[7]+=(tmp+1)/5;
  1332.                 a[9]+=(tmp+0)/5;
  1333.                 }
  1334. l10:;
  1335.         if(tmp=a[0]){
  1336.                 a[0]=0; /* cancel all factors of 10 */
  1337.                 for(i=0;i<=9;i++)a[i]+=alpha(i,tmp);
  1338.                 }
  1339.         if(a[5]) goto l5;
  1340.         if(a[0]) goto l10;
  1341.  
  1342. /* n5 == number of 5's cancelled; 
  1343.    must now cancel same number of factors of 2 */
  1344.         i=ipow(2,a[2]+2*a[4]+a[6]+3*a[8]-n5)*
  1345.                 ipow(3,a[3]+a[6]+2*a[9])*
  1346.                 ipow(7,a[7]);
  1347.         assert(i%10);   /* must not be zero */
  1348.         return  i%10;
  1349.         }
  1350.  
  1351. alpha(d,n){
  1352. /* number of decimal numbers in [1,n] ending in digit d */
  1353.         int tmp;
  1354.         tmp=(n+10-d)/10;
  1355.         if(d==0)tmp--;  /* forget 0 */
  1356.         return tmp;
  1357.         }
  1358.  
  1359. ipow(x,y){
  1360. /* x^y mod 10 */
  1361.         if(y==0) return 1;
  1362.         if(y==1) return x;
  1363.         return p[x-2][(y-1)%4];
  1364.         }
  1365.  
  1366.  
  1367.  
  1368.  
  1369. ==> arithmetic/digits/least.significant/tower.of.power.p <==
  1370. What are the least significant digits of 9^(8^(7^(6^(5^(4^(3^(2^1))))))) ?
  1371.  
  1372. ==> arithmetic/digits/least.significant/tower.of.power.s <==
  1373. 9^11 = 9 (mod 100), so we need to find 8^...^1 (mod 10).
  1374. 8^5 = 8 (mod 10), so we need to find 7^...^1 (mod 4).
  1375. 7^3 = 7 (mod 4), so we need to find 6^...^1 (mod 2), but
  1376. this is clearly 0, so 7^...^1 = 1 (mod 4) ==>
  1377. 8^...^1 = 8 (mod 10) ==> 9^...^1 = 9^8 (mod 100) = 21 (mod 100).
  1378.  
  1379. ==> arithmetic/digits/most.significant/googol.p <==
  1380. What digits does googol! start with?
  1381.  
  1382. ==> arithmetic/digits/most.significant/googol.s <==
  1383. I'm not sure how to calculate the first googol of digits of log10(e), but
  1384. here's the first 150(approximately) of them...
  1385.  
  1386. 0.43429448190325182765112891891660508229439700580366656611445378316586464920
  1387. 8870774729224949338431748318706106744766303733641679287158963906569221064663
  1388.  
  1389. We need to deal with the digits immediately after the decimal point in
  1390. googol*log10(e), which are  .187061
  1391.  
  1392. frac[log(googol!)] = frac[halflog2pi + 50 + googol(100-log10(e))]
  1393.  = frac{halflog2pi + frac[googol(100-log10(e))]}
  1394.  = frac[.399090 + (1- .187061)]
  1395.  = .212029
  1396.  
  1397. 10 ** .212029 = 1.629405
  1398.  
  1399. Which means that googol! starts with 1629
  1400.  
  1401. ==> arithmetic/digits/most.significant/powers.p <==
  1402. What is the probability that 2^N begins with the digits 603245?
  1403.  
  1404. ==> arithmetic/digits/most.significant/powers.s <==
  1405. 2^N begins with 603245 iff 603246*10^m > 2^N >= 603245*10^m for some
  1406. positive integer m ==> m+log(603246) > N*log(2) >= m+log(603245);
  1407. so 2^N begins with 603245 iff frac(log(603246)) > frac(N*log(2))
  1408. >= frac(log(603245)).  If we are using natural density then N*log(2)
  1409. is uniformly distributed mod 1 since log(2) is irrational, hence the
  1410. probability is frac(log(603246)) - frac(log(603245)) =
  1411. frac(log(603246)-log(603245)) = frac(log(603246/603245)).
  1412.  
  1413. A neat observation is that since it is known p_n*c, where p_n is the
  1414. nth prime and c is irrational, is uniformly distributed mod 1, we get
  1415. the same answer if we replace 2^N with 2^{p_n}.
  1416. -- 
  1417. Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618
  1418.  
  1419. ==> arithmetic/digits/nine.digits.p <==
  1420. Form a number using 0-9 once with its first n digits divisible by n.
  1421.  
  1422. ==> arithmetic/digits/nine.digits.s <==
  1423. First, reduce the sample set. For each digit of ABCDEFGHI, such that the last
  1424. digit, (current digit), is the same as a multiple of N :
  1425.  
  1426. A: Any number 1-9
  1427. B: Even numbers 2,4,6,8 (divisible by 2).
  1428. C: Any number 1-9 (21,12,3,24,15,6,27,18,9).
  1429. D: Even numbers 2,4,6,8 (divisible by 4, every other even).
  1430. E: 5 (divisible by 5 and 0 not allowed).
  1431. F: Even numbers (12,24,6,18)
  1432. G: Any number 1-9 (21,42,63,14,35,56,7,28,49).
  1433. H: Even numbers (32,24,16,8)
  1434. I: Any number 1-9 (81,72,63,54,45,36,27,18,9)
  1435.  
  1436. Since E must be 5, I can eliminate it everywhere else.
  1437. Since I will use up all the even digits, (2,4,6,8) filling in those spots
  1438.    that must be even. Any number becomes all odds, except 5.
  1439.  
  1440. A: 1,3,7,9
  1441. B: 2,4,6,8
  1442. C: 1,3,7,9
  1443. D: 2,4,6,8
  1444. E: 5
  1445. F: 2,4,6,8
  1446. G: 1,3,7,9
  1447. H: 2,4,6,8
  1448. I: 1,3,7,9
  1449.  
  1450. We have that 2C+D=0 (mod 4), and since C is odd,
  1451. this implies that D is 2 or 6; similarly we find that H is 2 or 6 ==>
  1452. {B,F} = {4,8}.  D+5+F=0 (mod 3) ==> if D=2 then F=8, if D=6 then F=4.
  1453.  
  1454. We have two cases.
  1455.  
  1456. Assume our number is of the form A4C258G6I0.  Now the case n=8 ==>
  1457. G=1,9; case n=3 ==> A+1+C=0 (mod 3) ==> {A,C}={1,7} ==> G=9, I=3.
  1458. The two numbers remaining fail for n=7.
  1459.  
  1460. Assume our number is of the form A8C654G2I0.  The case n=8 ==> G=3,7.
  1461. If G=3, we need to check to see which of 1896543, 9816543, 7896543, 
  1462. and 9876543 are divisible by 7; none are.
  1463.  
  1464. If G=7, we need to check to see which of 1896547, 9816547, 1836547,
  1465. and 3816547 are divisible by 7; only the last one is, which yields
  1466. the solution 3816547290.
  1467.  
  1468. ==> arithmetic/digits/palindrome.p <==
  1469. Does the series formed by adding a number to its reversal always end in
  1470. a palindrome?
  1471.  
  1472. ==> arithmetic/digits/palindrome.s <==
  1473. This is not known.
  1474.  
  1475. If you start with 196, after 9480000 iterations you get a 3924257-digit
  1476. non-palindromic number.  However, there is no known proof that you will
  1477. never get a palindrome.
  1478.  
  1479. The statement is provably false for binary numbers. Roland Sprague has
  1480. shown that 10110 starts a series that never goes palindromic.
  1481.  
  1482. ==> arithmetic/digits/palintiples.p <==
  1483. Find all numbers that are multiples of their reversals.
  1484.  
  1485. ==> arithmetic/digits/palintiples.s <==
  1486. We are asked to find numbers that are integer multiples of their
  1487. reversals, which I call palintiples.  Of course, all the palindromic
  1488. numbers are a trivial example, but if we disregard the unit multiples,
  1489. the field is narrowed considerably.
  1490.  
  1491. Rouse Ball (_Mathematical_recreations_and_essays_) originated the
  1492. problem, and G. H. Hardy (_A_mathematician's_apology_) used the result
  1493. that 9801 and 8712 are the only four-digit palintiples as an example
  1494. of a theorem that is not ``serious''.  Martin Beech (_The_mathema-
  1495. tical_gazette_, Vol 74, #467, pp 50-51, March '90) observed that
  1496. 989*01 and 879*12 are palintiples, an observation he ``confirmed'' on
  1497. a hand calculator, and conjectured that these are all that exist.
  1498.  
  1499. I confirm that Beech's numbers are palintiples, I will show that they
  1500. are not all of the palintiples.  I will show that the palintiples do
  1501. not form a regular language.  And then I will prove that I have found
  1502. all the palintiples, by describing the them with a generalized form
  1503. of regular expression.  The results become more interesting in other
  1504. bases.
  1505.  
  1506. First, I have a more reasonable method of confirming that these
  1507. numbers are palintiples:
  1508.  
  1509.     Proof:  First, letting "9*" and "0*" refer an arbitrary string of
  1510.     nines and a string of zeroes of the same length, I note that
  1511.  
  1512.         879*12 = 879*00 + 12 = (880*00 - 100) + 12 = 880*00 - 88
  1513.         219*78 = 219*00 + 78 = (220*00 - 100) + 78 = 220*00 - 22
  1514.  
  1515.         989*01 = 989*00 +  1 = (990*00 - 100) +  1 = 990*00 - 99
  1516.         109*89 = 109*00 + 89 = (110*00 - 100) + 89 = 110*00 - 11
  1517.  
  1518.     It is obvious that 4x(220*00 - 22) = 880*00 - 88 and that
  1519.     9x(110*00 - 11) = 990*00 - 99.  QED.
  1520.  
  1521. Now, to show that these palintiples are not all that exist, let us
  1522. take the (infinite) language L[4] = (879*12 + 0*), and let Pal(L[4])
  1523. refer to the set of palindromes over the alphabet L[4].  It is
  1524. immediate that the numbers in Pal(L[4]) are palintiples.  For
  1525. instance,
  1526.  
  1527.           8712 000 87912 879999912 879999912 87912 000 8712
  1528.     = 4 x 2178 000 21978 219999978 219999978 21978 000 2178
  1529.  
  1530. (where I have inserted spaces to enhance readability) is a palintiple.
  1531. Similarly, taking L[9] = (989*01 + 0*), the numbers in Pal(L[9]) are
  1532. palintiples.  We exclude numbers starting with zeroes.
  1533.  
  1534. The reason these do not form a regular language is that the
  1535. sub-palintiples on the left end of the number must be the same (in
  1536. reverse order) as the sub-palintiples on the right end of the number:
  1537.  
  1538.          8712 8712 87999912 = 4 x 2178 2178 21999978
  1539.  
  1540. is not a palintiple, because 8712 8712 87999912 is not the reverse of
  1541. 2178 2178 21999978.  The pumping lemma can be used to prove that
  1542. Pal(L[4])+Pal(L[9]) is not a regular language, just as in the familiar
  1543. proof that the palindromes over a non-singleton alphabet do not form a
  1544. regular language.
  1545.  
  1546. Now to characterize all the palintiples, let N be a palintiple,
  1547. N=CxR(N), where R(.) signifies reversal, and C>1 is an integer.  (I
  1548. use "x" for multiplication, to avoid confusion with the Kleene star
  1549. "*", which signifies the concatenated closure.)  If D is a digit of N,
  1550. let D' refer to the corresponding digit of R(N).  Since N=CxR(N),
  1551. D+10T = CxD'+S, where S is the carry in to the position occupied by D'
  1552. when R(N) is multiplied by C, and T is the carry out of that position.
  1553. Similarly, D'+10T'=CxD+S', where S', T' are carries in and out of the
  1554. position occupied by D when R(N) is multiplied by C.
  1555.  
  1556. Since D and D' are so closely related, I will use the symbol D:D' to
  1557. refer to a digit D on the left side of a string with a corresponding
  1558. digit D' on the right side of the string.  More formally, an
  1559. expression "x[1]:y[1] x[2]:y[2] ... x[n]:y[n] w" will refer to a
  1560. string "x[1] x[2] ... x[n] w y[n] ... y[2] y[1]", where the x[i] and
  1561. y[i] are digits and w is a string of zero or one digits.  So 989901
  1562. may be written as 9:1 8:0 9:9 and 87912 may be written as 8:2 7:1 9.
  1563. Thus Pal(L[4])+Pal(L[9]) (omitting numbers with leading zeroes) can be
  1564. represented as
  1565.  
  1566.             (8:2 7:1 9:9* 1:7 2:8 0:0*)*
  1567.               (0:0* + 0 + 8:2 7:1 ( 9:9* + 9:9* 9))
  1568.           + (9:1 8:0 9:9* 0:8 1:9 0:0*)*
  1569.               (0:0* + 0 + 9:1 8:0 ( 9:9* + 9:9* 9)).      (1)
  1570.  
  1571. For each pair of digits D:D', there are a very limited--and often
  1572. empty--set of quadruples S,T,S',T' of digits that satisfy the
  1573. equations
  1574.  
  1575.                     D +10T =CxD'+S
  1576.                     D'+10T'=CxD +S',                      (2)
  1577.  
  1578. yet such a quadruple must exist for "D:D'" to appear in a palintiple
  1579. with multiplier C.  Furthermore, the S and T' of one D:D' must be T
  1580. and S', respectively, of the next pair of digits that appear.  This
  1581. enables us to construct a finite state machine to recognize those
  1582. palintiples.  The states [X#Y] refer to a pair of carries in D and D',
  1583. and we allow a transition from state [T#S'] to state [S#T'] on input
  1584. symbol D:D' exactly when equations (2) are satisfied.  Special
  1585. transitions for a single-digit input symbol (the central digit of
  1586. odd-length palintiples) and the criteria for the initial and the
  1587. accepting states are left as exercises.  The finite state machines
  1588. thus formed are
  1589.  
  1590.    State         Symbol  New     Symbol  New      Symbol   New
  1591.         Accept?         State           State             State
  1592.  
  1593. --> [0#0]  Y       8:2  [0#3]      0:0  [0#0]         0   [A]
  1594.     [0#3]  N       7:1  [3#3]
  1595.     [3#3]  Y       1:7  [3#0]      9:9  [3#3]         9   [A]
  1596.     [3#0]  N       2:8  [0#0]
  1597.      [A]   Y
  1598.  
  1599. for constant C=4, and
  1600.  
  1601.    State         Symbol  New     Symbol  New      Symbol   New
  1602.         Accept?         State           State             State
  1603.  
  1604. --> [0#0]  Y       1:9  [0#8]      0:0  [0#0]         0   [A]
  1605.     [0#8]  N       8:0  [8#8]
  1606.     [8#8]  Y       0:8  [8#0]      9:9  [8#8]         9   [A]
  1607.     [8#0]  N       9:1  [0#0]
  1608.      [A]   Y
  1609.  
  1610. for constant C=9, and the finite state machines for other constants
  1611. accept only strings of zeroes.  It is not hard to verify that the
  1612. proposed regular expression (1) represents the union of the languages
  1613. accepted by these machines, omitting the empty string and strings
  1614. beginning with zero.
  1615.  
  1616. I have written a computer program that constructs finite state
  1617. machines for recognizing palintiples for various bases and constants.
  1618. I found that base 10 is actually an unusually boring base for this
  1619. problem.  For instance, the machine for base 8, constant C=5 is
  1620.  
  1621.    State         Symbol  New     Symbol  New      Symbol  New
  1622.         Accept?         State           State            State
  1623.  
  1624. --> [0#0]  Y       0:0  [0#0]      5:1  [0#3]         0  [A]
  1625.     [0#3]  N       1:0  [1#1]      6:1  [1#4]
  1626.     [1#1]  Y       0:1  [3#0]      5:2  [3#3]
  1627.     [3#0]  N       1:5  [0#0]      6:6  [0#3]         6  [A]
  1628.     [3#3]  Y       2:5  [1#1]      7:6  [1#4]
  1629.     [1#4]  N       1:1  [4#1]      6:2  [4#4]         1  [A]
  1630.     [4#4]  Y       2:6  [4#1]      7:7  [4#4]         7  [A]
  1631.     [4#1]  N       1:6  [3#0]      6:7  [3#3]
  1632.      [A]   Y
  1633.  
  1634. for which I invite masochists to write the regular expression.  If
  1635. anyone wants more, I should remark that the base 29 machine for
  1636. constant C=18 has 71 states!
  1637.  
  1638. By the way, I did not find any way of predicting the size or form of
  1639. the machines for the various bases, except that the machines for C=B-1
  1640. all seem to be isomorphic to each other.  If anyone investigates the
  1641. general behavior, I would be most happy to hear about it.
  1642.  
  1643. Dan Hoey
  1644. Hoey@AIC.NRL.Navy.Mil
  1645. May, 1992
  1646. [ A preliminary version of this message appeared in April, 1991. ]
  1647. ================================================================
  1648. Dan
  1649.  
  1650.  
  1651.  
  1652. ==> arithmetic/digits/power.two.p <==
  1653. Prove that for any 9-digit number (base 10) there is an integral power
  1654. of 2 whose first 9 digits are that number.
  1655.  
  1656. ==> arithmetic/digits/power.two.s <==
  1657. Let v = log to base 10 of 2.
  1658. Then v is irrational.
  1659.  
  1660. Let w = log to base 10 of these 9 digits.
  1661.  
  1662. Since v is irrational, given epsilon > 0, there exists some natural number 
  1663. n such that
  1664.  
  1665.    {w} < {nv} < {w} + epsilon
  1666.  
  1667. ({x} is the fractional part of x.)  Let us pick n for when 
  1668.  
  1669.    epsilon = log 1.00000000000000000000001.
  1670.  
  1671. Then 2^n does the job.
  1672.  
  1673. ==> arithmetic/digits/prime/101.p <==
  1674. How many primes are in the sequence 101, 10101, 1010101, ...?
  1675.  
  1676. ==> arithmetic/digits/prime/101.s <==
  1677. Note that the sequence
  1678. 101 , 10101, 1010101, ....
  1679. can be viewed as 
  1680. 100**1 +1, 100**2 + 100**1 + 1, 100**3 + 100**2 + 100**1 +1 ....
  1681. that is, 
  1682. the k-th term in the sequence is 
  1683. 100**k + 100**(k-1) + 100**(k-2) + ...+ 100**(1) + 1
  1684. = (100)**(k+1) - 1
  1685.   ----------------
  1686.     11 * 9
  1687. = (10)**(2k+2) - 1
  1688.   ----------------
  1689.     11 * 9
  1690. = ((10)**(k+1) - 1)*((10)**(k+1) +1)
  1691.    ---------------------------------
  1692.        11*9
  1693. thus either 11 and 9 divide the numerator. Either they both divide the
  1694. same factor in the numerator or different factors in the numerator. In
  1695. any case, after dividing, they leave the numerators as a product of two
  1696. integers.  Only in the case of k = 1, one of the integers is 1. Thus
  1697. there is exactly one prime in the above sequence: 101.
  1698.  
  1699. ==> arithmetic/digits/prime/all.prefix.p <==
  1700. What is the longest prime whose every proper prefix is a prime?
  1701.  
  1702. ==> arithmetic/digits/prime/all.prefix.s <==
  1703. 23399339, 29399999, 37337999, 59393339, 73939133
  1704.  
  1705. ==> arithmetic/digits/prime/change.one.p <==
  1706. What is the smallest number that cannot be made prime by changing a single
  1707. digit?  Are there infinitely many such numbers?
  1708.  
  1709. ==> arithmetic/digits/prime/change.one.s <==
  1710. 200.  Obviously, you would have to change the last digit, but 201, 203,
  1711. 207, and 209 are all composite.  For any smaller number, you can change
  1712. the last digit, and get
  1713. 2,11,23,31,41,53,61,71,83,97,101,113,127,131,149,151,163,173,181, or 191.
  1714.  
  1715. 200+2310n gives an infinite family, because changing the last
  1716. digit to 1 or 7 gives a number divisible by 3; to 3, a number divisible
  1717. by 7; to 9, a number divisible by 11.
  1718.  
  1719. ==> arithmetic/digits/prime/prefix.one.p <==
  1720. 2 is prime, but 12, 22, ..., 92 are not.  Similarly, 5 is prime
  1721. whereas 15, 25, ..., 95 are not.  What is the next prime number
  1722. which is composite when any digit is prefixed?
  1723.  
  1724. ==> arithmetic/digits/prime/prefix.one.s <==
  1725. 149
  1726.  
  1727. ==> arithmetic/digits/reverse.p <==
  1728. Is there an integer that has its digits reversed after dividing it by 2?
  1729.  
  1730. ==> arithmetic/digits/reverse.s <==
  1731. Assume there's such a positive integer x such that x/2=y and y is the
  1732. reverse of x.
  1733.  
  1734. Then x=2y.  Let x = a...b, then y = b...a, and:
  1735.  
  1736.                  b...a   (y)
  1737.                x     2
  1738.                --------
  1739.                  a...b   (x)
  1740.  
  1741. From the last digit b of x, we have b = 2a (mod 10), the possible
  1742. values for b are 2, 4, 6, 8 and hence possible values for (a, b) are
  1743. (1,2), (6,2), (2,4), (7,4), (3,6), (8,6), (4,8), (9,8).
  1744.  
  1745. From the first digit a of x, we have a = 2b or a = 2b+1.  None of the
  1746. above pairs satisfy this condition.  A contradiction.
  1747.  
  1748. Hence there's no such integer.
  1749.  
  1750. ==> arithmetic/digits/rotate.p <==
  1751. Find integers where multiplying them by single digits rotates their digits
  1752. one position, so that the last digit become the first digit.
  1753.  
  1754. ==> arithmetic/digits/rotate.s <==
  1755. 2 105263157894736842
  1756. 3 1034482758620689655172413793
  1757. 4 102564 153846 179487 205128 230769
  1758. 5 142857 102040816326530612244897959183673469387755
  1759. 6 1016949152542372881355932203389830508474576271186440677966
  1760.   1186440677966101694915254237288135593220338983050847457627
  1761.   1355932203389830508474576271186440677966101694915254237288
  1762.   1525423728813559322033898305084745762711864406779661016949
  1763. 7 1014492753623188405797 1159420289855072463768 1304347826086956521739
  1764. 8 1012658227848 1139240506329
  1765. 9 10112359550561797752808988764044943820224719
  1766.  
  1767. In base B, suppose you have an N-digit answer A whose digits are
  1768. rotated when multiplied by K.  If D is the low-order digit of A, we
  1769. have
  1770.  
  1771.     (A-D)/B + D B^(N-1) = K A .
  1772.  
  1773. Solving this for A we have
  1774.  
  1775.         D (B^N - 1)
  1776.     A = ----------- .
  1777.           B K - 1
  1778.  
  1779. In order for A >= B^(N-1) we must have D >= K.  Now we have to find N
  1780. such that B^N-1 is divisible by R=(BK-1)/gcd(BK-1,D).  This always has
  1781. a minimal solution N0(R,B)<R, and the set of all solutions is the set
  1782. of multiples of N0(R,B).  N0(R,B) is the length of the repeating part
  1783. of the fraction 1/R in base B.
  1784.  
  1785. N0(ST,B)=N0(S,B)N0(T,B) when (S,T)=1, and for prime powers, N0(P^X,B)
  1786. divides (P-1)P^(X-1). Determining which divisor is a little more
  1787. complicated but well-known (cf. Hardy & Wright).
  1788.  
  1789. So given B and K, there is one minimal solution for each
  1790. D=K,K+1,...,B-1, and you get all the solutions by taking repetitions
  1791. of the minimal solutions.
  1792.  
  1793. ==> arithmetic/digits/sesqui.p <==
  1794. Find the least number where moving the first digit to the end multiplies by 1.5
  1795. .
  1796.  
  1797. ==> arithmetic/digits/sesqui.s <==
  1798. Let's represent this number as  a*10^n+b,  where 1<=a<=9 and
  1799. b < 10^n.  Then the condition to be satisfied is:
  1800.  
  1801. 3/2(a*10^n+b) = 10b+a
  1802.  
  1803.   3(a*10^n+b) = 20b+2a
  1804.  
  1805.    3a*10^n+3b = 20b+2a
  1806.  
  1807.   (3*10^n-2)a = 17b
  1808.  
  1809.             b = a*(3*10^n-2)/17
  1810.  
  1811. So we must have 3*10^n-2 = 0 (mod 17) (since a is less than 10, it
  1812. cannot contribute the needed prime 17 to the factorization of 17b).
  1813. (Also, assuming large n, we must have a at most 5 so that b < 10^n will
  1814. be satisfied, but note that we can choose a=1).  Now,
  1815.  
  1816. 3*10^n-2 = 0 (mod 17)
  1817.  
  1818. 3*10^n = 2 (mod 17)
  1819.  
  1820. 10^n = 12 (mod 17)
  1821.  
  1822. A quick check shows that the smallest n which satisfies this is 15
  1823. (the fact that one exists was assured to us because 17 is prime).  So,
  1824. setting n=15 and a=1 (obviously) gives us b=176470588235294, so the
  1825. number we are looking for is
  1826.  
  1827.                         1176470588235294
  1828.  
  1829. and, by the way, we can set a=2 to give us the second smallest such
  1830. number,
  1831.                         2352941176470588
  1832.  
  1833. Other things we can infer about these numbers is that there are 5 of
  1834. them less than 10^16, 5 more less than 10^33, etc.
  1835.  
  1836. ==> arithmetic/digits/squares/change.leading.p <==
  1837. What squares remain squares when their leading digits are incremented?
  1838.  
  1839. ==> arithmetic/digits/squares/change.leading.s <==
  1840. Omitting solutions that are obtained from smaller solutions by
  1841. multiplying by powers of 10, the squares of these numbers satisfy the
  1842. condition:
  1843.  
  1844. 1. (105,145), (3375,4625), (14025,17225), (326625,454625),
  1845.     (10846875,14753125), (43708125,53948125), ...
  1846.  
  1847. 2. (45,55), (144375,175625), (463171875,560828125), ...
  1848.  
  1849. 7. (2824483699753370361328125,2996282391593370361328125), ...
  1850.  
  1851. Here is how to find them. We have (y+x)*(y-x) = 10^n, and so we must have 
  1852. {y+x, y-x} as {5^m*10^a, 2^m*10^b} in some order. It is also necessary (and
  1853. sufficient) that y/x lies in the interval [sqrt(3/2),sqrt(2)], or equivalently
  1854. that (y+x)/(y-x) lies in [3+sqrt(8),5+sqrt(24)] = [5.82842...,9.89897...].
  1855. Thus we need to make (5/2)^m*10^(a-b), or its reciprocal, in this range.
  1856. For each m there is clearly at most one power of 10 that will do. m=2,a=b
  1857. gives (105,145); m=3,b=a+2 gives (3375,4625), and so on.
  1858.  
  1859. There are infinitely many non-equivalent solutions, because log(5/2) / log(10)
  1860. is irrational.
  1861.  
  1862. One can use exactly the same argument to find squares whose initial 2 can 
  1863. be replaced by a 3, of course, except that the range of (y+x)/(y-x) changes.
  1864.  
  1865. ==> arithmetic/digits/squares/length.22.p <==
  1866. Is it possible to form two numbers A and B from 22 digits such that
  1867. A = B^2?  Of course, leading digits must be non-zero.
  1868.  
  1869. ==> arithmetic/digits/squares/length.22.s <==
  1870. No, the number of digits of A^2 must be of the form 3n or 3n-1.
  1871.  
  1872. ==> arithmetic/digits/squares/length.9.p <==
  1873. Is it possible to make a number and its square, using the digits from 1
  1874. through 9 exactly once?
  1875.  
  1876. ==> arithmetic/digits/squares/length.9.s <==
  1877. Yes, there are two such pairs: (567, 567^2=321489) and (854,854^2=729316).
  1878.  
  1879. Archive-name: puzzles/archive/arithmetic/part2
  1880. Last-modified: 17 Aug 1993
  1881. Version: 4
  1882.  
  1883.  
  1884. ==> arithmetic/digits/squares/three.digits.p <==
  1885. What squares consist entirely of three digits (e.g., 1, 4, and 9)?
  1886.  
  1887. ==> arithmetic/digits/squares/three.digits.s <==
  1888. The full set of solutions up to 10**12 is
  1889.               1 ->                            1
  1890.               2 ->                            4
  1891.               3 ->                            9
  1892.               7 ->                           49
  1893.              12 ->                          144
  1894.              21 ->                          441
  1895.              38 ->                         1444
  1896.             107 ->                        11449
  1897.             212 ->                        44944
  1898.           31488 ->                   9914 94144
  1899.           70107 ->                  49149 91449
  1900.         3 87288 ->               14 99919 94944
  1901.       956 10729 ->          9 14141 14499 11441
  1902.      4466 53271 ->        199 49914 44949 99441
  1903.     31487 17107 ->       9914 41941 99144 49449
  1904.   2 10810 79479 ->    4 44411 91199 99149 11441
  1905.  
  1906. If the algorithm is used in the form I presented it before, generating
  1907. the whole set P_n before starting on P_{n+1}, the store requirements
  1908. begin to become embarassing. For n>8 I switched to a depth-first
  1909. strategy, generating all the elements in P_i (i=9..12) congruent to
  1910. a particular x in P_8 for each x in turn. This means the solutions
  1911. don't come out in any particular order, of course. CPU time was 16.2
  1912. seconds (IBM 3084).
  1913.  
  1914. In article <1990Feb6.025205.28153@sun.soe.clarkson.edu>, Steven
  1915. Stadnicki suggests alternate triples of digits, in particular {1,4,6}
  1916. (with many solutions) and {2,4,8} (with few). I ran my program on
  1917. these as well, up to 10**12 again:
  1918.               1 ->                            1
  1919.               2 ->                            4
  1920.               4 ->                           16
  1921.               8 ->                           64
  1922.              12 ->                          144
  1923.              21 ->                          441
  1924.              38 ->                         1444
  1925.             108 ->                        11664
  1926.             119 ->                        14161
  1927.             121 ->                        14641
  1928.             129 ->                        16641
  1929.             204 ->                        41616
  1930.             408 ->                      1 66464
  1931.             804 ->                      6 46416
  1932.            2538 ->                     64 41444
  1933.            3408 ->                    116 14464
  1934.            6642 ->                    441 16164
  1935.           12908 ->                   1666 16464
  1936.           25771 ->                   6641 44441
  1937.           78196 ->                  61146 14416
  1938.           81619 ->                  66616 61161
  1939.         3 33858 ->               11 14611 64164
  1940.      2040 00408 ->         41 61616 64641 66464
  1941.      6681 64962 ->        446 44441 64444 61444
  1942.      8131 18358 ->        661 16146 41166 16164
  1943.     40182 85038 ->      16146 61464 66146 61444  (Steven's last soln.)
  1944.   1 20068 50738 ->    1 44164 46464 46111 44644
  1945.   1 26941 38988 ->    1 61141 16464 66616 64144
  1946.   1 27069 43631 ->    1 61466 41644 14114 64161
  1947.   4 01822 24262 ->   16 14611 14664 16614 44644
  1948.   4 05784 63021 ->   16 46611 66114 66644 46441
  1949.  78 51539 12392 -> 6164 66666 14446 44111 61664
  1950. and
  1951.               2 ->                            4
  1952.              22 ->                          484
  1953.             168 ->                        28224
  1954.             478 ->                      2 28484
  1955.            2878 ->                     82 82884 (Steven's last soln.)
  1956.      2109 12978 ->         44 48428 42888 28484
  1957. (so the answer to Steven's "Are there any more at all?" is "Yes".)
  1958.  
  1959. The CPU times were 42.9 seconds for {1,4,6}, 18.7 for {2,4,8}. This
  1960. corresponds to an interesting point: the abundance of solutions for
  1961. {1,4,6} is associated with abnormally large sets P_n (|P_8| = 16088
  1962. for {1,4,6} compared to |P_8| = 5904 for {1,4,9}) but the deficiency
  1963. of solutions for {2,4,8} is *not* associated with small P_n's (|P_8|
  1964. = 6816 for {2,4,8}). Can anyone wave a hand convincingly to explain
  1965. why the solutions for {2,4,8} are so sparse?
  1966.  
  1967. I suspect we are now getting to the point where an improved algorithm
  1968. is called for. The time to determine all the n-digit solutions (i.e.
  1969. 2n-digit squares) using this last-significant-digit-first is essentially
  1970. constant * 3**n. Dean Hickerson in <90036.134503HUL@PSUVM.BITNET>, and
  1971. Ilan Vardi in <1990Feb5.214249.22811@Neon.Stanford.EDU>, suggest using
  1972. a most-significant-digit-first strategy, based on the fact that the
  1973. first n digits of the square determine the (integral) square root; this
  1974. also has a running time constant * 3**n. Can one attack both ends at
  1975. once and do better?
  1976.  
  1977. Chris Thompson
  1978. JANET:    cet1@uk.ac.cam.phx
  1979. Internet: cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk
  1980.  
  1981. Hey guys, what about
  1982.  
  1983. 648070211589107021 ^ 2 = 419994999149149944149149944191494441
  1984.  
  1985. This was found by David Applegate and myself (about 5 minutes on a DEC 3100,
  1986. program in C).
  1987.  
  1988. This is the largest square less than 10^42 with the 149-property; checking
  1989. took a bit more than an hour of CPU time.
  1990.  
  1991. As somebody suggested, we used a combined most-significant/least-significant
  1992. digits attack.  First we make a table of p-digit prefixes (most significant
  1993. p digits) that could begin a root whose square has the 149 property in its
  1994. first p digits.  We organize this table into buckets by the least
  1995. significant q digits of the prefixes.  Then we enumerate the s digit
  1996. suffixes whose squares have the 149 property in their last s digits.  For
  1997. each such suffix, we look in the table for those prefixes whose last q
  1998. digits match the first q of the suffix.  For each match, we consider the p +
  1999. s - q digit number formed by overlapping the prefix and the suffix by q
  2000. digits.  The squares of these overlap numbers must contain all the squares
  2001. with the 149 property.
  2002.  
  2003. The time expended is O(3^p) to generate the prefix table, O(3^s) to
  2004. enumerate the suffixes, and O(3^(p+s) / 10^q) to check the overlaps (being
  2005. very rough and ignoring the polynomial factors) By judiciously chosing p, q,
  2006. and s, we can fix things so that each bucket of the table has around O(1)
  2007. entries: set q = p log10(3).  Setting p = s, we end up looking for squares
  2008. whose roots have n = 2 - log10(3) digits, with an algorithm that takes time
  2009. O( 3 ^ [n / (2 - log10(3)]) ), roughly time O(3^[.66n]).  Compared to the
  2010. O(3^n) performance of either single-ended algorithm, this lets us check 50%
  2011. more digits in the same amount of time (ignoring polynomial factors).  Of
  2012. course, the space cost of the combined-ends method is high.
  2013.  
  2014. -- Guy and Dave
  2015. -- 
  2016. Guy Jacobson                      School of Computer Science
  2017. Carnegie Mellon         arpanet : guy@cs.cmu.edu
  2018. Pittsburgh, PA  15213   csnet   : Guy.Jacobson%a.cs.cmu.edu@csnet-relay
  2019. (412) 268-3056          uucp    : ...!{seismo, ucbvax, harvard}!cs.cmu.edu!guy
  2020.  
  2021. Here is an algorithm which takes O(sqrt(n)log(n)) steps to find all perfect
  2022. squares < n whose only digits are 1, 4 and 9.
  2023.  
  2024. This doesn't sound too great *but* it doesn't use a lot of memory and only
  2025. requires addition and <.  Also, the actual run time will depend on where the
  2026. first non-{1,4,9} digit appears in each square.
  2027.  
  2028.         set n = 1
  2029.         set odd = 1
  2030.  
  2031.         while(n < MAXVAL)
  2032.         {
  2033.                 if(all digits of n are in {1,4,9})
  2034.                 {
  2035.                         print n
  2036.                 }
  2037.  
  2038.                 add 2 to odd
  2039.                 add odd to n
  2040.         }
  2041.  
  2042. This works because (X+1)^2 - x^2 = 2x+1.
  2043. That is, if you start with 0 and add successive odd
  2044. numbers to it you get 0+1=1, 1+3=4, 4+5=9, 9+7=16 etc.
  2045. I've started the algorithm at 1 for convenience.
  2046.  
  2047. The "O" value comes from looking at at most all digits
  2048. (log(n)) of all perfect squares < n (sqrt(n) of them)
  2049. at most a constant number of times. 
  2050.  
  2051. I didn't save the articles with algorithms claiming to be
  2052. O(3^log(n)) so I don't know if their calculations needed
  2053. to (or did) account for multiplication or sqrt() of large
  2054. numbers.  O(3^log(n)) sounds reasonable so I'm going to
  2055. assume they did unless I hear otherwise.
  2056.  
  2057. Any comments? Please email if you just want to refresh my memory
  2058. on the other algorithms.
  2059.  
  2060. Andrew Charles
  2061. acgd@ihuxy.ATT.COMM
  2062.  
  2063. ==> arithmetic/digits/squares/twin.p <==
  2064. Let a twin be a number formed by writing the same number twice,
  2065. for instance, 81708170 or 132132.  What is the smallest square twin?
  2066.  
  2067. ==> arithmetic/digits/squares/twin.s <==
  2068. 1322314049613223140496 = 36363636364 ^ 2.
  2069.  
  2070. The key to solving this puzzle is looking at the basic form of these
  2071. "twin" numbers, which is some number k = 1 + 10^n multiplied by some number
  2072. 10^(n-1) <= a < 10^n.  If ak is a perfect square, k must have some
  2073. repeated factor, since a<k. Searching the possible values of k for one
  2074. with a repeated factor eventually turns up the number 1 + 10^11 = 11^2
  2075. * 826446281.  So, we set a=826446281 and ak = 9090909091^2 =
  2076. 82644628100826446281, but this needs leading zeros to fit the pattern.
  2077. So, we multiply by a suitable small square (in this case 16) to get the
  2078. above answer.
  2079.  
  2080. ==> arithmetic/digits/sum.of.digits.p <==
  2081. Find sod ( sod ( sod (4444 ^ 4444 ) ) ).
  2082.  
  2083. ==> arithmetic/digits/sum.of.digits.s <==
  2084. let X = 4444^4444
  2085.  
  2086. sod(X) <= 9 * (# of digits) < 145900
  2087. sod(sod(X)) <= sod(99999) = 45
  2088. sod(sod(sod(X))) <= sod(39) = 12
  2089.  
  2090. but sod(sod(sod(X))) = 7 (mod 9)
  2091.  
  2092. thus sod(sod(sod(X))) = 7
  2093.  
  2094. ==> arithmetic/digits/zeros/million.p <==
  2095. How many zeros occur in the numbers from 1 to 1,000,000?
  2096.  
  2097. ==> arithmetic/digits/zeros/million.s <==
  2098. In the numbers from 10^(n-1) through 10^n - 1, there are 9 * 10^(n-1)
  2099. numbers of n digits each, so 9(n-1)10^(n-1) non-leading digits, of
  2100. which one tenth, or 9(n-1)10^(n-2), are zeroes.  When we change the
  2101. range to 10^(n-1) + 1 through 10^n, we remove 10^(n-1) and put in
  2102. 10^n, gaining one zero, so
  2103.  
  2104.     p(n) = p(n-1) + 9(n-1)10^(n-2) + 1 with p(1)=1.
  2105.  
  2106. Solving the recurrence yields the closed form
  2107.  
  2108.     p(n) = n(10^(n-1)+1) - (10^n-1)/9.
  2109.  
  2110. For n=6, there are 488,895 zeroes, 600,001 ones, and 600,000 of all other
  2111. digits.
  2112.  
  2113. ==> arithmetic/digits/zeros/trailing.p <==
  2114. How many trailing zeros are in the decimal expansion of n!?
  2115.  
  2116. ==> arithmetic/digits/zeros/trailing.s <==
  2117. The general answer to the question
  2118. "what power of p divides x!" where p is prime
  2119. is (x-d)/(p-1) where d is the sum of the digits of (x written in base p).
  2120.  
  2121. So where p=5, 10 is written as 20 and is divisible by 5^2 (2 = (10-2)/4);
  2122. x to base 10:     100    1000    10000    100000     1000000
  2123. x to base 5:      400   13000   310000  11200000   224000000
  2124. d          :        4       4        4         4           8
  2125. trailing 0s in x!  24     249     2499     24999      249998
  2126.  
  2127. ==> arithmetic/magic.squares.p <==
  2128. Are there large squares, containing only consecutive integers, all of whose
  2129. rows, columns and diagonals have the same sum?  How about cubes?
  2130.  
  2131. ==> arithmetic/magic.squares.s <==
  2132. These are called magic squares.  A magic square of order n (integers
  2133. from 1 to n*n) has only one possible sum: (n*n+1)*n/2.
  2134.  
  2135. Odd and even order squares must be constructed by different approaches.
  2136. For odd orders, the most common algorithm is a recursive scheme
  2137. devised by de la Loubere about 300 years ago.  For even orders, one
  2138. procedure is the Devedec algorithm, which treats even orders not
  2139. divisible by 4 slightly differently from those which are divisible by
  2140. 4 (doubly even).
  2141.  
  2142. For squares with odd-length sides, the following algorithm builds a magic
  2143. square:
  2144.  
  2145. Put 1 in the middle box in the upper row. From then on, if it's
  2146. possible to put the next number one box diagonally up and to the right
  2147. (wrapping around if the edge of the grid is reached), do so, otherwise,
  2148. put it directly below the last one.
  2149.  
  2150.                17 24  1  8 15
  2151.                23  5  7 14 16 
  2152.                 4  6 13 20 22
  2153.                10 12 19 21  3 
  2154.                11 18 25  2  9 
  2155.  
  2156. ...or even
  2157.  
  2158.          47 58 69 80  1 12 23 34 45
  2159.          57 68 79  9 11 22 33 44 46
  2160.          67 78  8 10 21 32 43 54 56
  2161.          77  7 18 20 31 42 53 55 66
  2162.           6 17 19 30 41 52 63 65 76
  2163.          16 27 29 40 51 62 64 75  5
  2164.          26 28 39 50 61 72 74  4 15
  2165.          36 38 49 60 71 73  3 14 25
  2166.          37 48 59 70 81  2 13 24 35
  2167.  
  2168. See archive entry knight.tour for magic squares that are knight's tours.
  2169.  
  2170. To get a 4x4 square, write the numbers in order across each row, filling
  2171. the square...
  2172.  
  2173. 1  2  3  4
  2174. 5  6  7  8
  2175. 9  10 11 12
  2176. 13 14 15 16
  2177.  
  2178. then use the following pattern as a mask:
  2179.  
  2180. .  X  X  .
  2181. X  .  .  X
  2182. X  .  .  X
  2183. .  X  X  .
  2184.  
  2185. Everywhere there is an X, complement the number (subtract it from
  2186. n*n+1).  For the 4x4 you get:
  2187.  
  2188. 1  15 14 4
  2189. 12 6  7  9
  2190. 8  10 11 5
  2191. 13 3  2  16
  2192.  
  2193. For n even (n>4):
  2194.  
  2195. Make an initial magic square by writing an n/2 magic square four times
  2196. (the same one each time).  Now, although this square adds up right we
  2197. have the numbers 1 to n*n/4 written four times each.  To fix this,
  2198. simply add to it n*n/4 times one of the following magic squares:
  2199.  
  2200. if n/2 is odd (example: n/2=7),
  2201.  
  2202. 3 3 3 0 0 0 0 2 2 2 2 2 1 1   (there are int(n/4) 3s, int(n/4-1) 1s on each
  2203. 3 3 3 0 0 0 0 2 2 2 2 2 1 1    row)
  2204. 3 3 3 0 0 0 0 2 2 2 2 2 1 1
  2205. 0 3 3 3 0 0 0 2 2 2 2 2 1 1   (this is row int(n/4)+1.  It starts with just
  2206. 3 3 3 0 0 0 0 2 2 2 2 2 1 1    the one 0)
  2207. 3 3 3 0 0 0 0 2 2 2 2 2 1 1
  2208. 3 3 3 0 0 0 0 2 2 2 2 2 1 1
  2209. 0 0 0 3 3 3 3 1 1 1 1 1 2 2   (the lower half is the same as the upper half
  2210. 0 0 0 3 3 3 3 1 1 1 1 1 2 2    with 3<->0 and 1<->2 swapped.  This guarantees
  2211. 0 0 0 3 3 3 3 1 1 1 1 1 2 2    that each number 1-n*n will appear in the
  2212. 3 0 0 0 3 3 3 1 1 1 1 1 2 2    completed square)
  2213. 0 0 0 3 3 3 3 1 1 1 1 1 2 2
  2214. 0 0 0 3 3 3 3 1 1 1 1 1 2 2
  2215. 0 0 0 3 3 3 3 1 1 1 1 1 2 2
  2216.  
  2217. if n/2 is even (example: n/2=4),
  2218.  
  2219. 0 0 3 3 2 2 1 1  (there are n/4 of each number on each row)
  2220. 0 0 3 3 2 2 1 1
  2221. 0 0 3 3 2 2 1 1
  2222. 0 0 3 3 2 2 1 1
  2223. 3 3 0 0 1 1 2 2
  2224. 3 3 0 0 1 1 2 2
  2225. 3 3 0 0 1 1 2 2
  2226. 3 3 0 0 1 1 2 2
  2227.  
  2228. ~References:
  2229.     "Magic Squares and Cubes"
  2230.     W.S. Andrews
  2231.     The Open Court Publishing Co.
  2232.     Chicago, 1908
  2233.  
  2234.     "Mathematical Recreations"
  2235.     M. Kraitchik
  2236.     Dover
  2237.     New York, 1953
  2238.  
  2239. ==> arithmetic/pell.p <==
  2240. Find integer solutions to x^2 - 92y^2 = 1.
  2241.  
  2242. ==> arithmetic/pell.s <==
  2243. x=1        y=0
  2244. x=1151     y=120
  2245. x=2649601  y=276240
  2246. etc.
  2247.  
  2248. Each successive solution is about 2300 times the previous
  2249. solution;  they are every 8th partial fraction (x=numerator,
  2250. y=denominator) of the continued fraction for sqrt(92) = 
  2251. [9,  1,1,2,4,2,1,1,18,  1,1,2,4,2,1,1,18,  1,1,2,4,2,1,1,18, ...]
  2252.  
  2253. Once you have the smallest positive solution (x1,y1) you
  2254. don't need to "search" for the rest.  You can obtain the nth positive
  2255. solution (xn,yn) by the formula
  2256.  
  2257. (x1 + y1 sqrt(92))^n = xn + yn sqrt(92).
  2258.  
  2259. See Niven & Zuckerman's An Introduction to the Theory of Numbers.
  2260. Look in the index under Pell's equation.
  2261.  
  2262. ==> arithmetic/subset.p <==
  2263. Prove that all sets of n integers contain a subset whose sum is divisible by n.
  2264.  
  2265. ==> arithmetic/subset.s <==
  2266. Consider the set of remainders of the partial sums a(1) + ... + a(i).
  2267. Since there are n such sums, either one has remainder zero (and we're
  2268. thru) or 2 coincide, say the i'th and j'th.  In this case, a(i+1) +
  2269. ... + a(j) is divisible by n.  (note this is a stronger result since
  2270. the subsequence constructed is of *adjacent* terms.)  Consider a(1)
  2271. (mod n), a(1)+a(2) (mod n), ..., a(1)+...+a(n) (mod n).  Either at
  2272. some point we have a(1)+...+a(m) = 0 (mod n) or else by the pigeonhole
  2273. principle some value (mod n) will have been duplicated.  We win either
  2274. way.
  2275.  
  2276. ==> arithmetic/sum.of.cubes.p <==
  2277. Find two fractions whose cubes total 6.
  2278.  
  2279. ==> arithmetic/sum.of.cubes.s <==
  2280. Restated:  
  2281. Find X, Y, minimum Z (all positive integers) where
  2282. (X/Z)^3 + (Y/Z)^3 = 6
  2283.  
  2284. Again, a generalized solution would be nice.
  2285.  
  2286. You are asking for the smallest z s.t. x^3 + y^3 = 6*z^3 and x,y,z in Z+.
  2287. In general, questions like these are extremely difficult; if you're
  2288. interested take a look at books covering Diophantine equations
  2289. (especially Baker's work on effective methods of computing solutions).
  2290.  
  2291. Dudeney mentions this problem in connection with #20 in _The Canterbury
  2292. Puzzles_; the smallest answer is (17/21)^3 + (37/21)^3 = 6.
  2293.  
  2294. For the interest of the readers of this group I'll quote:
  2295.  
  2296.    "Given a known case for the expression of a number as the sum or
  2297. difference of two cubes, we can, by formula, derive from it an infinite
  2298. number of other cases alternately positive and negative.  Thus Fermat,
  2299. starting from the known case 1^3 + 2^3 = 9 (which we will call a
  2300. fundamental case), first obtained a negative solution in bigger
  2301. figures, and from this his positive solution in bigger figures still.
  2302. But there is an infinite number of fundamentals, and I found by trial
  2303. a negative fundamental solution in smaller figures than his derived
  2304. negative solution, from which I obtained the result shown above.  That
  2305. is the simple explanation."
  2306.  
  2307. In the above paragraph Dudeney is explaining how he derived (*by hand*)
  2308. that (415280564497/348671682660)^3 + (676702467503/348671682660)^3 = 9.
  2309.  
  2310. He continues:
  2311.  
  2312. "We can say of any number up to 100 whether it is possible or not to
  2313. express it as the sum of two cubes, except 66.  Students should read
  2314. the Introduction to Lucas's _Theorie des Nombres_, p. xxx."
  2315.  
  2316. "Some years ago I published a solution for the case 6 = (17/21)^3 +
  2317. (37/21)^3, of which Legendre gave at some length a 'proof' of
  2318. impossibility; but I have since found that Lucas anticipated me in
  2319. a communication to Sylvester."
  2320.  
  2321. ==> arithmetic/sums.of.powers.p <==
  2322. Partition 1,2,3,...,16 into two equal sets, such that the sums of the
  2323. numbers in each set are equal, as are the sums of their squares and cubes.
  2324.  
  2325. ==> arithmetic/sums.of.powers.s <==
  2326. The solution is A = {1,4,6,7,10,11,13,16}
  2327.                 B = {2,3,5,8,9,12,14,15}                                       
  2328.                   
  2329.  
  2330. Let X+k be a set formed by adding k to all elements of X.
  2331. Then A+k and B+k have the property of satisfying i,ii and iii.
  2332. That means, any 16 numbers in A.P can be partioned in such a way to
  2333. satisfy i,ii and iii.
  2334.  
  2335. How do we arrive at the above solution without using a computer?
  2336.  
  2337. By the preceding discussion,
  2338.  
  2339.         A1 = A-1 = {0,3,5,6,9,10,12,15}
  2340.         B1 = B-1 = {1,2,4,7,8,11,13,14}
  2341.  
  2342. have the property of satisfying i,ii and iii.
  2343. Notice that all numbers of A1 have even number of 1's in binary and
  2344. all numbers of B1 have odd number of 1's in binary. Essentially the
  2345. above partition is a partition based on parity.
  2346.  
  2347. Observation:
  2348.  
  2349.         Partition of (n+1) bit numbers based on parity into two
  2350. groups A and B (each consisting of 2^n elements) satisfies
  2351.  
  2352.  sum of kth powers of elements of A = sum of kth powers of elements of B
  2353.  
  2354. for k=1,2,...,n. (The above puzzle is a special case n=3).
  2355.  
  2356.  
  2357. The above observation also holds for any radix. In radix r we will have
  2358. r groups.
  2359.  
  2360. Infact,
  2361.  
  2362.         Any r^(n+1) terms in A.P can be partitioned into r groups (each of
  2363. r^n elements) such that sum of kth powers of all r groups is same (k=1,2,...,n)
  2364.  
  2365. Finding such groups with minimal number of elements (less than r^n) appears to
  2366. be more difficult!
  2367.  
  2368. ALL THIS APPEARS TO BE INTERESTING. IS IT A CONSEQUENCE OF A SIMPLE THEOREM OF
  2369. NUMBER THEORY? HOW DO I PROVE THIS?
  2370.  
  2371. Thanks in advance for any clues,
  2372.  
  2373. -- ramana@svl.cdc.com (Mr. Ramana (Indian analyst))
  2374.  
  2375. ==> arithmetic/tests.for.divisibility/eleven.p <==
  2376. What is the test to see if a number is divisible by eleven?
  2377.  
  2378.  
  2379. ==> arithmetic/tests.for.divisibility/eleven.s <==
  2380. If the alternating sum of the digits is divisible by eleven, so is the number.
  2381.  
  2382. For example, 1639 leads to 9 - 3 + 6 - 1 = 11, so 1639 is divisible by 11.
  2383.  
  2384. Proof:
  2385. Every integer n can be expressed as 
  2386. n = a1*(10^k) + a2*(10^k-1)+ .....+ a_k+1
  2387. where a1, a2, a3, ...a_k+1 are integers between 0 and 9.
  2388. 10 is congruent to -1 mod(11).
  2389. Thus if (-1^k)*a1 + (-1^k-1)*a2 + ...+ (a_k+1) is congruent to 0mod(11) then 
  2390. n is divisible by 11.
  2391.  
  2392. ==> arithmetic/tests.for.divisibility/nine.p <==
  2393. What is the test to see if a number is divisible by nine?
  2394.  
  2395. ==> arithmetic/tests.for.divisibility/nine.s <==
  2396. If the sum of the digits is divisible by nine, so is the number.
  2397.  
  2398. Proof:
  2399. Every integer n can be expressed as 
  2400. n = a1*(10^k) + a2*(10^k-1)+ .....+ a_k+1
  2401. where a1, a2, a3, ...a_k+1 are integers between 0 and 9.
  2402. Note that 10 is congruent to 1 (mod 9). Thus 10^k is congruent to 1 (mod 9) for
  2403. every k >= 0.
  2404. Thus n is congruent to (a1+a2+a3+....+a_k+1) mod(9).
  2405. Hence (a1+a2+...+a_k+1) is divisible by 9 iff n is divisible by 9.
  2406.  
  2407. ==> arithmetic/tests.for.divisibility/seven.p <==
  2408. What is the test to see if a number is divisible by seven?
  2409.  
  2410. ==> arithmetic/tests.for.divisibility/seven.s <==
  2411. Take the last digit (n mod 10) and double it.
  2412. Take the rest of the digits (n div 10) and subtract the doubled last
  2413.     digit from it.
  2414. The resulting number is divisible by 7 iff the original number
  2415.     is divisible by 7.
  2416.  
  2417. Example:  Take 53445
  2418.           Subtract (53445 mod 10) * 2 from (53445 div 10)
  2419.                            -  5  * 2   +   5344
  2420.                             = 5334
  2421.           533 - 2 * 4 = 525
  2422.           52 - 5 * 2 = 42 which is divisible by 7
  2423.           so 53445 is divisible by 7.
  2424.  
  2425. ==> arithmetic/tests.for.divisibility/three.p <==
  2426. What is the test to see if a number is divisible by three?
  2427.  
  2428. ==> arithmetic/tests.for.divisibility/three.s <==
  2429. A number is divisible by three iff the sum of its digits is divisible by three.
  2430. First, prove 10^N = 1 mod 3 for all integers N >= 0.
  2431. 1 = 1 mod 3. 10 = 1 mod 3. 10^N = 10^(N-1) * 10 = 10^(N-1) mod 3.
  2432. QED by induction. 
  2433. Now let D[0] be the units digit of N, D[1] the tens digit, etc.
  2434. Now N = Summation From k=0 to k=inf of D[k]*10^k.
  2435. Therefore N mod 3 = Summation from k=0 to k=inf of D[k] mod 3. QED
  2436.  
  2437.