**consider:looking-to-see**696

Quickly recognizing primes less than 100 | The Math Less Traveled

2 days ago by Vaguery

Recently, Mark Dominus wrote about trying to memorize all the prime numbers under . This is a cool idea, but it made me start thinking about alternative: instead of memorizing primes, could we memorize a procedure for determining whether a number under is prime or composite? And can we make it clever enough to be done relatively quickly? This does tie into my other recent posts about primality testing, but to be clear, it’s also quite different: I am not talking about a general method for determining primality, but the fastest method we can devise for mentally determining, by hook or by crook, whether a given number under is prime. Hopefully there are rules we can come up with which are valid for numbers less than —and thus make them easier to test—even though they aren’t valid for bigger numbers in general.

mathematical-recreations
number-theory
heuristics
nudge-targets
consider:looking-to-see
to-write-about
2 days ago by Vaguery

The Kolakoski Sequence - Futility Closet

9 days ago by Vaguery

This is a fractal, a mathematical object that encodes its own representation. It was described by William Kolakoski in 1965, and before him by Rufus Oldenburger in 1939. University of Evansville mathematician Clark Kimberling is offering a reward of $200 for the solution to five problems associated with the sequence:

Is there a formula for the nth term?

If a string occurs in the sequence, must it occur again?

If a string occurs, must its reversal also occur?

If a string occurs, and all its 1s and 2s are swapped, must the new string occur?

Does the limiting frequency of 1s exist, and is it 1/2?

So far, no one has found the answers.

mathematical-recreations
self-reference
fractals
open-questions
nudge-targets
consider:looking-to-see
Is there a formula for the nth term?

If a string occurs in the sequence, must it occur again?

If a string occurs, must its reversal also occur?

If a string occurs, and all its 1s and 2s are swapped, must the new string occur?

Does the limiting frequency of 1s exist, and is it 1/2?

So far, no one has found the answers.

9 days ago by Vaguery

Efficiency of repeated squaring | The Math Less Traveled

10 days ago by Vaguery

Claim: the binary algorithm is the most efficient way to build using only doubling and incrementing steps. That is, any other way to build by doubling and incrementing uses an equal or greater number of steps than the binary algorithm.

algorithms
mathematical-recreations
nudge-targets
consider:looking-to-see
to-write-about
10 days ago by Vaguery

[1602.06208] Every positive integer is a sum of three palindromes

17 days ago by Vaguery

For integer g≥5, we prove that any positive integer can be written as a sum of three palindromes in base g.

number-theory
proof
nudge-targets
consider:algorithms
consider:looking-to-see
17 days ago by Vaguery

[1808.05845] Popular Products and Continued Fractions

4 weeks ago by Vaguery

We prove bounds for the popularity of products of sets with weak additive structure, and use these bounds to prove results about continued fractions. Namely, we obtain a nearly sharp upper bound for the cardinality of Zaremba's set modulo p.

continued-fractions
number-theory
to-write-about
nudge-targets
consider:looking-to-see
4 weeks ago by Vaguery

SMT solutions | The Math Less Traveled

8 weeks ago by Vaguery

In my last post I described the general approach I used to draw orthogons using an SMT solver, but left some of the details as exercises. In this post I’ll explain the solutions I came up with.

geometry
programming
rather-interesting
representation
testing
to-write-about
mathematical-recreations
nudge-targets
consider:looking-to-see
8 weeks ago by Vaguery

Custom Baking - Futility Closet

9 weeks ago by Vaguery

Is it possible to bake a cake that can be divided into four parts by a single straight cut?

mathematical-recreations
simplicity
nudge-targets
consider:looking-to-see
consider:novelty-search
9 weeks ago by Vaguery

Dembo , Peres : A Topological Criterion for Hypothesis Testing

10 weeks ago by Vaguery

A simple topological criterion is given for the existence of a sequence of tests for composite hypothesis testing problems, such that almost surely only finitely many errors are made.

via:cshalizi
statistics
learning-from-data
algorithms
existence-proof
consider:looking-to-see
to-write-about
nudge-targets
10 weeks ago by Vaguery

Theorem of the Day

11 weeks ago by Vaguery

The list is presented here in reverse chronological order, so that new additions will appear at the top. This is not the order in which the theorem of the day is picked which is more designed to mix up the different areas of mathematics and the level of abstractness or technicality involved. The way that the list of theorems is indexed is described here.

mathematics
proof
lists
rather-interesting
nudge-targets
consider:looking-to-see
11 weeks ago by Vaguery

[1710.10964] At the Roots of Dictionary Compression: String Attractors

july 2018 by Vaguery

A well-known fact in the field of lossless text compression is that high-order entropy is a weak model when the input contains long repetitions. Motivated by this fact, decades of research have generated myriads of so-called dictionary compressors: algorithms able to reduce the text's size by exploiting its repetitiveness. Lempel-Ziv 77 is probably one of the most successful and known tools of this kind, followed by straight-line programs, run-length Burrows-Wheeler transform, and other less-known schemes. In this paper, we show that these techniques are different solutions to the same, elegant, combinatorial problem: to find a small set of positions capturing all distinct text's substrings. We call such a set a string attractor. We first show reductions between dictionary compressors and string attractors. This gives us the approximation ratios of dictionary compressors with respect to the smallest string attractor and allows us to solve several open problems related to the asymptotic relations between the output sizes of different dictionary compressors. We then show that the k-attractor problem - that is, deciding whether a text has a size-t set of positions capturing all substrings of length at most k - is NP-complete for k >= 3. We provide approximation techniques for the smallest k-attractor, show that the problem is APX-complete for constant k, and give strong inapproximability results. To conclude, we provide matching lower- and upper- bounds for the random access problem on string attractors. Our optimal data structure is universal: by our reductions to string attractors, it supports random access on any dictionary-compression scheme. In particular, our solution matches the lower bound also on LZ77, straight-line programs, collage systems, and macro schemes, and therefore essentially closes (at once) the random access problem for all these compressors.

compression
strings
feature-extraction
representation
algorithms
computational-complexity
to-understand
nudge-targets
consider:looking-to-see
july 2018 by Vaguery

[1805.07980] Collisionless periodic orbits in the free-fall three-body problem

may 2018 by Vaguery

Although the free-fall three-body problem have been investigated for more than one century, however, only four collisionless periodic orbits have been found. In this paper, we report 234 collisionless periodic orbits of the free-fall three-body system with some mass ratios, including three known collisionless periodic orbits. Thus, 231 collisionless free-fall periodic orbits among them are entirely new. In theory, we can gain periodic orbits of the free-fall three-body system in arbitrary ratio of mass. Besides, it is found that, for a given ratio of masses of two bodies, there exists a generalized Kepler's third law for the periodic three-body system. All of these would enrich our knowledge and deepen our understanding about the famous three-body problem as a whole.

nonlinear-dynamics
stamp-collecting
rather-interesting
nudge-targets
consider:looking-to-see
consider:performance-measures
may 2018 by Vaguery

[1805.02436] Combining Tools for Optimization and Analysis of Floating-Point Computations

may 2018 by Vaguery

Recent renewed interest in optimizing and analyzing floating-point programs has lead to a diverse array of new tools for numerical programs. These tools are often complementary, each focusing on a distinct aspect of numerical programming. Building reliable floating point applications typically requires addressing several of these aspects, which makes easy composition essential. This paper describes the composition of two recent floating-point tools: Herbie, which performs accuracy optimization, and Daisy, which performs accuracy verification. We find that the combination provides numerous benefits to users, such as being able to use Daisy to check whether Herbie's unsound optimizations improved the worst-case roundoff error, as well as benefits to tool authors, including uncovering a number of bugs in both tools. The combination also allowed us to compare the different program rewriting techniques implemented by these tools for the first time. The paper lays out a road map for combining other floating-point tools and for surmounting common challenges.

numerical-methods
algorithms
optimization
rather-interesting
floating-point
representation
to-understand
nudge-targets
consider:looking-to-see
may 2018 by Vaguery

[1805.02274] On the $f$-Matrices of Pascal-like Triangles Defined by Riordan Arrays

may 2018 by Vaguery

We define and characterize the f-matrices associated to Pascal-like matrices that are defined by ordinary and exponential Riordan arrays. These generalize the face matrices of simplices and hypercubes. Their generating functions can be expressed simply in terms of continued fractions, which are shown to be transformations of the generating functions of the corresponding γ- and h-matrices.

combinatorics
continued-fractions
topology
to-understand
to-write-about
nudge-targets
consider:looking-to-see
may 2018 by Vaguery

[1607.01117] Anagram-free Graph Colouring

may 2018 by Vaguery

An anagram is a word of the form WP where W is a non-empty word and P is a permutation of W. We study anagram-free graph colouring and give bounds on the chromatic number. Alon et al. (2002) asked whether anagram-free chromatic number is bounded by a function of the maximum degree. We answer this question in the negative by constructing graphs with maximum degree 3 and unbounded anagram-free chromatic number. We also prove upper and lower bounds on the anagram-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and k-anagram-free colouring.

graph-theory
algorithms
graph-coloring
feature-construction
nudge-targets
consider:looking-to-see
computational-complexity
may 2018 by Vaguery

[1612.09443] Transversals in Latin arrays with many distinct symbols

may 2018 by Vaguery

An array is row-Latin if no symbol is repeated within any row. An array is Latin if it and its transpose are both row-Latin. A transversal in an n×n array is a selection of n different symbols from different rows and different columns. We prove that every n×n Latin array containing at least (2−2‾√)n2 distinct symbols has a transversal. Also, every n×n row-Latin array containing at least 14(5−5‾√)n2 distinct symbols has a transversal. Finally, we show by computation that every Latin array of order 7 has a transversal, and we describe all smaller Latin arrays that have no transversal.

combinatorics
existence-proof
rather-interesting
nudge-targets
consider:looking-to-see
may 2018 by Vaguery

[1708.09571] Anagram-free colourings of graph subdivisions

may 2018 by Vaguery

An anagram is a word of the form WP where W is a non-empty word and P is a permutation of W. A vertex colouring of a graph is anagram-free if no subpath of the graph is an anagram. Anagram-free graph colouring was independently introduced by Kam\v{c}ev, {\L}uczak and Sudakov and ourselves. In this paper we introduce the study of anagram-free colourings of graph subdivisions. We show that every graph has an anagram-free 8-colourable subdivision. The number of division vertices per edge is exponential in the number of edges. For trees, we construct anagram-free 10-colourable subdivisions with fewer division vertices per edge. Conversely, we prove lower bounds, in terms of division vertices per edge, on the anagram-free chromatic number for subdivisions of the complete graph and subdivisions of complete trees of bounded degree.

combinatorics
graph-theory
graph-coloring
computational-complexity
rather-interesting
nudge-targets
consider:looking-to-see
may 2018 by Vaguery

[1801.07155] Continued fractions and orderings on the Markov numbers

may 2018 by Vaguery

Markov numbers are integers that appear in the solution triples of the Diophantine equation, x2+y2+z2=3xyz, called the Markov equation. A classical topic in number theory, these numbers are related to many areas of mathematics such as combinatorics, hyperbolic geometry, approximation theory and cluster algebras.

There is a natural map from the rational numbers between zero and one to the Markov numbers. In this paper, we prove two conjectures seen in Martin Aigner's book, Markov's theorem and 100 years of the uniqueness conjecture, that determine an ordering on subsets of the Markov numbers based on their corresponding rational.

The proof uses the cluster algebra of the torus with one puncture and a resulting reformulation of the conjectures in terms of continued fractions. The key step is to analyze the difference in the numerator of a continued fraction when an operation is applied to its entries.

number-theory
continued-fractions
rather-interesting
to-write-about
consider:looking-to-see
consider:generalizations
There is a natural map from the rational numbers between zero and one to the Markov numbers. In this paper, we prove two conjectures seen in Martin Aigner's book, Markov's theorem and 100 years of the uniqueness conjecture, that determine an ordering on subsets of the Markov numbers based on their corresponding rational.

The proof uses the cluster algebra of the torus with one puncture and a resulting reformulation of the conjectures in terms of continued fractions. The key step is to analyze the difference in the numerator of a continued fraction when an operation is applied to its entries.

may 2018 by Vaguery

[1803.01422] DAGs with NO TEARS: Smooth Optimization for Structure Learning

april 2018 by Vaguery

Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian networks) is a challenging problem since the search space of DAGs is combinatorial and scales superexponentially with the number of nodes. Existing approaches rely on various local heuristics for enforcing the acyclicity constraint and are not well-suited to general purpose optimization packages for their solution. In this paper, we introduce a fundamentally different strategy: We formulate the structure learning problem as a smooth, constrained optimization problem over real matrices that avoids this combinatorial constraint entirely. This is achieved by a novel characterization of acyclicity that is not only smooth but also exact. The resulting nonconvex, constrained program involves smooth functions whose gradients are easy to compute and only involve elementary matrix operations. By using existing black-box optimization routines, our method uses global search to find an optimal DAG and can be implemented in about 50 lines of Python and outperforms existing methods without imposing any structural constraints.

graph-theory
combinatorics
algorithms
rather-interesting
computational-complexity
to-understand
to-write-about
nudge-targets
consider:looking-to-see
representation
april 2018 by Vaguery

[1801.00663] A Sharp Estimate for Probability Distributions

march 2018 by Vaguery

We consider absolutely continuous probability distributions f(x)dx on ℝ≥0. A result of Feldheim and Feldheim shows, among other things, that if the distribution is not compactly supported, then there exist z>0 such that most events in {X+Y≥2z} are comprised of a 'small' term satisfying min(X,Y)≤z and a 'large' term satisfying max(X,Y)≥z (as opposed to two 'large' terms that are both larger than z)

limsupz→∞ ℙ(min(X,Y)≤z|X+Y≥2z)=1.

The result fails if the distribution is compactly supported. We prove

supz>0 ℙ(min(X,Y)≤z|X+Y≥2z)≥124+8log2(med(X)‖f‖L∞),

where med(X) denotes the median. Interestingly, the logarithm is necessary and the result is sharp up to constants; we also discuss some open problems.

probability-theory
statistics
rather-interesting
nudge-targets
consider:looking-to-see
limsupz→∞ ℙ(min(X,Y)≤z|X+Y≥2z)=1.

The result fails if the distribution is compactly supported. We prove

supz>0 ℙ(min(X,Y)≤z|X+Y≥2z)≥124+8log2(med(X)‖f‖L∞),

where med(X) denotes the median. Interestingly, the logarithm is necessary and the result is sharp up to constants; we also discuss some open problems.

march 2018 by Vaguery

A hybrid placement strategy for the three-dimensional strip packing problem - ScienceDirect

march 2018 by Vaguery

This paper presents a hybrid placement strategy for the three-dimensional strip packing problem which involves packing a set of cuboids (‘boxes’) into a three-dimensional bin (parallelepiped) of fixed width and height but unconstrained length (the ‘container’). The goal is to pack all of the boxes into the container, minimising its resulting length. This problem has potential industry application in stock cutting (wood, polystyrene, etc. – minimising wastage) and also cargo loading, as well as other applications in areas such as multi-dimensional resource scheduling. In addition to the proposed strategy a number of test results on available literature benchmark problems are presented and analysed. The results of empirical testing of the algorithm show that it out-performs other methods from the literature, consistently in terms of speed and solution quality-producing 28 best known results from 35 test cases.

operations-research
hyperheuristics
metaheuristics
optimization
constraint-satisfaction
nudge-targets
consider:representation
consider:looking-to-see
to-write-about
march 2018 by Vaguery

**related tags**

Copy this bookmark: