The game of subtract-a-square is played by two players with a pile of coins. They take turns taking a square number of coins until none are left. The last player to move wins. So how can we play this game optimally and efficiently? As it turns out, there's some deep number theory lurking in the answer.( Read more...Collapse ) Update: See a later post for some experiments on the growth rate of this set.
Climate change countermeasures and continued research.
A coordinated response to extreme climate events.
Regulation of carbon dioxide as a pollutant.
National parks and wildlife preserves.
Guaranteed health care.
State-level limits on how predatory the health care industry can be.
A recovering economy and continuing tech boom.
The minimum wage.
Social security and medicare.
The Supreme Court.
Abortion rights and access to contraception.
Anti-discrimination laws and same-sex marriage.
The truth defense from libel.
No wholesale legal persecution of opposition parties.
Restrictions on gun ownership.
Religious freedom for anyone other than Christians.
Limits on how blatantly Christianity can be used as an excuse for bigotry.
Redistricting rules that prevent continued gerrymandering.
Anything resembling adequate polling places in poor and minority districts.
Universal voter registration.
Pressure to reduce sexual harassment and sexual assaults in our universities, or anywhere else.
Reduced or free college tuition for anyone.
Any hope of reining in the out-of-control racists in our police forces.
Farm workers, housecleaners, construction workers, food service workers, and all those other people who do the things nobody else wants to do.
The ability to bring in talented students and workers from other countries.
NATO and the free Baltic states.
A president who wouldn't start a nuclear war based on a whim or personal slight.
Clinton could still pull this out, mathematically, but barring a miraculous turnaround in Wisconsin or Arizona there doesn't seem to be any remaining path to 270 electoral votes. And with the House and Senate in Republican hands and a free slot on the court there are no checks and balances left; the voters were the last line of defense.
Anyone in a nice safe part of the world looking for academic computer scientists? Canada? Iceland? New Zealand?
- Jörg Arndt's library and book of bit-manipulation programming techniques (G+)
- The geometric median of a solid triangle, another triangle center whose lack of closed form is keeping it out of ETC (G+)
- Rigid-origami variable-capacity measuring spoon (G+)
- "Easily the largest road-distance TSP that has been solved to date", a pub-crawl with 24727 stops (G+)
- High performance Java implementation of a Cuckoo filter (G+)
- OMICS conference accepts a paper written by autocomplete (G+)
- Matt Parker makes mathematical sculpture from office supplies (G+)
- The Rule 90 cellular automaton on Wikipedia (G+)
- 3d objects that look like Escher's impossible objects (G+)
- Dual graph on Wikipedia (G+)
- ArXiv uses Turnitin to detect plagiarized submissions; Turnitin gains access to arXiv content to detect plagiarism elsewhere (G+)
- Using the Strahler number to visualize watersheds (G+)
- The many women in computing who have been the the first X, no qualifier (G+)
- Five easy-to-state but hard-to-solve problems in mathematics (G+)
- Symmetries of the permutohedron (G+)
In Conway's Game of Life, and other cellular automata with the same neighborhood structure, you can determine the values of the cells in any 2x × 2x square of cells from their values x steps earlier in a bigger 4x × 4x square. If we view this as a time-space diagram, with two of the dimensions as the spatial dimensions of the Life grid and the third dimension as time, we can view the bigger starting square and the smaller resulting square as the bottom and top of a sort of stepped pyramid formed by stacking concentric squares. The values of the cells in each layer of the pyramid are determined by the ones in the layer below. The squares shrink inward as they rise upward, because the other cells outside the pyramid need more information (outside the base of the pyramid) to determine their values. The image below shows this construction for x = 1, 2, and 4, with each time-space state of a cell represented as a cube.
( Read more...Collapse )
- Restoring the St. John Altarpiece...with mathematics! (G+)
- Nonconvex equilateral hecatontetracontahedron (G+)
- Sets of seven non-cocircular points with integral distances (G+)
- Biographies of prominent Latin and Hispanic mathematicians (G+)
- UK cuts off the flow of foreign students, because British higher education hasn't imploded quickly enough in the wake of Brexit and needs a push (G+)
- DNA origami: programmable matter for making nano-scale shapes and structures (G+)
- How political hoaxes spread on twitter (G+)
- The McGee graph animated in 3d to show off its symmetries (G+)
- 2-satisfiability, now a Good Article on Wikipedia (G+)
- OMICS hijacks two previously-reputable publishers and their journals (G+)
- The Reuleaux triangle tetrahedron, what you get if you glue four Reuleaux triangles edge-to-edge (G+)
- Symposium on Computational Geometry call for papers (abstracts Nov. 28, papers Dec. 5; G+)
- The McGee graph, again, as a non-rigid unit distance graph (G+)
After posting about a recursive generator for the Kolakoski sequence yesterday, I found the following alternative and non-recursive algorithm, which generates the same sequence in a linear number of bit operations with a logarithmic number of bits of storage.
def Kolakoski(): x = y = -1 while True: yield [2,1][x&1] f = y &~ (y+1) x ^= f y = (y+1) | (f & (x>>1))
Like the previous one, this can be understood as traversing an infinite tree. The tree is defined using essentially the same rules as before: two consecutive nodes on the same level of the tree have the same number of children if and only if they have the same parent. However, it extends infinitely upward rather than infinitely downward, with two children for each node on the leftmost path. Each level of the tree has the same sequence of degrees, which equals the Kolakoski sequence starting from its second position (the missing first position is why this starts at x = y = -1 rather than zero).
The algorithm traverses the bottom level of the tree in left-to-right order. As it does, the variable x maintains, in its binary representation, the numbers of children modulo 2 of the path of nodes extending infinitely upwards from the current leaf. All but finitely many (logarithmically many as a function of the position of the leaf) of these bits are zero, so (after the first step) x is a non-negative finite number with logarithmically many bits. The variable y, similarly, maintains a sequence of bits corresponding to the nodes on the same path that are 0 when the node is a left child of a degree-2 node and 1 otherwise. Again, finitely many of these bits are 1, so y is non-negative with logarithmically many bits. The bit manipulation tricks of the algorithm merely update these two variables to describe the next path in the traversal.
Update 10/16: Fast C++ implementation by Jörg Arndt
Draw an infinite tree according to the following rules:
- Each tree node is labeled 1 or 2, and has a number of children equal to its label.
- If the nodes are placed into their breadth-first search ordering, then two consecutive nodes have the same label if and only if they have the same parent.
There are two choices for the root label, but the trees they produce are almost the same as each other, so let's say the root is labeled 2, giving the tree shown below together with its spiraling breadth first search order. (If the root were labeled 1, the only difference would be to add one more node labeled 1 above the node that is the root in the drawing.)
Then the breadth-first sequence of labels that we obtain is exactly the Kolakoski sequence, starting from its third term. The Kolakoski sequence begins 1,2,2,1,1,2,1,2,2,1,2,2... and has the property that it equals the sequence of run-lengths in itself: the numbers 1, 2, 2, etc. are exactly the numbers of consecutive 1's, 2's, 1's, etc. in the sequence. Our tree is defined in such a way that each run of consecutive equal labels comes from the same parent, so the run-lengths of the sequence equal the numbers of children of the nodes, which equal the labels of the nodes, which define the sequence itself.( Read more...Collapse )
ETA: See next post for an alternative algorithm that avoids the recursion.
( Read more...Collapse )
- Geometric Watercolors by artist Jacob Van Loon (G+)
- Congressman Lamar Smith's campaign of intimidation against global-warming researchers (G+)
- Irvine has become the largest predominantly-Asian city in the continental US — yay diversity! (G+)
- Online course materials must be accessible to the blind and the hearing impaired; uncaptioned videos are not good enough (G+)
- Search engine for free versions of papers from their DOIs (G+)
- Subhash Khot declared a genius (G+)
- Disappearing national forests on online maps highlight our dependence on an information monoculture in the cloud (G+)
- College students help edit Wikipedia (G+)
- Levels of space-filling curves as cross-sections of a 3d-printed surface (G+)
- Winner of the draw-the-Greek-gods'-genealogy contest and others from Graph Drawing (G+)
- Canon DSLR telephoto lens array as a serious astronomical instrument (G+)
- Distinguish the additive reals from the rationals in monadic second-order logic (G+)
- Female chess championship contenders protest being forced to wear hijabs (G+)
- EFF tells court that DMCA's preventing publication of academic crypto research should be unconstitutional (G+)
( Read more...Collapse )
- "Provably" considered harmful (G+)
- Superresolution image enhancement through deep learning (G+)
- Isohedral isosceles-triangle torus (G+)
- 30x bigger impact factor still not enough to give your paper a statistically significant chance of more citations (G+)
- Forbidden minors for infinite DFS trees depend on set-theoretic axioms (G+)
- Why non-deplorable people should avoid saying they have 88 of anything (G+)
- Premature death of geometric artist Alba Rojo Cama (G+)
- Graph Drawing 2016 proceedings mirror (G+)
- Noam Nisan wins Knuth Prize (G+)
- Short video on how the Royal Society is trying to move away from being a boys-only club (G+)
- Open-access legal quagmire re making a preprint available and then signing away copyright (G+)
- OpenStreetMap demo of k-shortest paths in a road network (G+)
- Optimal packing in the plane for regular pentagons (G+)
- More than phi: Mathematical artist Lun-Yi London Tsai captures the feel of mathematicians' blackboards (G+)
My own paper "Upright-quad drawing of st-planar learning spaces" described an analogous geometric representation for antimatroids (which in this context can be seen as another special type of lattice). So a recent CS-theory stack-exchange question about planar modular graphs got me wondering: what do the graphs of 2-dimensional modular lattices (a subclass of the planar modular graphs) look like?
( Read more...Collapse )
- Honeycomb generated by interlocking hexagonal tilings (G+)
- Computer-written new Wikipedia articles didn't work as well as the programmers thought (G+)
- Woody Blackwell's portfolio of glass and stone knapping (G+)
- A more mathematically interesting five-ring link than the Olympic one (G+)
- 102-year-old researcher and honorary professor forced off campus (G+)
- A newspaper article from the early days of pioneering computer programmer Dame Stephanie Shirley (G+)
- A report from the 6th meeting on Origami, Science, Math, and Education (G+)
- Self-similar colorings of aperiodic tilings (G+)
- Counting grid graph matchings by continued fractions (G+)
- US FTC takes action against predatory scientific publisher OMICS (G+)
- A mathematical history of taffy pullers (G+)
- Feds use Rand formula to spot discrimination; the GOP calls it junk science (G+)
- Congratulations to Andreas Björklund, Nerode prize winner 2016 (G+)
- The geometric models collection of V. N. Karazin Kharkiv National University, Ukraine (G+)
- Elsevier patents online peer review (G+)
( Read more...Collapse )
- Cap sets on Wikipedia (mathematical models of stuck games of Set; G+)
- A unified theory of random shapes (G+)
- Visualization of star polyhedra as surfaces of nonzero genus (G+)
- Game theory weirdness (G+)
- Ventricle by softlab, hanging meshed membrane artwork (G+)
- A publishing industry association tries to spread FUD over open-access research (G+; see also MF)
- Marie Curie and the underground university for women (G+)
- Stone hypar stereotomy (G+)
- Run Logo programs in your browser (G+)
- Internet access is a human right which India is violating (G+)
- Leopold Blaschka's glass sea creatures (G+)
- Peacock feather macrophotography (G+)
- Force polygons of equilibrium structures (G+)
( Read more...Collapse )
- "Minimum forcing sets for Miura folding patterns", SODA 2015.
- "Finding all maximal subsequences with hereditary properties", SoCG 2015.
- "Contact graphs of circular arcs", WADS 2015.
- "Rooted cycle bases", WADS 2015.
- "The parametric closure problem", WADS 2015.
- "Genus, treewidth, and local crossing number", GD 2015.
- "Treetopes and their graphs", SODA 2016.
- "On the planar split thickness of graphs", LATIN 2016.
- "From discrepancy to majority", LATIN 2016.
- "Cuckoo filter: simplification and analysis", SWAT 2016.
- "Maximizing the sum of radii of disjoint balls or disks", CCCG 2016.
- Kate Claghorn, forgotten giant of the Progressive Era (G+)
- latexmathjax, turn latex sources into nicely formatted web pages by putting them in the same folder as a short html stub (G+)
- The physics of wrinkles vs dimples (G+)
- The post-coup crackdown in Turkey extends to higher education (G+)
- A plagiarism rubric, or maybe a catalog of excuses (G+)
- Curved folds by Polly Verity (G+)
- Fellows of the American Statistical Association (G+)
- ICALP business meeting report with discussions on the health of Track C and on strictness of proceedings formatting (G+ with more discussion)
- Wikileaks squanders its legacy for a mess of pottage (G+)
- Former refugee Sara Zahedi and the other winners of the EMS Prize (G+)
- Accepted papers for Graph Drawing (G+)
- Fighting anti-women discrimination in science in 1999 (G+)
- Astronomy photo of the year candidates (G+)
- Reversible logic unnecessary for ultra-low power (G+)
- When AIs learn language from human texts, they pick up human sexism (G+)
- Promotional video on the algorithmic design of caustics (G+)
- Squircle illusion: now 3d printing can make things round and square at the same time (G+)
- The latest wonders of mathematical art from Bridges 2016 (G+)
- CCCG accepted papers (or now there's an actual schedule; G+)
- Low faculty uptake of the University of California's all-subjects open access repository (G+, many good comments)
- 20-minute nontechnical video documentary about recent hacking culture (G+)
- How can you divide a square into finitely many similar acute triangles? (G+)
- No article can be judged on the basis of the Impact Factor of the journal in which it is published (G+)
- Uniformly-spaced point sets in nature (see also Wikipedia on Delone sets; G+)
- A trickier variant of the 4 4's puzzle (G+, with spoilers in the comments)
- Researchers keeping a low online profile in the face of persistent harassment of anyone who criticizes misogyny in computer gaming (G+)
( Read more...Collapse )