數(shù)學(xué)外文翻譯外文文獻(xiàn)英文文獻(xiàn)具體數(shù)學(xué)(文件)
【正文】 2n + 1 = 2 re essentially done! We have shown that the functionsA(n),B(n), and C(n) of (), which solve () in general, satisfy the equationsA(n) = 2m, or n = 2m + l and 0 ≤ l 2m。 this gives us a repertoire of special cases that we can we obtain the general case by bining the special cases. We need as many independent special solutions as there are independent parameters (in this case three, for α，β and γ) Exercises 16 and 20 provide further examples of the repertoire approach.We know that the originalJrecurrence has a magical solution, in binary: J (bmbm?1...b1b0)2 = (bm?1...b1b0bm)2, when bm = 1.Does the generalized Josephus recurrence admit of such magic?Sure, why not? We can rewrite the generalized recurrence () asf(1) = α。 f(dn + j) = cf(n) + βj for 0 ≤ j d and n ≥ 1, （10）is the same as the previous one except that we start with numbers in radix d and produce values in radixc. That is, it has the radixchanging solution f (bmbm?1...b1b0)d = (αbmβbm?1βbm?2 . . . βb1βb0)c. （11）For example, suppose that by some stroke of luck we39。And this recurrence unfolds, binarywise:f (bmbm?1...b1b0)2 = 2f (bmbm?1...b1)2 + βb0 = 4f (bmbm?1...b2)2 + 2βb1 + βb1 = 2mf (bm)2 + 2m?1βbm?1 + . .+ βb0 = 2mα + 2m?1βbm?1 + . . + βb0.Suppose we now relax the radix2notation to allow arbitrary digits instead of just0and1. The derivation above tells us thatf (bmbm?1...b1b0)2 = (αβbm?1βbm?2 . . . βb1 + βb0)2. （9）Nice. We would have seen this pattern earlier if we had written () in another way:For example, when n = 100 = (1100100)2 our original Josephus valuesα = 1，β = ?1，and γ = 1 yieldas before. The cyclicshift property follows because each block of binary digits(10...000)2 in the representation of nis transformed into(1 ?1... ?1 ?1)2 = (0 0 ... 0 1)2.So our change of notation has given us the pact solution () to the general recurrence (). If we39。A(n) + C(n) = n.Our conjectures in () follow immediately, since we can solve these equations to get C(n) = n ? A(n) = l and B(n) = A(n) ? 1 ? C(n) = 2m ? 1 ? l。These equations hold for allnwhenα = 1，β = 2 and γ = 1, so we don39。2n = 2 3 = 2 s true (by induction onm) that ,A(2m + l) = 2m Next, let39。s illustrate this by considering the special caseα = 1，β = γ = 0 when f(n) is supposed to be equal toA(n): Recurrence () beesA(1) = 1。C(n) = l. （7）Here, as usual, n = 2m + l and 0 ≤ l 2m，for n ≥ 1。（4）f (2n + 1) = 2f (n) + γ, for n ≥ 1.(Our original recurrence had α = 1，β = ?1 andγ = 1。s not hard to verify that 2m2 is a multiple of3whenmis odd, but not when mis even. (We will study such things in Chapter 4.) Therefore there are innitely many solutions to the equationJ(n) =n/2 beginning as follows:Notice the pattern in the rightmost column. These are the binary numbers for which cyclicshifting one place left produces the same result as ordinaryshifting one place right (halving).OK, we understand theJfunction pretty well。Similarly8or moreJ(J(...J(101101101101011)2...)) = 210 ? 1 = 1023。 the 0disappears when it bees the leading fact, J(n) must always be ≤n, by denition, sinceJ(n) is the survivor39。 (3)that is, in the lingo of puter programming, we get J(n) from nby doing a onebit cyclic shift left! Magic. For example, if n= 100 =(1100100)2 then J(n) = J(1100100)2=(1001001)2, which is 64+8+1=73. If we had been working all along in binary notation, we probably would have spotted this pattern immediately.if we start with nand iterate theJ function m+1 times, we39。snatural to look at the radix2 representations of nandJ(n). Suppose n39。s pute J(100). In this case we have100 =26+ 36, so J(100) = 2*36 + 1 = 73Now that we39。 thus the basis of reduces to J(1) = 1, which is true. The induction step has two parts, depending on whetherl is
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1