7.Arithmetic & Number Theoretic Recreations

SOURCES - page 1

7.ARITHMETIC & NUMBER THEORETIC RECREATIONS

7.A.FIBONACCI NUMBERS

We use the standard form: F0 = 0, F1 = 1, Fn+1 = Fn + Fn-1, with the auxiliary Lucas numbers being given by: L0 = 2, L1 = 1, Ln+1 = Ln + Ln-1.

Parmanand Singh. The so-called Fibonacci numbers in ancient and medieval India. HM 12 (1985) 229-244. In early Indian poetry, letters had weights of 1 or 2 and meters were classified both by the number of letters and by the weight. Classifying by weight gives the number of sequences of 1s and 2s which add to the weight n and this is Fn+1.

Pińgala [NOTE: ń denotes n with an overdot.] (c-450) studied prosody and gives cryptic rules which have been interpreted as methods for generating the next set of sequences, either classified by number of letters or by weight and several later writers have given similar rules. The generation implies Fn+1 = Fn + Fn-1. Virahāńka [NOTE: ń denotes n with an overdot.] (c7C) is slightly more explicit. Gopāla (c1134) gives a commentary on Virahāńka [NOTE: ń denotes n with an overdot.] which explicitly gives the numbers as 3, 5, 8, 13, 21. Hemacandra (c1150) states "Sum of the last and last but one numbers ... is ... next." This is repeated by later authors.

The Prākŗta [NOTE: ŗ denotes r with an underdot] Paińgala [NOTE: ń denotes n with an overdot.] (c1315) gives rules for finding the k-th sequence of weight n and for finding the position of a particular sequence in the list of sequences of weight n and the positions of those sequences having a given number of 2s (and hence a given number of letters). It also gives the relation Fn+1 = Σi BC(n-i,i).

Narayana Pandita (= Nārāyaņa Paņdita’s [NOTE: ņ denotes n with an overdot and the d should have an underdot.]) Gaņita[NOTE: ņ denotes n with an underdot.] Kaumudī (1356) studies additive sequences in chap. 13, where each term is the sum of the last q terms. He gives rules which are equivalent to finding the coefficients of (1 + x + ... + xq-1)p and relates to ordered partitions using 1, 2, ..., q.

Narayana Pandita (= Nārāyaņa Paņdita [NOTE: ņ denotes n with an overdot and the d should have an underdot.]). Gaņita[NOTE: ņ denotes n with an underdot.] Kaumudī (1356). Part I, (p. 126 of the Sanskrit ed. by P. Dvivedi, Indian Press, Benares, 1942), ??NYS -- quoted by Kripa Shankar Shukla in the Introduction to his edition of: Narayana Pandita (= Nārāyaņa Paņdita); Bījagaņitāvatamsa [NOTE: the ņ denotes an n with an under dot and there should be a dot over the m.]; Part I; Akhila Bharatiya Sanskrit Parishad, Lucknow, 1970, p. iv. "A cow gives birth to a calf every year. The calves become young and themselves begin giving birth to calves when they are three years old. Tell me, O learned man, the number of progeny produced during twenty years by one cow."

WESTERN HISTORIES

H. S. M. Coxeter. The golden section, phyllotaxis, and Wythoff's game. SM 19 (1953) 135 143. Sketches history and interconnections.

H. S. M. Coxeter. Introduction to Geometry. Wiley, 1961. Chap. 11: The golden section and phyllotaxis, pp. 160-172. Extends his 1953 material.

Maxey Brooke. Fibonacci numbers: Their history through 1900. Fibonacci Quarterly 2:2 (1964) 149 153. Brief sketch, with lots of typographical errors. Doesn't know of Bernoulli's work.

Leonard Curchin & Roger Herz-Fischler. De quand date le premier rapprochement entre la suite de Fibonacci et la division en extrême et moyenne raison? Centaurus 28 (1985) 129-138. Discusses the history of the result that the ratio Fn+1/Fn approaches φ. Pacioli and Kepler, described below, seem to be the first to find this.

Roger Herz Fischler. Letter to the Editor. Fibonacci Quarterly 24:4 (1986) 382.

Roger Herz-Fischler. A Mathematical History of Division in Extreme and Mean Ratio. Wilfrid Laurier University Press, Waterloo, Ontario, 1987. Retitled: A Mathematical History of the Golden Number, with new preface and corrections and additions, Dover, 1998. Pp. 157-162 discuss early work relating the Fibonacci sequence to division in extreme and mean ratio. 15 pages of references.

Georg Markovsky. Misconceptions about the Golden Ratio. CMJ 23 (1992) 2-19. This surveys many of the common misconceptions -- e.g. that -- appears in the Great Pyramid, the Parthenon, Renaissance paintings and/or the human body and that the Golden Rectangle is the most pleasing -- with 59 references. He also discusses the origin of the term 'golden section', sketching the results given in Herz-Fischler's book.

Thomas Koshy. Fibonacci and Lucas Numbers with Applications. Wiley-Interscience, Wiley, 2001. Claims to be 'the first attempt to compile a definitive history and authoritative analysis' of the Fibonacci numbers, but the history is generally second-hand and marred with a substantial number of errors, The mathematical work is extensive, covering many topics not organised before, and is better done, but there are more errors than one would like.

Ron Knott has a huge website on Fibonacci numbers and their applications, with material on many related topics, e.g. continued fractions, π, etc. with some history. .

Fibonacci. 1202. Pp. 283 284 (S: 404-405): Quot paria coniculorum in uno anno ex uno pario germinentur [How many pairs of rabbits are created by one pair in one year]. Rabbit problem -- the pair propagate in the first month so there are Fn+2 pairs at the end of the n-th month. (English translation in: Struik, Source Book, pp. 2 3.) I have colour slides of this from L.IV.20 & 21 and Conventi Soppresi, C. I. 2616. This is on ff. 130r-130v of L.IV.20, f. 225v of L.IV.21, f. 124r of CS.C.I.2616.

Unknown early 16C annotator. Marginal note to II.11 in Luca Pacioli's copy of his 1509 edition of Euclid. Reproduced and discussed in Curchin & Herz-Fischler and discussed in Herz-Fischler's book, pp. 157-158. II.11 involves division in mean and extreme ratio. Uses 89, 144, 233 and that 1442 = 89 * 233 + 1. Also refers to 5, 8, 13.

Gori. Libro di arimetricha. 1571. F. 73r (p.81). Rabbit problem as in Fibonacci.

J. Kepler. Letter of Oct 1597 to Mästlin. ??NYS -- described in Herz-Fischler's book, p. 158. This gives a construction for division in extreme and mean ration. On the original, Mästlin has added his numerical calculations, getting 1/φ = .6180340, which Herz-Fischler believes to be the first time anyone actually calculated this number.

J. Kepler. Letter of 12 May 1608 to Joachim Tanckius. ??NYS -- described in Herz-Fischler (1986), Curchin & Herz-Fischler and Herz-Fishler's book, pp. 160-161. Shows that he knows that the ratio Fn+1/Fn approaches φ and that Fn2 + (-1)n = Fn-1Fn+1.

J. Kepler. The Six Cornered Snowflake. Op. cit. in 6.AT.3. 1611. P. 12 (20 21). Mentions golden section in polyhedra and that the ratio Fn+1/Fn approaches φ. See Herz-Fischler's book, p. 161.

Albert Girard, ed. Les Œuvres Mathematiques de Simon Stevin de Bruges. Elsevier, Leiden, 1634. Pp. 169 170, at the end of Stevin's edition of Diophantos (but I have seen other page references). Notes the recurrence property of the Fibonacci numbers, starting with 0, and asserts that the ratio Fn+1/Fn approaches the ratio of segments of a line cut in mean and extreme ratio, i.e. φ, though he doesn't even give its value -- but he says 13, 13, 21 'rather precisely constitutes an isosceles triangle having the angle of a pentagon'. Herz-Fischler's book, p. 162, notes that Girard describes it as a new result and includes 0 as the starting point of the sequence.

Abraham de Moivre. The Doctrine of Chances: or, A Method of Calculating the Probability of Events in Play. W. Pearson for the Author, London, 1718. Lemmas II & III, pp. 128 134. Describes how to find the generating function of a recurrence. One of his illustrations is the Lucas numbers for which he gets:

x + 3x2 + 4x3 + 7x4 + 11x5 + ... = (2x + x2)/(1 - x - x2). However, he does not have the Fibonacci numbers and he does not use the generating function to determine the individual coefficients of the sequence. In Lemma III, he describes how to find the recurrence of p(n) an where p(n) is a polynomial. Koshy [p. 215] says De Moivre invented generating functions to solve the Fibonacci recurrence, which seems to be reading much more into De Moivre than De Moivre wrote. The second edition is considerably revised, cf below.

Daniel Bernoulli. Observationes de seriebus quae formantur ex additione vel substractione quacunque terminorum se mutuo consequentium, ubi praesertim earundem insignis usus pro inveniendis radicum omnium aequationum algebraicarum ostenditur. Comm. Acad. Sci. Petropolitanae 3 (1728(1732)) 85 100, ??NYS. = Die Werke von Daniel Bernoulli, ed. by L. P. Bouckaert & B. L. van der Waerden, Birkhäuser, 1982, vol. 2, pp. 49+??. Section 6, p. 52, gives the general solution of a linear recurrence when the roots of the auxiliary equation are distinct. Section 7, pp. 52 53, gives the 'Binet' formula for Fn. [Binet's presentation is so much less clear that I suggest the formula should be called the Bernoulli formula.]

Abraham de Moivre. The Doctrine of Chances: or, A Method of Calculating the Probability of Events in Play. 2nd ed, H. Woodfall for the Author, London, 1738. Of the Summation of recurring Series, pp. 193-206. This is a much revised and extended version of the material, but he says it is just a summary, without demonstrations, as he has given the demonstrations in his Miscellanea Analytica of 1730 (??NYS). Gives the generating functions for various recurrences and even for a finite number of terms. Prop. VI is: In a recurring series, any term may be obtained whose place is assigned. He assumes the roots of the auxiliary equation are real and distinct. E.g., for a second order recurrence with distinct roots m, p, he says the general term is Amn + Bpn where he has given A and B in terms of the first two values of the recurrence. He even gives the general solution for a fourth order recurrence and expresses A, B, C, D in terms of the first four values of the recurrence. Describes how to take the even terms and the odd terms of a recurrence separately and how to deal with sum and product of recurrences.

R. Simson. An explication of an obscure passage in Albert Girard's commentary upon Simon Stevin's works. Phil. Trans. Roy. Soc. 48 (1753) 368 377. Proves that Fn2 + ( 1)n = Fn-1Fn+1. This says that the triple Fn-1, Fn, Fn+1 "nearly express the segments of a line cut in extreme and mean proportion, and the whole line;" from which he concludes that the ratio Fn+1/Fn does converge to φ. Herz-Fischler's book, p. 162, notes that his proof is essentially an induction. (He also spells the author Simpson, but it is definitely Simson on the paper.) [Koshy, p. 74, says Fn2 + ( 1)n = Fn-1Fn+1 was discovered in 1680 by Giovanni Domenico Cassini, but he gives no reference and neither Poggendorff nor BDM help to determine what paper this might be.]

Ch. Bonnet. Recherches sur l'usage des feuilles dans les plantes. 1754, pp. 164 188. Supposed to be about phyllotaxis but only shows some spirals without any numbers. Refers to Calandrini. Nice plates.

Master J. Paty (at the Mathematical Academy, Bristol), proposer; W. Spicer, solver. Ladies' Diary, 1768-69 = T. Leybourn, II: 293, quest. 584. Cow calves at age two and every year thereafter. How many offspring in 40 years? Answer is: 0 + 1 + 1 + 2 + 3 + ... + F39. We would give this as: F41 - 1, but he gets it as: 2F39 + F38 - 1.

Eadon. Repository. 1794. P. 389, no. 47. Same as the previous problem.

Jackson. Rational Amusement. 1821. Curious Arithmetical Questions, no. 32, pp. 22 & 82. Similar to Fibonacci, with a cow and going for 20 generations.

Martin Ohm. Die reine Elementar-Mathematik. 2nd ed., Jonas Verlags-Buchhandlung, Berlin, 1835. P. 194, footnote to Prop. 5. ??NYS -- extensively discussed in Herz-Fischler's book, p. 168. This is the oldest known usage of 'goldene Schnitt'. It does not appear in the 1st ed. of 1826 and here occurs as: "... nennt man wohl auch den goldenen Schnitt" (... one also appropriately calls [this] the golden section). The word 'wohl' has many, rather vague, meanings, giving different senses to Ohm's phrase. Herz-Fischler interprets it as 'habitually', which would tend to imply that Ohm and/or his colleagues had been using the term for some time. I don't really see this meaning and interpreting 'wohl' as 'appropriately' would give no necessity for anyone else to know of the phrase before Ohm. However the term is used in several other German books by 1847. [Incidentally, this is not the Ohm of Ohm's Law, but his brother.]

A. F. W. Schimper & A. Braun. Flora. 1835. Pp. 145 & 737. ??NYS

J. Binet. Mémoire sur l'integration des équations linéaires aux différences finies, d'un ordre quelconque, à coefficients variables. (Extrait par l'auteur). CR Acad. Sci. Paris 17 (1843) 559 567. States the Binet formula as an example of a general technique for solving recurrences of the form: v(n+2) = v(n+1) + r(n)v(n), but the general technique is not clearly described, nor is the linear case.

B. Peirce. Mathematical investigation of the fractions which occur in phyllotaxis. Proc. Amer. Assoc. Adv. Sci. 2 (1849) 444 447. Not very interesting.

Gustav Theodor Fechner. Vorschule der Ästhetik. Breitkopf & Härtel, Leipzig, 1876. ??NYS. Origin of the aesthetic experiments on golden rectangles.

Koshy [p. 5] says Lucas originally called Fn the 'série de Lamé', but introduced the name Fibonacci numbers in May 1876. However, he doesn't give a reference. There are several papers by Lucas which might be the desired paper.

Note sur le triangle arithmétique de Pascal et sur la série de Lamé. Nouvelle Correspondence Mathématique 2 (1876) 70-75; which might be the desired paper.

L'arithmétique, la série de Lamé, le problème de Beha-Eddin, etc. Nouvelles Annales de Mathématiques 15 (1876) 20pp.

Édouard Lucas. Théorie des fonctions numériques simplement périodiques. AJM 1 (1878) 184-240 (Sections 1-23) & 289-321 (Sections 24-30). [There is a translation by Sidney Kravitz of the first part as: The Theory of Simply Periodic Numerical Functions, edited by Douglas Lind, The Fibonacci Association, 1969. Dickson I 400, says this consists of 7 previous papers in Nouv. Corresp. Math. in 1877-1878 with some corrections and additions. Robert D. Carmichael; Annals of Math. (2) 15 (1913) 30-70, ??NX, gives corrections.] The classic work which begins the modern study of recurrences.

Koshy, p. 273, says Adolf Zeising's Der goldene Schnitt of 1884 put forth the theory that "the golden ratio is the most artistically pleasing of all proportions ...." But cf Fechner, 1876.

Pearson. 1907. Part II, no. 63: A prolific cow, pp. 126 & 203. Same as Fibonacci's rabbits, but wants the total after 16 generations.

Koshy, p. 242, asserts that Mark Barr, an American mathematician, introduced the symbol φ (from Phidias) for the Golden Ratio, (1 + 5)/2, about 1900, but he gives no reference.

Coxeter, 1953, takes τ from the initial letter of τoμη, the Greek word for section, but I have no idea if this was used before him.

There is a magic trick where you ask someone to pick two numbers and extend them to a sequence of ten by adding the last two numbers each time. You then ask him to add up the ten numbers and you tell him the answer, which is 11 times the seventh number. In general, if the two starting numbers are A and B, the n-th term is Fn-2A + Fn-1B and the sum of the first 2n terms is F2nA + (F2n+1-1)B = Ln (FnA + Fn+1B), but only the case n = 5 is interesting! I saw Johnny Ball do this in 1989 and I have found it in: Shari Lewis; Abracadabra! Magic and Other Tricks; (World Almanac Publications, NY, 1984); Puffin, 1985; Sum trick!, p. 14, but it seems likely to be much older.

7.B.JOSEPHUS OR SURVIVOR PROBLEM

See Tropfke 652.

This is the problem of counting out every k th from a circle of n. Early versions counted out half the group; later authors and the Japanese are interested in the last man -- the survivor. Euler (1775) seems to be the first to ask for the last man in general which we denote as L(n, k). Cardan, 1539, is the first to associate this process with Josephus. Some later authors derive this from the Roman practice of decimation.

For last man versions, see the general entries and: Michinori?, Kenkō, Cardan, Coburg, Bachet, van Etten, Yoshida, Muramatsu, Schnippel, Ozanam (1696 & 1725), Les Amusemens, Fujita, Euler, Miyake, Matuoka, Boy's Own Book, Nuts to Crack, The Sociable, Indoor & Outdoor, Secret Out (UK), Leske, Le Vallois, Hanky Panky, Kemp, Mittenzwey, Gaidoz, Ducret, Lemoine, Akar et al, Lucas, Schubert, Busche, Tait, Ahrens, Rudin, MacFhraing, Mendelsohn, Barnard, Zabell, Richards, Dean, Richards,

2 to last, counted by 9s: Boy's Own Book,

3 to last, counted by 9s: Boy's Own Book,

4 to last, counted by 9s: Boy's Own Book,

5 to last, counted by 9s: Boy's Own Book,

6 to last, counted by 9s: Boy's Own Book,

7 to last, counted by 9s: Boy's Own Book,

9 to last, counted by 9s: Boy's Own Book,

10 to last, counted by 9s: Boy's Own Book,

11 to last, counted by 9s: Boy's Own Book,

12 to last, counted by 9s: Boy's Own Book, Secret Out (UK),

12 to last, counting number unspecified: Coburg,

13 to last, counted by 2s: Ducret, Leeming,

13 to last, counted by 9s: Boy's Own Book, Secret Out (UK), Leske, Rudin,

14 to all!, counted by 6s: Secret Out,

14 to last, counted by 10s: Mittenzwey,

17 to last, counted by 3s: Barnard,

21 to last, counted by 5s: Hyde,

21 to last, counted by 7s: Nuts to Crack, The Sociable, Indoor & Outdoor, Hanky Panky, H. D. Northrop,

21 to last, counted by 8s: Mittenzwey,

21 to last, counted by 10s: Hyde,

24 to last, counted by 9s: Kemp,

28 to last, counted by 9s: Kemp,

30 to last, counted by 9s: Schnippel,

30 to last, counted by 10s: see entries in next table for 15 & 15 counted by 10s

40 to last man, counted by 3s: van Etten (erroneous),

41 to last man, counted by 3s: van Etten, Ozanam (1725), Vinot, Ducret, Lucas (1895),

General case: Euler, Lemoine, Akar et al., Schubert, Busche, Tait, Ahrens, MacFhraing, Mendelsohn, Robinson, Jakóbczyk, Herstein & Kaplansky, Zabell, Richards,

There are a few examples where one counts down to the last two persons -- see references to Josephus and: Pacioli, Muramatsu, Mittenzwey, Ducret, Les Bourgeois Punis.

Almost all the authors cited consider 15 & 15 counted by 9s, so I will only index other versions.

2 & 2 counted by 3s: Ball (1911),

2 & 2 counted by 4s: Ball (1911),

3 & 3 counted by 7s: Ball (1911),

3 & 3 counted by 8s: Ball (1911),

4 & 4 counted by 2s: Leeming,

4 & 4 counted by 5s: Ball (1911),

4 & 4 counted by 9s: Ball (1911),

5 & 5 counted by ??: Dudeney (1905), Pearson, Ball (1911), Ball (1920), Shaw,

6 & 6 counted by ??: Dudeney (1900),

8 & 2 counted by ??: Les Bourgeois Punis,

8 & 8 counted by 8s: Kanchusen,

8 & 8 counted by ??: Dudeney (1899),

12 & 12 counted by 6s: Harrison,

15 & 15 counted by 3s: Tartaglia, Alberti,

15 & 15 counted by 4s: Tartaglia,

15 & 15 counted by 5s: Tartaglia,

15 & 15 counted by 6s: AR, Codex lat. Monacensis 14908, Tartaglia,

15 & 15 counted by 7s: Tartaglia, Schnippel,

15 & 15 counted by 8s: Codex lat. Monacensis 14836, AR, Codex lat. Monacensis 14908, Tartaglia, Alberti,

15 & 15 counted by 10s: Michinori?, Reimar von Zweiter, AR, Codex lat. Monacensis 14908, Chuquet, Tartaglia, Buteo, Hunt, Yoshida, Muramatsu, Wingate/Kersey, Schnippel, Alberti, Shinpen Kinko-ki, Fujita, Miyake, Matuoka, Sanpo Chie Bukuro, Hoffmann, Brandreth, Benson, Williams, Collins, Dean. (Almost all of these actually continue to the last person.)

15 & 15 counted by 11s: Tartaglia, Schnippel,

15 & 15 counted by 12s: AR, Codex lat. Monacensis 14908, Tartaglia,

15 & 15 counted by other values, not specified -- ??check: Codex lat. Monacensis 14836, Meermanische Codex, at Tilimsâni, Bartoli, Murray 643, Chuquet, Keasby,

17 & 15 counted by 10s: Schnippel,

17 & 15 counted by 12s: Mittenzwey,

18 & 2 counted by 12s: Pacioli, Rudin,

18 & 6 counted by 8s: Manuel des Sorciers,

18 & 18 counted by 9s: Chuquet,

24 & 24 counted by 9s: Chuquet,

30 & 2 counted by 7s: Pacioli,

30 & 2 counted by 9s: Pacioli,

30 & 6 counted by 10s: Ducret, 30 & 10 counted by 12s: Endless Amusement II, Magician's Own Book, The Sociable, Boy's Own Conjuring Book, Lucas (1895),