The telephone numbers obey a simple recurrence T(n) = T(n-1) + (n-1)T(n-2), and it's easy to test whether a prime number p divides at least one telephone number by running this recurrence modulo p. Whenever n is 1 mod p, the right hand side of the recurrence simplifies to T(n-1) mod p, and we get two consecutive numbers that are equal mod p; After that point, the recurrence continues as it would from its initial conditiions (two consecutive ones), multiplied mod p by some unknown factor. Therefore, the recurrence mod p either repeats exactly with period p, or it becomes identically zero (as it does for p=2), or it repeats with a higher period that is a multiple of p and a divisor of p(p–1), where all sub-periods of length p are multiples of each other. In particular, if p divides at least one telephone number, it divides infinitely many of them, whose positions are periodic with period p.
All primes divide at least one Fibonacci number (a sequence of numbers with an even simpler recurrence) but that is not true for the telephone numbers. For instance, the telephone numbers mod 3 form the infinite repeating sequence 1,1,2,1,1,2,... with no zeros. So how many of the prime numbers are in the new sequence? A heuristic estimate suggests that the telephone primes should form a 1–1/e fraction of all primes (around 63.21%): p is a telephone prime when there is a zero in the first p terms of the recurrence sequence mod p, and if we use random numbers instead of the actual recurrence then the probability of not getting a zero is approximately 1/e. With this estimate in mind, I tried some computational experiments and found that among the first 10000 primes, 6295 of them (approximately 63%) are in the sequence. Pretty accurate, I think! But I have no idea how to approach a rigorous proof that this estimate should be correct.
Incidentally, while looking up background material for this I ran into a paper by Rote in 1992 that observes a relationship between the telephone number and another sequence, A086828. A086828 counts the number of states in a dynamic programming algorithm for the traveling salesman problem on graphs of bandwidth k, for a parameter k. So its calculation, in the mid-1980s, can be seen as an early example of the parameterized analysis of algorithms. It has the same recurrence relation as the telephone numbers, but with different initial conditions, so we can consider using this sequence instead of the telephone numbers. But the same analysis above showing that all subperiods of length p are similar applies equally well to this sequence, showing that after an initial transient of length p, all subperiods are either identically zero or similar to the corresponding subperiods of the telephone numbers. So if we ask which primes divide at least one member of A086828, we get almost the same answer, except possibly for some additional primes that either divide one of the first p numbers of A086828 (and then no other members of A086828 later in the sequence) or that divide all but finitely many members of A086828.
- Reuleaux triangle, now a Wikipedia "good article" (G+)
- Triangle centers from curve shortening (MathOverflow question still missing a complete solution, but a lot of interesting partial results and discussion; G+)
- Rumors of Babai's graph isomorphism result (G+)
- Balancing understandability and pedantry in popular scitech writing (G+)
- A dubious similarity network of novelists, displaying the phenomenon that nearest-neghbor links are not bidirectional (G+)
- Southern California Theory Day, now past (G+)
- Advice from Valerie Barr on being a good feminist ally (G+)
- Reductio ad absurdum of "show your thinking" style math problems (G+)
- Petition to the EU to protest using gold-model open access as an excuse to redirect funding from researchers to publiishers (G+)
- Unification of random-walk and interior-point convex optimization (G+)
- Mathematical street art (G+)
- Can planets have corkscrew orbits? Greg Egan takes down an incautious 3-body analysis (G+)
- More women in science doesn't mean less sexism: the example of Argentinian astronomy (G+)
- The planted clique problem, part of a growing trend of interest in quasipolynomial time algorithmics (G+)
Another of the properties of the square and the equilateral triangle is that they are rep-tiles in many different way. Any square number of these tiles can be put together to make a larger copy. A rep-tile is said to be rep-k if it uses k tiles to tile its larger self; these shapes are rep-k for all square k. For tiles whose side lengths are all rational multiples of each other, that's the most versatile a rep-tile can be, because the side length of the larger copy is the square root of k. Let's say that a rep-tile is a pan-rep-tile if it has this same property, of being rep-k for all square k. Are there other pan-rep-tiles?
( Read more...Collapse )
- How big publishers are likely to co-opt the open access movement (G+)
- Famous puzzle becomes amusing short story (G+)
- Test how not-ready-for-prime-time your browser's MathML implementation is (G+)
- It's hard to convince men of gender bias in STEM (G+)
- Daniel Widrig's geometric sculpture (G+)
- Maria Chudnovsky's search for a combinatorial perfect graph coloring algorithm (G+)
- Thank you LaTeX stack exchange for having useful answers to everyday questions, this time about a bad interaction between hyperref, natbib, and dois in bibtex data (G+)
- Another article about Neil Sloane and the OEIS (G+)
- Wikipedia cites open-access journals more frequently than closed-access ones (G+)
- GF(2)-polynomial multiplication instructions lead to a fast XOR-universal hash function (G+)
- Three times the House Science Committee abused its subpoena power to hassle scientists it disagreed with (G+)
- Simple 4-polytopes without good separators (G+)
- Hollow heaps, a supposedly-simpler replacement for Fibonacci heaps (G+)
- SWAT (the Scandinavian Symposium and Workshops on Algorithm Theory) goes open-access with LIPIcs (G+)
- Polyhedral approximations of gyroids and the Laves graph (G+)
Unfortunately I didn't keep any shots from my favorite of the houses, an effort by Clemson involving a modular open-source design made out of aluminum composite panels, with amazingly lightweight but strong and attractive snap-together wooden furniture. It was also the only one to pack three bedrooms into the 1000 square foot limit for the enclosed part of the house.
Instead, here are some of the other houses, with annotations.
- Reversible cellular automaton, newly listed as a Wikipedia "Good Article" (G+)
- André Schulz's report from GD 2015, all the GD presentation slides, and Pat Morin's contest-winning freshman research project (G+)
- Lior Pachter's unsolved problems supplementing the Common Core (MF; G+)
- Dune trails on Mars (G+)
- Global coalition tells Facebook to kill its Real Names policy (G+)
- SODA formatting fixes (G+)
- Nature on Mochizuki's baffling ABC proof (Via; G+)
- The 120-cell and its decomposition into 12 rings of 10 dodecahedra (G+)
- How not to be ad-tracked by your Verizon cell-phone (G+)
- The collaborative and social nature of mathematics (G+)
- The WAVL tree data structure (G+)
- Augmented reality meets food psychology (G+)
- Serial sexual harasser resigns Berkeley professorship (G+)
- The importance of recreational mathematics (G+)
( Read more...Collapse )
An ongoing concern in graph drawing research has been curve complexity. If you draw a graph using a certain style, how complicated are you going to have to make the edges? More complicated curves are harder for readers to follow, and therefore they make the graph less readable. But simpler curves (such as line segments) may have their own problems: not fitting the style (which may constrain the edges to certain directions), running through vertices, forming sharp angles with each other, etc. To balance these concerns, a lot of work in graph drawing has allowed edges to be polygonal paths but has tried to prove hard upper bounds on how many bends you need to use. I'm not fond of polylines and bends myself — I prefer smooth curves such as circular arcs meeting at inflection points — but in this case one can measure the curve complexity in terms of the number of arcs you need per edge, and the theory ends up being much the same.( Read more...Collapse )
- UCI is #1 for low-income students (G+)
- Applications of convolutions in combinatorics (G+)
- Is it good to take advantage of free subscriptions to online information services for Wikipedia editors? (Yes. G+)
- A Helsinki street paved with Penrose tiles (G+)
- Colbert on diploma mills (G+)
- Realizing graphs as polyhedra (talk slides from my talk at the Graph Drawing satellite workshop; G+)
- Impact factors are bad and you should feel bad for using them (G+)
- Numberphile on the Houdini fold-and-cut trick (G+)
- Using the h-index to measure research productivity can lock in and amplify pre-existing gender biases (G+)
- Elsevier profiteers off open-access requirements, no longer usable by NSERC-funded researchers unless they pay thousands to get their own papers published (G+)
- Visualizing the space of simple closed curves in hyperbolic manifolds (G+)
It's also the first photo-op for my new cell phone, a Samsung Note 4 that I got a month or so ago after my old faithful Droid 2 Global finally gave up. I miss having an actual physical keyboard but the big screen and up-to-date software are both big improvements.
( Read more...Collapse )
One of Chernick's universal forms is the polynomial (6x + 1)(12x + 1)(18x + 1). This produces Carmichael numbers when x is 1, 6, 35, 45, 51, 55, 56, 100, ... (OEIS:A046025). By Dickson's conjecture there are infinitely many values of x that make all three factors prime and therefore infinitely many Carmichael numbers of this form. Not all of Chernick's universal forms are like this, but in this one all the irreducible factors are a monomial plus one. This property makes it particularly easy to test that the whole polynomial is one modulo each irreducible factor minus one: we need only test whether each of the leading monomials 6x, 12x, and 18x in the factors of the polynomial divides each of the non-constant monomials in the polynomial itself.
So what's special about (6,12,18) here? Do other triples of numbers work? Why or why not? Obviously, integer multiples of the same three numbers also work, but what about other triples that are not in the proportions (1,2,3)?
( Read more...Collapse )
Today's example: my lunch bill was $10.67. I knew that I had not very many coins, but I had more $1 bills than I wanted, and didn't have any $5 or $10 bills. So, I handed over $21. This confused the cashier so badly that she rang it up as if I had given her $11, realized her mistake, asked me if I knew that I had given her $21, and was unable to figure out what to give me in change (even with the difference between $11 and $10.67 visible on the register screen) without totally redoing the whole transaction from scratch.
But this led me to think about the following variations on the classical change-making problem. They might make good dynamic programming exercises, in part because it's less obvious how to use a greedy algorithm to solve them than it is to use a greedy algorithm for change-making.
Simplest change: given a payment amount, a set of coins (or bills) that can be used for the payment, and a (possibly different) set of coins/bills that can be used to make change, choose how much to pay in order to minimize the number of coins/bills you will get back in change.
Simplest transaction: with the same input data, choose how much to pay in order to minimize the total number of coins/bills that change hands in both directions. (Previously.)
Thinnest wallet: with the same input data, choose how much to pay in order to minimize the total number of coins/bills that you end up with after the transaction, including both your change and the coins and bills that you didn't use to pay the charge.
In all cases, let's assume that the cashier either knows how to give you the optimal change or can be guided by the register into doing so. I'd add another problem here, about choosing how to pay in order to minimize the transaction time and least annoy the math-phobic cashiers, but I'm sure using a credit card or debit card is the answer for that.
- Wikipedia paid editing and article protection money ring busted (G+)
- Faculty slots losing out to support staff at English unis (G+)
- Floor tile steganography at UCLA (G+)
- My new Wikipedia Book on matroid theory (G+)
- To square your photos or not to square your photos (G+)
- Karim Alexander Adiprasito, Zdeněk Dvořák, and Robert Morris win the European Prize in Combinatorics (G+)
- Computer science courses that don't exist, but should (G+)
- Soviet-era architectural sketches by Brodsky and Utkin (G+)
- Carol Wood can make up new and strange numbers because she's a model theorist (G+)
- Shelley James's geometric glass art + video (G+)
- Harry Potter and the set of all sets that do not contain themselves (G+)
- A nice algebraic explanation of the (3,7)-cage and its symmetries (G+)
- SODA accepted papers and abstracts (G+)
So this naturally raises some questions: is anonymization really possible? What can we do to scramble the data, and what useful information would we lose by doing it?
( Read more...Collapse )
( Read more...Collapse )
( Read more...Collapse )
- The Tutte–Coxeter graph and its construction from the outer automorphisms of S6 (G+)
- Google's S2 spatial data structure (G+)
- Question: how many arXiv papers are updated to their final journal versions? (Answer: about half of them have non-empty journal-reference metadata; G+)
- Keleti's conjecture on the ratio of perimeter to area of a union of unit squares (G+)
- Reference for mixed graph acyclicity testing? (Still not adequately answered, but the bounty has since expired; G+)
- Purifying spoiled randomness with spoiled randomness (G+)
- Six-tetrahedron kaleidocycles don't work (but it takes a computer simulation to demonstrate it, because paper ones do; G+)
- The new single-divisible-vote last-place-elimination scheme for Hugo nominations (or as they call it, e pluribus Hugo; G+)
- Wikipedia blocked in Russia over its refusal to take down information about illegal drugs (since unblocked; G+)
- The two cultures of CS: theory vs experiment (G+)
- Six points in general position in 3d can be partitioned into triples determining two linked circles (G+)
- Boulet imagines what physicists in a pixelated world might think of it (G+)
- Just because a formula looks mathy doesn't mean it makes any sense (G+)
- Google teaches spammers how to break security to get their ads through (G+)
- Hyde Al Dzhazil, Yemeni town built on a rock (G+)
- Constructing the Golay error-correcting code from a great dodecahedron (G+)