December 2018 - mathfun@mailman.xmission.com

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

23 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 22 Dec '18

22 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 22 Dec '18

22 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

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

21 Dec '18

"Lucas, Stephen K - lucassk" <lucassk(a)jmu.edu> wrote: > Keith F. Lynch <kfl(a)KeithLynch.net> wrote: >> I'm pretty sure that rational numbers, other than integers and >> their reciprocals, won't work. > Rational numbers work as the base of a number system where the > integers terminate if you are careful with the digits allowed, not > limiting yourself to digits up to floor(R). Thanks. >> Once you've chosen a radix, what digits should be allowed? The >> standard is 0 through R-1, where R is the ceiling of the radix. >> (Assuming the radix is greater than 1.) I've since realized that for algebraic irrational bases, in the general case I can't limit myself to digits up to floor(R) or even floor(R+1) if I want all integers to terminate. For instance in base sqrt(10) the current year is 2000108 and Columbus sailed in 1040902. I could represent those numbers with no digits greater than 3, but then neither number would terminate. >> 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. This looks like a job for brute force. Base ten is a bit much for a one-hour project, but I checked ternary with all possible set of three digits between -9 and 9 inclusive. The following digit sets seem to be able to represent all integers, and presumably all reals as well: {-7,0,1}, {-5,0,2}, {-4,0,1}, {-2,-1,0}, {-2,0,5}, {-1,0,1}, {-1,0,4}, {-1,0,7}, {0,1,2}. Note the symmetry that if I replace each digit with its negative, that works too. I then did the same with quaternary, also with digits -9 through 9. The following sets of four digits appear to work: {-9,-7,0,2}, {-9,-2,0,1}, {-9,0,1,2}, {-9,0,2,5}, {-7,-5,0,2}, {-7,-1,0,2}, {-7,-1,0,6}, {-7,0,2,3}, {-6,-5,0,1}, {-6,-1,0,1}, {-6,-1,0,5}, {-6,0,1,7}, {-5,-2,0,1}, {-5,-2,0,9}, {-5,0,1,2}, {-5,0,1,6}, {-3,-2,-1,0}, {-3,-2,0,7}, {-3,-1,0,2}, {-2,-1,0,1}, {-2,-1,0,5}, {-2,-1,0,9}, {-2,0,1,3}, {-2,0,1,7}, {-2,0,5,7}, {-2,0,7,9}, {-1,0,1,2}, {-1,0,1,6}, {-1,0,2,5}, {-1,0,2,9}, {-1,0,5,6}, {0,1,2,3}. Again, if I replace each digit with its negative, that works too. The only other patterns I notice immediately are that 0 must always be included and that both negatives and positives must be included unless the digits are consecutive. Surprisingly, neither 1 nor -1 needs to be included. (If base four is called quaternary, why isn't base three called tertiary? Geologists have abandoned both terms, replacing them with neogene and paleogene, so mathematicians might as well use them. Just so long as we don't confuse triadic fractions with triassic fractions.)

1 0

[math-fun] Klein bottle puzzle
by Dan Asimov 21 Dec '18

21 Dec '18

Here's a puzzle I think I know the answer to, but I don't have a proof: Let K denote the Klein bottle, the ideal surface you get when you identify the top and bottom edges of the unit square [0,1] x [0,1] normally, by (x,0) ~ (x,1), but identify the left and right edges by a flip: (0,y) ~ (1,1-y). Puzzle: ----------------------------------------------------------------------- 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. Two self-homeomorphisms h_0, h_1 of K are *in the same path component* of Homeo(K) if there is a continuous *family* {h(t) | 0 <= t <= 1} of homeomorphisms h(t) in Homeo(K) such that h(e) = h_e for e = 0, 1. The continuity of this family just amounts to there being a continuous map H : K x [0,1] —> K such that the restriction of H to any time-slice K x {t}: H | K x {t} —> K is the homeomorphism h(t) : K —> K. QUESTION: ————————— How many path components does Homeo(K) have? ----------------------------------------------------------------------- —Dan

3 2