Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTo count clean triangles we count on $imph(n)$
61
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A clean lattice triangle in ${mathbb R}^2$ is a triangle that does not contain any lattice points on its sides other than its vertices. The central goal of this paper is to count the number of clean triangles of a given area up to unimodular equivalence. In doing so we use a variant of the Euler phi function which we call $imph(n)$ (imitation phi).
rate research
Read More
We illustrate the application of the matrix-transfer method for a number of enumeration problems concerning the party game Silent Circles, Hamiltonian cycles in the antiprism graphs, and simple paths and cycles of a fixed length in arbitrary graphs.
We use a sign-reversing involution to show that trees on the vertex set [n], considered to be rooted at 1, in which no vertex has exactly one child are counted by 1/n sum_{k=1}^{n} (-1)^(n-k) {n}-choose-{k} (n-1)!/(k-1)! k^(k-1). This result corrects a persistent misprint in the Encyclopedia of Integer Sequences.
Regular tree grammars and regular path expressions constitute core constructs widely used in programming languages and type systems. Nevertheless, there has been little research so far on frameworks for reasoning about path expressions where node cardinality constraints occur along a path in a tree. We present a logic capable of expressing deep counting along paths which may include arbitrary recursive forward and backward navigation. The counting extensions can be seen as a generalization of graded modalities that count immediate successor nodes. While the combination of graded modalities, nominals, and inverse modalities yields undecidable logics over graphs, we show that these features can be combined in a decidable tree logic whose main features can be decided in exponential time. Our logic being closed under negation, it may be used to decide typical problems on XPath queries such as satisfiability, type checking with relation to regular types, containment, or equivalence.
The counting of pairs of galaxies or stars according to their distance is at the core of all real-space correlation analyzes performed in astrophysics and cosmology. The next stage upcoming ground (LSST) and space (Euclid) surveys will measure properties of billions of galaxies and tomographic shells will contain hundreds of millions of objects. The combinatorics of the pair count challenges our ability to perform such counting in a minute-scale time which is the order of magnitude useful for optimizing analyses through the intensive use of simulations. The problem is not CPU intensive and is only limited by an efficient access to the data, hence it belongs to the big data category. We use the popular Apache Spark framework to address it and design an efficient high-throughput algorithm to deal with hundreds of millions to billions of input data. To optimize it, we revisit the question of nonhierarchical sphere pixelization based on cube symmetries and develop a new one that we call the Similar Radius Sphere Pixelization (SARSPix) with square-like pixels. It provides the most adapted sphere packing for all distance-related computations. Using LSST-like fast simulations, we compute autocorrelation functions on tomographic bins containing between a hundred million to one billion data points. In all cases we achieve the full construction of a classical pair-distance histogram in about 2 minutes, using a moderate number of worker nodes (16 to 64). This is typically two orders of magnitude higher than what is achieved today and shows the potential of using these new techniques in the field of astronomy on ever-growing datasets. The method presented here is flexible enough to be adapted to any medium size cluster and the software is publicly available from https://github.com/LSSTDESC/SparkCorr.
The Exact Satisfiability problem, XSAT, is defined as the problem of finding a satisfying assignment to a formula in CNF such that there is exactly one literal in each clause assigned to be 1 and the other literals in the same clause are set to 0. If we restrict the length of each clause to be at most 3 literals, then it is known as the X3SAT problem. In this paper, we consider the problem of counting the number of satisfying assignments to the X3SAT problem, which is also known as #X3SAT. The current state of the art exact algorithm to solve #X3SAT is given by Dahllof, Jonsson and Beigel and runs in $O(1.1487^n)$, where $n$ is the number of variables in the formula. In this paper, we propose an exact algorithm for the #X3SAT problem that runs in $O(1.1120^n)$ with very few branching cases to consider, by using a result from Monien and Preis to give us a bisection width for graphs with at most degree 3.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
