March 2018 - mathfun@mailman.xmission.com

[math-fun] 1/7 etc.
by Bill Gosper 19 Mar '18

19 Mar '18

On 2018-03-19 08:35, James Propp wrote: > It’s nice to 89, in addition to being 10^2-10-1, is also a Fibonacci > number. > How many Fibonacci numbers are of the form n^2-n-1? > > Jim Propp In[26]:= Select[Fibonacci@Range@99999, squareq[4 # + 5] &] // tim During evaluation of In[26]:= 4767.121894,5 Out[26]= {1, 1, 5, 55, 89} In[24]:= squareq[n_Integer] := IntegerQ@√n Looks like a companion to 0,1,144. (Neither in OEIS) How about OEIS typographical finiteness conventions? E.g.: (Heegner) ..., 163. (Period means no more.) (Wieferich) 1093,3511,? means probably more (Pemutables) 991,1111111111111111111,11111111111111111111111.? maybe no more (Fibs) 4181,6765, fer sure more. --rwg > > On Monday, March 19, 2018, James Buddenhagen <jbuddenh(a)gmail.com> wrote: > >> Looks nicely fiby up till 90. (re: Allan Wechsler's 1/9899). >> >> On Sun, Mar 18, 2018 at 12:42 PM, Allan Wechsler <acwacw(a)gmail.com> wrote: >> >> > What do you think of 1/9899? In[2]:= RealDigits[1/9899] Out[2]= {{{1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 1, 3, 2, 1, 3, 4, 5, 5, 9, 0, 4, 6, 3, 6, 8, 3, 2, 0, 0, 3, 2, 3, 2, 6, 4, 9, 7, 6, 2, 6, 0, 2, 2, 8, 3, 0, 5, 8, 8, 9, 4, 8, 3, 7, 8, 6, 2, 4, 1, 0, 3, 4, 4, 4, 7, 9, 2, 4, 0, 3, 2, 7, 3, 0, 5, 7, 8, 8, 4, 6, 3, 4, 8, 1, 1, 5, 9, 7, 1, 3, 1, 0, 2, 3, 3, 3, 5, 6, 9, 0, 4, 7, 3, 7, 8, 5, 2, 3, 0, 8, 3, 1, 3, 9, 7, 1, 1, 0, 8, 1, 9, 2, 7, 4, 6, 7, 4, 2, 0, 9, 5, 1, 6, 1, 1, 2, 7, 3, 8, 6, 6, 0, 4, 7, 0, 7, 5, 4, 6, 2, 1, 6, 7, 8, 9, 5, 7, 4, 7, 0, 4, 5, 1, 5, 6, 0, 7, 6, 3, 7, 1, 3, 5, 0, 6, 4, 1, 4, 7, 8, 9, 3, 7, 2, 6, 6, 3, 9, 0, 5, 4, 4, 4, 9, 9, 4, 4, 4, 3, 8, 8, 3, 2, 2, 0, 5, 2, 7, 3, 2, 5, 9, 9, 2, 5, 2, 4, 4, 9, 7, 4, 2, 3, 9, 8, 2, 2, 2, 0, 4, 2, 6, 3, 0, 5, 6, 8, 7, 4, 4, 3, 1, 7, 6, 0, 7, 8, 3, 9, 1, 7, 5, 6, 7, 4, 3, 1, 0, 5, 3, 6, 4, 1, 7, 8, 1, 9, 9, 8, 1, 8, 1, 6, 3, 4, 5, 0, 8, 5, 3, 6, 2, 1, 5, 7, 7, 9, 3, 7, 1, 6, 5, 3, 7, 0, 2, 3, 9, 4, 1, 8, 1, 2, 3, 0, 4, 2, 7, 3, 1, 5, 8, 9, 0, 4, 9, 3, 9, 8, 9, 2, 9, 1, 8, 4, 7, 6, 6, 1, 3, 7, 9, 9, 3, 7, 3, 6, 7, 4, 1, 0, 8, 4, 9, 5, 8, 0, 7, 6, 5, 7, 3, 3, 9, 1, 2, 5, 1, 6, 4, 1, 5, 7, 9, 9, 5, 7, 5, 7, 1, 4, 7, 1, 8, 6, 5, 8, 4, 5, 0, 3, 4, 8, 5, 2, 0, 0, 5, 2, 5, 3, 0, 5, 5, 8, 6, 4, 2, 2, 8, 7, 0, 9, 9, 7, 0, 7, 0, 4, 1, 1, 1, 5, 2, 6, 4, 1, 6, 8, 0, 9, 7, 7, 8, 7, 6, 5, 5, 3, 1, 8, 7, 1, 9, 0, 6, 2, 5, 3, 1, 5, 6, 8, 8, 4, 5, 3, 3, 7, 9, 1, 2, 9, 2, 0, 4, 9, 7, 0, 1, 9, 9, 0, 1, 0, 0, 0}}, -3} >> > >> > >> > On Sun, Mar 18, 2018 at 2:26 PM, Thane Plambeck <tplambeck(a)gmail.com> >> > wrote: >> > >> > > i like the decimal expansion of 1/9801 >> > > >> > > On Sat, Mar 17, 2018 at 2:59 PM, Cris Moore <moore(a)santafe.edu> wrote: >> > > >> > > > >> > > > Indeed, 14+28+57 = 99… because 7 is a divisor of 10101... >> > > > and 07+69+23 = 99, because 13 is too. >> > > > >> > > > - Cris >> > > > >> > > > > On Mar 17, 2018, at 3:13 PM, Simon Plouffe < >> simon.plouffe(a)gmail.com> >> > > > wrote: >> > > > > >> > > > > >> > > > > >> > > > > Hello, >> > > > > >> > > > > we can remark that 142857 is symmetrical, 142 + 857 = 999 >> > > > > >> > > > > so one just has to remember half of the period in order to >> > > > > know all of the digits, >> > > > > 1/13 = 076923 , 076+923 = 999 too. >> > > > > >> > > > > this phenomena is true whenever p <> 2 or p <> 11 and >> > > > > the period is even. >> > > > > >> > > > > best regards, >> > > > > Simon Plouffe >> > > > > >> > > > > >> > > > > Le 2018-03-17 à 21:59, Cris Moore a écrit : >> > > > >> well, >> > > > >> >> > > > >> 1/13 = 0769/9997 = 0.0769 (1 + 0.0003 + 0.00000009 + …) = 0.0769 >> > 2307 >> > > … >> > > > >> >> > > > >> although this doesn’t quite break up the repetend 076923. You >> could >> > > > use the clumsier >> > > > >> >> > > > >> 1/13 = 076/988 = 0.076 (1 + 0.012 + 0.000144) = 0.076 + 0.000912 + >> > > > 0.0000109… = 0.076923… >> > > > >> >> > > > >> but this involves a bunch of carrying. >> > > > >> >> > > > >> Cris >> > > > >> >> > > > >>> On Mar 17, 2018, at 2:36 PM, James Propp <jamespropp(a)gmail.com> >> > > wrote: >> > > > >>> >> > > > >>> I just figured out for myself a probably well-known trick for >> > > > >>> deriving/remembering the decimal expansion of 1/7: 1/7 = 14/98 = >> > > > 14/(100-2) >> > > > >>> = .14/(1-.02) = .14 + .0028 + .000056 + .00000112 + ... = >> > .142857... >> > > > >>> >> > > > >>> >> > > > >>> Are there other examples where the repetend of the decimal >> > expansion >> > > > of 1/n >> > > > >>> in splits into blocks that are related to this sort of fashion? >> > > > >>> >> > > > >>> >> > > > >>> Jim Propp

1 1

Re: [math-fun] 1/7 etc.
by Keith F. Lynch 19 Mar '18

19 Mar '18

James Propp <jamespropp(a)gmail.com> wrote: > How many Fibonacci numbers are of the form n^2-n-1? For positive Fibonacci numbers less than 2^63, none except 1, 5, 55, and 89. If I replace one or both minus signs with plus signs, there are still no solutions above 89 (though there are a few more below it). Similarly if I leave out the n or the 1 (leaving n^2), except that 144 is of course square.

1 0

Re: [math-fun] References to math-fun for the outside world?
by Henry Baker 19 Mar '18

19 Mar '18

I have no problem with that, Allan. At 04:57 PM 3/18/2018, Allan Wechsler wrote: >I am making an entry to OEIS for Henry Baker's interesting sequence of >numerators to the successively better rational over-estimates of 2*pi. Can >I give credit with a reference to the math-fun archives? Are we "public" in >that sense? > >Henry, do I have permission to credit you and give your original post as a >reference?

2 1

[math-fun] 1/7 etc.
by James Propp 19 Mar '18

19 Mar '18

I just figured out for myself a probably well-known trick for deriving/remembering the decimal expansion of 1/7: 1/7 = 14/98 = 14/(100-2) = .14/(1-.02) = .14 + .0028 + .000056 + .00000112 + ... = .142857... Are there other examples where the repetend of the decimal expansion of 1/n in splits into blocks that are related to this sort of fashion? Jim Propp

6 11

Re: [math-fun] References to math-fun for the outside world?
by Dan Asimov 18 Mar '18

18 Mar '18

It may be good to limit the randomness of those having easy access to e-mail addresses. —Dan ----- I am making an entry to OEIS for Henry Baker's interesting sequence of numerators to the successively better rational over-estimates of 2*pi. Can I give credit with a reference to the math-fun archives? Are we "public" in that sense? Henry, do I have permission to credit you and give your original post as a reference? -----

1 0

Re: [math-fun] References to math-fun for the outside world?
by Keith F. Lynch 18 Mar '18

18 Mar '18

Allan Wechsler <acwacw(a)gmail.com> wrote: > I am making an entry to OEIS for Henry Baker's interesting sequence > of numerators to the successively better rational over-estimates of > 2*pi. Can I give credit with a reference to the math-fun archives? > Are we "public" in that sense? Well, OEIS is where I first heard of this list. > Henry, do I have permission to credit you and give your original > post as a reference? And a search for all mentions of the late Dan Hoey in OEIS is where I found the OEIS entry that mentioned this list. So if I get a vote, I vote for yes. Ironically, there was a recent discussion in a truly private forum that's not specifically dedicated to math that parallels a current thread here. Someone (not me) even mentioned an old HAKMEM entry about continued fractions by Gosper and RCS.

1 0

[math-fun] References to math-fun for the outside world?
by Allan Wechsler 18 Mar '18

18 Mar '18

I am making an entry to OEIS for Henry Baker's interesting sequence of numerators to the successively better rational over-estimates of 2*pi. Can I give credit with a reference to the math-fun archives? Are we "public" in that sense? Henry, do I have permission to credit you and give your original post as a reference?

2 1

[math-fun] "Contratinued fractions"
by Allan Wechsler 18 Mar '18

18 Mar '18

Gosper probably thought all this out decades ago, but Henry Baker's recent post discussed rational approximations to 2pi constrained to converge from above. Classical continued fractions converge to their target in alternating fashion, with the first convergent being below the target, the second closer but above, the third closer still but below, and so on. If the target is T0, we have C0 = floor(T0), and the reciprocal of the error is T1 = 1/(T0 - C0). Then we continue to calculate, with Cn = floor(Tn), and T[n+1] = 1/(Tn - Cn). But suppose we use ceiling instead of floor? That is, with target S0, set D0 = ceiling(S0), S1 = 1/(D0 - T0), Dn = ceiling(Sn), and S[n+1] = 1/(Dn - Sn). The resulting series of convergent rationals stays above the target, converging on it monotonically downward. The representation, expanded out, looks like S0 = D0 - 1/(D1 - 1/(D2 - 1/(...))), with subtraction instead of addition in the denominators. Until somebody comes up with a better name, I will call this a "contratinued fraction". Henry's first sequence, the one that OEIS doesn't know, is the sequence of numerators of the convergents of the contratinued fraction for 2pi. (Are these "contravergents"?). The coefficients of the contratinued fraction for 2pi are 7, 2, 2, 3, 9, 2, 148. In general, for an arbitrary positive real target, these contraefficients are always at least 2, except the leading one which can be 1. Probably there is fairly simple machinery for converting a continued fraction directly to a contratinued fraction, but I am not seeing it immediately.

1 0

[math-fun] Scaling of computer memories
by Henry Baker 18 Mar '18

18 Mar '18

[This post is mercifully short.] There are good empirical & theoretical reasons for thinking that the reference locality of computer software scales as M^(-3/2). This means that if one has a least-recently-used (LRU) cache of size M, the "miss ratio" (probability of not getting a cache "hit") is proportional to M^(-1/2).* One problem with analyzing cache behavior is the "lumpiness" of the cache hierarchy. However, LRU behavior can be modeled by a linear *stack*, where each reference *permutes* an address location to the *top* of the stack using a move-to-front strategy. As a result, the entire memory system becomes linearly ordered in LRU fashion.** Once we have a memory in LRU order, the probability of access to the N'th element in the stack is now proportional to N^(-3/2), so we have a more-or-less smooth analytic model of our memory system. We now have the probability of accessing the N'th element, but in order to compute the mean access *latency*, we need to know how memory latency scales with memory size. Thus, expected access time (EAT): EAT = integrate(pr(N)*latency(N),N,1,infinity) where pr(N) is the probability of accessing the N'th item in the LRU stack, and latency(N) is the latency of accessing the N'th item in the LRU stack. But if latency(N) scales as fast as sqrt(N) -- i.e., speed of light on a 2D plane -- then our *integral won't converge*, and our computer will run slower and slower *per memory access* (it grows as log(M)) on larger and larger programs. However, if latency(N) scales like N^(1/3) -- i.e., speed of light in 3D -- then our *integral WILL converge*, and our computer will run at a constant expected time *per memory access*. So we have no choice but to utilize 3D memory systems for large computations. So perhaps this explains why our brains are approximately spherical? Also, this explains why the denizens of Flatland will never achieve true brilliance. * Hartstein, et al. "On the Nature of Cache Miss Behavior": Is It sqrt(2)?". J. Instruction-Level Parallelism 10 (2008), 1-22. ** Mattson, et al. "Evaluation Techniques for Storage Hierarchies", IBM Sys. J. 9, 78 (1970).

1 0

Re: [math-fun] 1/7 etc.
by rcs＠xmission.com 18 Mar '18

18 Mar '18

There's a whole host of similar repeating decimal tricks, where a few leading digits are enough to reveal the whole. Usually, the trick is to recognize the denominator D as dividing some instance of A * 10^G +- B. Ideally A or B is 1, but other small numbers are usable. G is the length of the feedback loop. examples: 97 | 1*100 - 3 leads to 1/97 = .010309278350515... x3 -> 3092783505154... shifted by 2 digits 98 | 1*100 - 2 1/98 = .010204081632653... x2 -> 204081632653... 7 | 1*100 - 2 1/7 = 14/98 = .142857142857142... x2 -> 28571428571428... 19 | 2*10 -1 1/19 = .0526315789473684210526... /2 -> 26315789473684210526... 1 digit shift 23 | 1*1000 - 11 1/23 = .04347826086956521739130434... *11 -> 4782608695652173913043... 3 digit shift or 2*1000 + 1 /2 -> 21739130434782608695... + is complemented 78260869565217391304... 29 | 3*10 - 1 1/29 = .03448275862068965517241379310344... +1, /3 -> 344827586206896551724137931034... 17 | 1*100 + 2 1/17 = .05882352941176470588... x2 -> 1176470588 + is complemented 8823529411 2 digit shift 1*1000 + 3 1764705882 + is complemented 8235294117 3 digit shift 1*10000-4 x4 2352941176 4 digit shift 2*10 - 3 *3/2 882352941 1 digit shift Curiously, 999998 = 2 * 31 * 127^2 = 254 * 3937. This leads to Gosper's observation about 7874... below. Any number N ending in 1,3,7, or 9 divides some 10^K-1. The minimal such exponent K is a divisor of phi(N). When N is prime, and 10 is not a square mod N, then N will divide some 10^K+1, with K a divisor of (P-1)/2. Then the fraction's period can be split in half, with the second half being the 9s complement of the first. 10 is a non-square mod P for primes P = +-7,11,17,19 mod 40. However, sometimes even when 10 _is_ a square mod P, P can still divide some 10^K+1, and the period will have the two-halves-are-9s-complement property. P=13 is an example: 10 is a square (6^2=36=10 mod 13), but 13 | 1001, and the period (length 6) can be broken into 076 and 923. OTOH, for P=41, 10 is a square (16^2=256=10 mod 41), but 41 | 10^5-1, and never divides any 10^K+1. The period of 1/41 is .02439, with no complement property. --Rich --- Quoting Bill Gosper <billgosper(a)gmail.com>: > Also, from http://www.tweedledum.com/rwg/cfup.htm > > Similarly, if you want 100/2.54, the number of inches per meter, > you will find > > 39 2 1 2 2 1 4 > > which is much nicer than > > 39.(370078740157480314960629921259842519685039) > > where the part in parentheses repeats forever. (Incidentally, this > repeating decimal is easily computed since the remainder of 2 after > the quotient digits 3937 ensures that, starting with 7874..., the > answer will be just twice the original one, ignoring the > decimal point. Thus you just double the quotient, starting from the > left (using one digit lookahead for carries), placing the answer > digits on the right, so as to make the number chase its tail. This > trick is even easier in expansions of ratios where some remainder > is exactly 1/nth of an earlier one, for small n. You forget about > the divisor and simply start shortdividing by n at the quotient > digit corresponding to the earlier remainder. If this seems confusing, > forget it--it has nothing to do with continued fractions.) > > I just remembered that this writeup used to have a preface that began > "Continued fractions are hard to like. People who like continued fractions > drive Citroens and eat pickled okra." Followed by some disparagement of > people who eat with bent metal objects instead of chopsticks. > > I can't Google this anywhere. I bet somebody has a hardcopy. > --rwg > On 2018-03-17 14:13, Simon Plouffe wrote: >> Hello, >> >> we can remark that 142857 is symmetrical, 142 + 857 = 999 >> >> so one just has to remember half of the period in order to >> know all of the digits, >> 1/13 = 076923 , 076+923 = 999 too. >> >> this phenomena is true whenever p <> 2 or p <> 11 and >> the period is even. >> >> best regards, >> Simon Plouffe >> >> >> Le 2018-03-17 à 21:59, Cris Moore a écrit : >>> well, >>> >>> 1/13 = 0769/9997 = 0.0769 (1 + 0.0003 + 0.00000009 + ?) = 0.0769 2307 ? >>> >>> although this doesn?t quite break up the repetend 076923. You could use > the clumsier >>> >>> 1/13 = 076/988 = 0.076 (1 + 0.012 + 0.000144) = 0.076 + 0.000912 + > 0.0000109? = 0.076923? >>> >>> but this involves a bunch of carrying. >>> >>> Cris >>> >>>> On Mar 17, 2018, at 2:36 PM, James Propp <jamespropp(a)gmail.com> wrote: >>>> >>>> I just figured out for myself a probably well-known trick for >>>> deriving/remembering the decimal expansion of 1/7: 1/7 = 14/98 = > 14/(100-2) >>>> = .14/(1-.02) = .14 + .0028 + .000056 + .00000112 + ... = .142857... >>>> >>>> >>>> Are there other examples where the repetend of the decimal expansion of > 1/n >>>> in splits into blocks that are related to this sort of fashion? >>>> >>>> >>>> Jim Propp > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

1 0