- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] New Year's oddity
by Keith F. Lynch 23 Dec '18

23 Dec '18

Lots of things will change with the new year in a few days. But there's one thing that won't: The power of two in which the year first appears. As we all know, 2^212 is 6582018229284824168619876730229402019930943462534319453394436096. What you may not have noticed, not being as perceptive as me (i.e. having a life) is that it contains both 2018 and 2019 as substrings. And that it's the *first* power of two to contain *either* of those numbers as substrings. When, if ever, is the last time this happened? When, if ever, will be the next time? What's the expected density of this sequence? And should I add it to OEIS? Of course the question can be extended to other radices than base ten, and to other powers than those of two. A problem I haven't solved is which is the first power of two to start with 2018, and which is the first to start with 2019. It's easy to prove that there must be a solution, not just for 2018 and 2019, but for any positive integer.

5 4

[math-fun] New Mersenne; GIMPS Coin? Why not GIMPS for POW?
by Henry Baker 23 Dec '18

23 Dec '18

FYI -- A dozen Mersenne Primes in 15 years isn't exactly the same as a new blockchain block every 10 minutes, but at least it isn't consuming as much electricity as a third world country. Why not use GIMPS as proof-of-work for a "coin" that is only minted ~1X per year? We already have *sharing arrangements* to spread the wealth among all of the searchers of other blockchain coins, so this sort of arrangement should also work for GIMPS. https://www.mersenne.org/primes/?press=M82589933 https://science.slashdot.org/story/18/12/22/2130212/51st-known-mersenne-pri… The Great Internet Mersenne Prime Search (GIMPS) has discovered the largest known prime number, 2^82,589,933-1, having 24,862,048 digits. A computer volunteered by Patrick Laroche from Ocala, Florida made the find on December 7, 2018. GIMPS has been on amazing lucky streak, finding triple the expected number of new Mersenne primes -- a dozen in the last fifteen years. Patrick Laroche is one of thousands of volunteers using GIMPS' free software to hunt for prime numbers -- and is now eligible for a $3,000 "research discovery award," the group writes at mersenne.org. --- Perhaps it would be better for GIMPS if we *were* in Kansas anymore: https://yro.slashdot.org/story/18/12/22/2029247/kansas-is-trying-to-unload-… Kansas Governor Jeff Colyer's administration is seeking a way to donate or sell at a steep discount as much as $10 million in unused computer equipment that has been stored in a state office building since 2016. The state still owes $2 million on the equipment, which it bought in 2016 as part of a failed plan to develop a centralized storage system, call Kansas GovCloud, for computer information. That idea was canceled by state IT officials who said it was too expensive. Instead, the state contracts with an outside company to store data on remote servers. Attempts to sell the equipment failed to attract bidders, leading to discussions about finding someone to take the equipment before its value dropped to the level of scrap metal... [I seem to recall that between manufacturing and delivery, the old DEC computers were constantly working on GIMP-style problems; with today's blockchain mining apparatus, yet-to-be-delivered & warehoused computers could be earning their keep.]

2 1

Re: [math-fun] Exotic radices
by Don Reble 22 Dec '18

22 Dec '18

> A110081... begins 1, 7, 25, 31... > But that doesn't agree with my results. ... please name a real number > which can't be represented by {0, 1, -4}. Or by {0, 1, -10}. By Matula's lemma 3, {0,1,-4} doesn't represent 2. (More generally, {0,1,-(6n+4)} doesn't represent (3n+2).) The proof is straightforward (and correct, I hope): With {0,1,-4} digits, base 3: if the digit sequence (d_1 d_2 d_3 ... d_n) represents 2, then d_n must be -4, and so (d_1 d_2 d_3 ... d_{n-1}) represents [2 - (-4)] / 3 = 2. Inducing, there must be a single digit that represents 2. But there isn't. That treats only integer-like finite representations. But I doubt there's an infinite representation for 2. (1.??????...?) > I've confirmed that all integers up to at least 300 can be > represented with a 7-digit ternary number using those digits. !? Please show how {0,1,-4} makes 2. -- Don Reble djr(a)nk.ca

1 0

Re: [math-fun] Exotic radices
by Don Reble 22 Dec '18

22 Dec '18

>>> But as balanced ternary demonstrates, that's not the only choice. >>> Will any set of R consecutive digits do, so long as one of them is >>> 0? For instance almost-balanced decimal, where the decimal digits >>> are -4 through +5? Will any other set do? >> Other weird sets are possible. I have a vague recollection that >> digit sets in base ten are possible with gaps. But a search through >> my literature pile has been unsuccessful in tracking down the paper. Matula's paper is good. See OEIS A110081. -- Don Reble djr(a)nk.ca

4 3

Re: [math-fun] Exotic radices
by Keith F. Lynch 22 Dec '18

22 Dec '18

Don Reble <djr(a)nk.ca> wrote: > See OEIS A110081. That lists "Integers n such that the digit set D = (0, 1, -n) used in base 3 expansions of the form Sum_{ -N < j < infty} d_j 3^{-j}, all d_j in D, can represent all real numbers." It begins 1, 7, 25, 31... But that doesn't agree with my results. I concur on 1 and 7. I didn't test anything as high as 25. But please name a real number which can't be represented by {0, 1, -4}. Or by {0, 1, -10}. I can't find one. I've confirmed that all integers up to at least 300 can be represented with a 7-digit ternary number using those digits. (Larger integers presumably simply require more digits.) (Real numbers can of course be represented by moving the radix point to the left. Move it N places to the left and you can approximate any real number to a precision of 3^-N.) But neither have I proven there isn't one. Without such a proof, I'm reluctant to update OEIS. I'll look for a proof based on finding patterns in the digits. "Lucas, Stephen K - lucassk" <lucassk(a)jmu.edu> wrote: > Considering the fact that Matula?s paper came out in 1982, but was > based upon a technical report dating to 1978, I wonder who should > get priority for discovering digit sets that are not contiguous and > still can be used to represent integers and reals. Odlyzko (first > page is available) suggests a question by Knuth. I'm surprised it's so recent. It's the sort of thing that Fibonacci could have done. > And another fun result: most papers I?ve read on the topic > include 0 as a digit. It turns out not to be necessary. In > https://www.math.tugraz.at/fosp/pdfs/tugraz_0024.pdf they prove > that in base 2 you can use the digit set {1,4} except for the > leading digit, which may be {1,2,4} Interesting. I've been looking only at sets of N digits for base N. Even so, I was mistaken when I said ternary had to have 0. I tried all seven-digit ternary numbers using each possible sets of three digits from -9 through 9. I now realize I was implicitly thinking that seven-digit numbers included all shorter numbers too, since the leading digits can be zeros. Well, no, the leading digits *can't* be zeros if there's no zero in the set! I've corrected that, and discovered 32 sets of three digits not containing 0 to go with the 9 sets I had previously discovered that did contain 0. For instance {-3, 1, 2}. Here are zero through ten in that form of ternary, with 3 meaning -3: 13, 1, 2, 23, 11, 12, 233, 21, 22, 113, 231. Also, any number can be prefaced with 13 without changing its value. Hence 1 = 131 = 13131 = 1313131, etc.

1 0

[math-fun] Are you smarter than a 5th grade amoeba?
by Henry Baker 22 Dec '18

22 Dec '18

FYI -- This is a cool bio hack, but is this approach ever going to be faster and/or cheaper than an electronic computer for the same precision of optimization? https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.… Amoeba finds approximate solutions to NP-hard problem in linear time December 20, 2018 by Lisa Zyga, Phys.org Researchers have demonstrated that an amoeba--a single-celled organism consisting mostly of gelatinous protoplasm--has unique computing abilities that may one day offer a competitive alternative to the methods used by conventional computers. The researchers, led by Masashi Aono at Keio University, assigned an amoeba to solve the Traveling Salesman Problem (TSP). The TSP is an optimization problem in which the goal is to find the shortest route between several cities, so that each city is visited exactly once, and the start and end points are the same. https://royalsocietypublishing.org/doi/pdf/10.1098/rsos.180396 Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism Choosing a better move correctly and quickly is a fundamental skill of living organisms that corresponds to solving a computationally demanding problem. A unicellular plasmodium of Physarum polycephalum searches for a solution to the travelling salesman problem (TSP) by changing its shape to minimize the risk of being exposed to aversive light stimuli. In our previous studies, we reported the results on the eight-city TSP solution. In this study, we show that the time taken by plasmodium to find a reasonably high-quality TSP solution grows linearly as the problem size increases from four to eight. Interestingly, the quality of the solution does not degrade despite the explosive expansion of the search space. Formulating a computational model, we show that the linear-time solution can be achieved if the intrinsic dynamics could allocate intracellular resources to grow the plasmodium terminals with a constant rate, even while responding to the stimuli. These results may lead to the development of novel analogue computers enabling approximate solutions of complex optimization problems in linear time.

1 0

Re: [math-fun] Pre-K Klein bottle puzzle (SPOILER)
by Dan Asimov 21 Dec '18

21 Dec '18

The usual arggh. Changed notation in midstream. << Let X denote the union of all H_n, n <= 0, and all C_n, n > 0. should read ----- Let X denote the union of all X_n, n <= 0, and all X_n, n > 0. ----- Sorry about that. —Dan

1 0

Re: [math-fun] Pre-K Klein bottle puzzle (SPOILER)
by Dan Asimov 21 Dec '18

21 Dec '18

Okay, here's an example. Note that the half-open interval [0,1) maps bijectively to the unit circle S^1 in the complex plane by a continuous map with no continuous inverse: f : [0,1) —> S^1 via f(x) = exp(2πix). Now define the space X as a subset of C as follows: For each integer n <= 0, include a half-open interval X_n. For each integer n > 0, include a circle X_n. Let X denote the union of all H_n, n <= 0, and all C_n, n > 0. Then move X_n to X_(n+1) by a homeomorphism for n nonzero, and use a function like f above to map the half-interval X_0 bijectively onto the circle X_1 by a continuous map with no continuous inverse. This is clearly a continuous bijection of X to itself with no continuous inverse. If a connected set is desired, just arrange each X_n consecutively in the upper half plane intersecting the x-axis in one point (e.g., the point 4n so the X_n will be disjoint). Then add the x-axis to X, and we're done. —Dan For each integer n <= 0, include the half-open interval H_n = {(x,4n) in R^2 | 0 <= x < 1} in X. For each integer n > 0, include the circle C_n = {(1-exp(2πix),4n) ----- There do exist spaces X that are subsets of the plane possessing a continuous bijection X —> X without continuous inverse. Consider it a puzzle if you like. (But not the Klein bottle.) —Dan Bill Gosper wrote: ----- DanA: Consider the space Homeo(K) of self-homeomorphisms of the Klein bottle. I.e., Homeo(K) consists of all continuous bijections h : K —> K having a continuous inverse. __________ Umm, can somebody show me a continuous bijection with a *dis*continuous inverse? -----

1 0

[math-fun] Pre-K Klein bottle puzzle
by Bill Gosper 21 Dec '18

21 Dec '18

DanA: Consider the space Homeo(K) of self-homeomorphisms of the Klein bottle. I.e., Homeo(K) consists of all continuous bijections h : K —> K having a continuous inverse. __________ Umm, can somebody show me a continuous bijection with a *dis*continuous inverse? —rwg

2 2

Re: [math-fun] Pre-K Klein bottle puzzle
by Dan Asimov 21 Dec '18

21 Dec '18

There do exist spaces X that are subsets of the plane possessing a continuous bijection X —> X without continuous inverse. Consider it a puzzle if you like. (But not the Klein bottle.) —Dan Bill Gosper wrote: ----- DanA: Consider the space Homeo(K) of self-homeomorphisms of the Klein bottle. I.e., Homeo(K) consists of all continuous bijections h : K —> K having a continuous inverse. __________ Umm, can somebody show me a continuous bijection with a *dis*continuous inverse? -----

1 0