May 2020 - mathfun@mailman.xmission.com

Re: [math-fun] Graph question
by Dan Asimov 14 May '20

14 May '20

Just to be clear, I made no conjecture. I was only asking when such graphs exist. —Dan Andy Latto wrote: ----- On Thu, May 14, 2020 at 11:02 AM Dan Asimov <dasimov(a)earthlink.net> wrote: > Question: > --------- > Given a pair of positive integers (n,k), when does there exist a homogeneous graph G such that > > * every vertex has valence n, and > > * every vertex has just k vertices that are not adjacent to it > > ??? I left out your definition of "homogeneous" (which is an interesting definition; I would be surprised if this concept didn't already exist in graph theory, possibly under some other name) because your conjecture is false even if you remove the word "homogeneous". if n and k are both odd, then you are looking for a graph with n+k+1 vertices, each of which has odd degree, which is impossible. -----

1 0

Re: [math-fun] Random integers
by Dan Asimov 13 May '20

13 May '20

Michael Collins wrote: ----- I think the "symmetry" argument is destroyed by the non-constructive choice of A; i.e. I suspect there are some A which would assign non-zero probability to 37, some which select an even integer with probability other than 1/2 et cetera. ----- No. Regardless of what problems this method may have, asymmetry between different integers is not one of them. Recap of method: ---------------- Identify the circle R/Z with the half-open interval [0, 1). Then R/Z is partitioned into subsets {A_n | n in Z} whose disjoint union is R/Z and which are all rotated versions of each other. That allows this theoretical method for picking a random integer: Pick x at random from the half-open interval [0, 1). Then x lies in A_n for a unique integer n. That n is the random integer. ---------------- (( In fact, there is a certain subset A of R/Z such that — for a fixed choice of irrational (say it's sqrt(2)) — the A_n's are each defined as A_n = A + n*sqrt(2) (modulo 1) for all n in Z. )) This means, e.g., that if we defined E = the union of the A_n's for n even and O = the union of the A_n's for n odd then the disjoint union of E and O is R/Z and they are rotated versions of each other. (Similarly if for some K in Z+ we took the union of A_n for all n == j (mod K) for j = 0, 1, ..., K-1.) So there's no assymetry between different integers. —Dan

2 1

Re: [math-fun] Binet's formula
by Dan Asimov 13 May '20

13 May '20

Even more than Binet's formula I like the closely related fact that F_n = round(phi^n/ sqrt(5)) where round(x) = floor(x + 1/2). —Dan

2 1

[math-fun] Random integers
by Dan Asimov 13 May '20

13 May '20

The concept of picking just one point at random from a probability distribution is not a rigorous mathematical concept, although maybe it could be made rigorous. Or maybe for some reason it cannot be. One bit of mathematical folklore is that there's no such thing as a random integer, if all integers are treated symmetrically. I have long felt skeptical of this claim. Here is one reason: Let 𝛼 denote an irrational number. For definiteness, say 𝛼 = sqrt(2). Let C = R/Z denote the (unit-circumference) circle group. Let g_n denote the element g_n = n*𝛼 (mod 1) in C. Then G = {g_n in C | n in Z} forms a countable dense subgroup of C. There is a well-defined group isomorphism J : G —> Z taking g_n in G to the integer n in Z. The cosets C/G = {x + G | x in C} of G form an uncontable quotient group that is rarely if ever discussed among decent mathematicians. Let A denote a set consisting of exactly one element from each coset x + G. Then the subsets A_n = A + g_n of G form a partition of G by countably many sets that are rotated versions of each other. The mapping phi : C —> Z defined as phi(x) = n where n is the unique integer such that x belongs to A_n. Finally, since it is generally accepted that one can select a point at random from the uniform distribution on the unit interval [0, 1), which we identify with C, suppose this is done and the point selected is x. Then a random integer is phi(x). By symmetry, all integers are treated equally. —Dan

3 2

[math-fun] Two graphs (update)
by Éric Angelini 13 May '20

13 May '20

Hello Math-Fun, I have rewritten 66% of my page, getting rid of everything related to the graph theory. I hope this is more clear now -- and wish someone will grow more "mini-trees". https://cinquantesignes.blogspot.com/2020/05/two-graphs-with-distinct-verti… Best, É.

1 0

[math-fun] Binet's formula
by rcs＠xmission.com 13 May '20

13 May '20

(from Bernie Cosell <bernie(a)fantasyfarm.com>) (The list filtering software intercepted this message, without telling me why. I've retyped the formulas. --rcs) Binets formula for the Fibonacci numbers follows fairly easily from the assumption that F_n=x^n, but I didnt quite follow how/why one would make that guess. I tried to see if I could come up with Binets formula not guessing that form. Instead I tried a finite polynomial F_n = sum(i=0,n,a_i*x^i). But then Im stuck. Id love to have discovered that this implies a_i=0 for all i/=n and a_i=1 for i=n and then Binets formula follows. But I cant quite figure that out. When I take that summation and plug it into F_n = F_(n-1) + F_(n-2) the best I can come up with a_n x^n = F_(n-2), which doesnt look promising. What am I missing? I know this isn't much "fun" but for odd reasons I've been revisiting math stuff that seemed obvious to me 50+ years, but has lain dormant. Thanks /bernie\ Bernie Cosell bernie(a)fantasyfarm.com -- Too many people; too few sheep --

4 3

[math-fun] Pauli-Covid Exclusion Principle
by Henry Baker 13 May '20

13 May '20

Each filled discrete energy level must be separated from every other filled discrete energy levels by 5 unfilled energy levels. --- (Lame, I know. But it's too early in the morning...)

9 10

Re: [math-fun] Cross-My-Primes
by Keith F. Lynch 12 May '20

12 May '20

Eric Angelini <bk263401(a)skynet.be> wrote: > this game (hope not old hat) is played on a Scrabble board where all > squares are white, and no square has any text on it. The starting > "star" square, in the center of the grid, has a 7 on it (the number, > not the word, as this game is played with digits only that will form > numbers ? instead of letters forming words). > The single player must now form prime numbers at every turn on the > board ? at the first turn placing the integer 1, at the second turn > placing 2, then 3, then 4, then 5, etc. Interesting. But why not keep as many rules of Scrabble as possible? Two alternating players, non-blank board, random selection of seven tiles, allowed to play any number of tiles in a straight line, no checking the "dictionary" during a game unless to challenge the opponent's alleged word or prime, etc.? The main problem with this game, as with yours, is that very few people have memorized vast numbers of primes. Your proposed game inspired me to look into building up primes one digit at a time, with every partial result being a prime. I learned that numbers built only leftwards are called left-truncatable primes (A024785), and numbers built only rightwards are called right-truncatable primes (A024770). There are exactly 4260 left-truncatable primes, the largest of which is 35768631264621656762913 (25 digits). (That's in base 10. In base 24, there are about a billion of them.) There are exactly 83 right-truncatable primes, of which the largest is 73939133. Fifteen primes are both left- and right-truncatable; the largest is 739397. The largest prime of which every substring is a prime is 373. But what I'm really looking for is a prime from which any number of digits can be removed, one at a time, from either the left or the right, in any order, without ever giving a non-prime. A137812, with 149677 terms, ending with 8939662423123592347173339993799, seems to be claiming to be such a sequence, but it includes terms that end with 1 or with 9, which are of course not prime. Nor is 99, which that largest term ends with, nor is 8, which it begins with, so I must be misundertanding what that sequence is. Is my proposed sequence not yet in OEIS? Since it could end with any of its digits, every digit must be 2, 3, 5, or 7, and only the leftmost digit could be 2 or 5. On second thought, that's not what I'm looking for, since I'm building primes, not taking them apart, and I can build them in any (gap-free) order. So maybe A137812 is what I'm looking for. But if so, it's phrased rather unclearly.

2 1

[math-fun] Two graphs
by Éric Angelini 12 May '20

12 May '20

Hello Math-Fun, (full text and illustrations on my personal blog page here: https://cinquantesignes.blogspot.com/2020/05/two-graphs-with-distinct-verti…) The idea is to build a planar graph with distinct positive integers k at every vertex – this integer being the exact number of edges linking the node k to the graph. (Pardon my ignorance of the precise words but my knowledge in graph theory is close to –273.15°C.) Both (uncompleted) graphs showed here don't admit that an edge crosses another (a good example is known as the Three utilities problem): someone walking from a vertex to another must not meet any crossroad. The first graph is above and is called (by me) the Maxi-graph. We want indeed this graph to show the maximum number of edges compatible with the constraint. We have: 1 linked to 2, 2 linked to 1 and 3, 3 inked to 2, 4 and 5, 4 linked to 3, 6, 7 and 8, 5 linked to 3, 9, 10, 11 and 12, 6 linked to 4, 13, 14, 15, 16 and 17, 7 linked to 4, 18, 19, 20, 21, 22 and 23, 8 linked to 4, 24, 25, 26, 27, 28, 29 and 30, 9 linked to 5, ... etc. We could have drawn a few shortcuts (linking 5 to 8, for instance) – but no! this is precisely what the Maxi-graph is about: building as many roads as possible! The second graph is the Mini-graph – we take into account the environmental costs of asphalt and concrete; we want, as before, to build a graph starting with 1, than linking 1 to 2, then linking this 2 to another node (3), then link the node 3 to 4 and 5... with a first divergence here from the Maxi-graph: 4 will be linked to 3, as before, but also to 5! (and to 6 and 7). Here is how the Mini-graph looks (for the first 11 vertices) (...) Best, É.

1 0

[math-fun] 3-smooth numbers #2 -- near a googolplex
by jacobs＠xmission.com 11 May '20

11 May '20

Blanket disclaimer: "if my calculations are correct, then ..." The largest 3-smooth number that is less than 10^(10^100) is (2^i * 3^j) with exponents: i = 5240457667536011553835317450277728970934205468247636517564762249075461811464263633070239562599567131 j = 17652672078113695646780517281391322686756289658776623674452938609239119167653573777408804025286004169 The next larger 3-smooth number, the smallest greater than 10^(10^100) is (2^i * 3^j) with exponents: i = 27911468858263353241606509519002899665982732517683148866824387638854242548327309121999804414370453492 j = 3348856574332340113860690779192481010573144504681280790577562072532814236920588073281466383293377609 The count of 3-smooth numbers below 10^(10^100) is: 348121998551416012668317959038480349279883545263691567113007477174736072507536976909539413592707867929651180140491194903602707766209055905884337013518535303190734936825129889519635109995577520171302547 Incredibly, Ramnujan's approximation is a mere 18 below this. My counting function computes (n = indx(i, j)) as the index in A003586(n) for entry (2^i * 3^j). The first key to making this computation quickly is to use a result by Donald J. Mintz, from "2,3 Sequence as Binary Mixture", The Fibonacci Quaterly Volume 19, 351-360, 1981. Mintz calls his counting function Ord(a, b), which is indexed starting from 0 rather than from 1. His Theorem 9 states: Ord(a,b) = a*b + Ord(a,0) + Ord(0,b) My equivalent relationship is: indx(i,j) = i*j + indx(i,0) + indx(0,j) - 1 where the -1 is a consequence of starting the index at 1. I use two auxillary functions which happen to correspond directly to OEIS entries: indx(i,j) = i*j + i_indx(i) + j_indx(j) - 1 where i_indx(i) is A022331 j_indx(j) is A022330 This is a pretty good start, because it reduces the evaluation of any point in the I-J plane to a single multiplication plus one evaluation on each of the I-J axes. The trick to making i_indx() and j_indx() efficient is to exploit Pick's Theorem. Pick's Theorem is used to count vertices in and on a triangle with vertices {(0,0), (i,0), (j,0)}. However, there are constraints for using Pick's Theorem to count 3-smooth numbers. The simplest case where Pick's Theorem applies is when (i,0) and (j,0) are at opposite ends of a single hop. An example of this is shown below: 2295: (84 0) [-84 53]15 19342813113834066795298816 2296: (0 53) [65 -41]10 19383245667680019896796723 The first time that hop [-85 53]15 appears in the hop sequence is at index 2295, where (84,0) is followed immediately by (0,53), so that the diagonal of the triangle is covered by a single hop. I use alpha(h) to refer to the first appears of hop(h) in the hop sequence that generates 3-smooth numbers. In simple cases where the diagonal corresponds to a single hop, Pick's Theorem can be formulated as: pick(i,j) = 1 + ((i + 1) * (j + 1) / 2) Since the hop corresponds to a convergent of the CF of log_2(3), the numerator and denominator are relatively prime, so they cannot both be even. Thus at least one of (i+1), (j+1) is even, and dividing the product by 2 leaves a whole number. Pick's Theorem is applied after the hop so that all of the vertices are included in the count. So in this case: j_indx(53) = pick(84,53) = 1 + (85 * 54 / 2) = 2296 i_indx(84) = j_indx(53) - 1 When Pick's Theorem applies, the computations are very fast, since the only operations involved are three increments, one multiplication, and a division which can be implemented as an integer right shift. All the calculations are integers, so no expensive floating point operations are needed. There are slightly more complicated cases where Pick's Theorem can be used. Triangles of the form {(0,0), (t*i,0), (0,t*j)} can sometimes be counted using Pick's Theorem, as shown in the example below: 9041* (168 0) [-84 53]15 374144419156711147060143317175368453031918731001856 9042* (84 53) [-84 53]15 374926498489468450744392093558119645344593994579968 9043* (0 106) [149 -94]11 375710212613636260325580163599137907799836383538729 In this case, the sequence starts at (168,0) and two identical hops [-84 53]15 are used to "skip" to (0,106). In cases with (t > 1), Pick's Theorem can be cast in the form: pick(i,j,t) = 1 + ((t * (i*(t*j + 1) + j + 1) / 2) so that j_indx(j) = pick(i,j,t) = 1 + (2 * (84*(2*53 + 1) + 53 + 1) / 2) = 9043 i_indx(i) = j_indx(j) - t = 9041 There are very few cases where Pick's Theorem can be applied to counting vertices in a true right triangle in the I-J plane. These rare case happen to be related to the "hop rectangles" that I described in post #1. In total, only about 2150 of these cases exist below the googolplex upper bound. Half correspond the hops that start from the I axis and land on the J axis, and half correspond to hops that start from the J axis and land on the I axis. The final step to optimizing i_indx() and j_indx() exploits the Pick-able cases by decomposing the set of vertices into a small number of rectangles combined with Pick-able triangles. I'll try to describe that process in post #3.

1 0