The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
0answers
716 views

How many 2L-bit numbers are the product of two L-bit numbers?

If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective. I am interested in the size of ...
5
votes
0answers
393 views

Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and $b$ are natural numbers. For example, this set of ...
5
votes
0answers
611 views

On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
4
votes
0answers
208 views

Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions. Call a lattice ...
3
votes
0answers
119 views

Citation for subset complement result

Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* ...
3
votes
0answers
97 views

Are there existing resources on modular-esque recurrence relations?

Does anyone know where I would be able to get information on analyzing a class of polynomial recurrence relations of a form like this? $\begin{align*} f_{n,k}(x) & ...
3
votes
0answers
130 views

A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?

Hello, What is a fast way to test whether a partial function can be extended to a chirotope of rank 3 ? That is: I have a domain $E = \{1,...,n\}$ and a partial function $f: E^3 \to \{-1, 0, 1\}$ ...
3
votes
0answers
657 views

Method for variable substitution in multiple summation

I want to ask: is there any general method for variable substitution in multiple summation? For example in the following equation a new variable $\lambda=n+m-2\mu$ is introduced to transform the LHS ...
2
votes
0answers
297 views

Guessing game with guess cost

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...
2
votes
0answers
141 views

Number of breakpoints in parametric maximum flow problems

The parametric maximum flow problem can be formulated as $$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right), $$ where all $c_{ij}<0$ (so that ...
1
vote
0answers
207 views

Trigonometric semialgebraic conditions for two floors to be unequal [edited]

EDIT: Since posting my original question I have simplified the problem to finding a sufficient condition for $\lfloor \frac{a}{\phi}\rfloor \neq \lfloor \frac{b}{\phi}\rfloor$ which is trigonometric ...
1
vote
0answers
165 views

recursion formula for odd holonomic function

suppose we have a map $f:\mathbb{Z}\longrightarrow\mathbb{C}[t^{\pm}]$ with property that $f(i)=-f(-i)$. The algebra $\mathcal{T}=\mathbb{C}[t^{\pm}][L^{\pm},M^{\pm}]/[LM=tML]$ acts on $f$ by ...
1
vote
0answers
420 views

Zeroes of a tricky function.

I am attempting to show that there does not exist an N past which every open unit interval (k, k+1) -where k is an integer- contains a zero of the following function: $h(x)=\sum_{n=2}^{[\sqrt(x)]} ...
0
votes
0answers
112 views

Probability generating function zero implies random variable is infinite

Let $V$ be a random variable supported on the nonnegative integers (including $\infty$) and $f(x) = \mathbf E x^V$ be the probability generating function. In our model $V$ is the number of visits to ...
0
votes
0answers
112 views

Lattice basis reductions and finding minimal values

While reading several articles about lattice basis reduction I am left with a few questions. For one, I came across this piece of text Let $\alpha$ and $\beta \in \mathbb{R}$. Also let $X>0$ and ...
0
votes
0answers
125 views

Two variable recurrence equation with varying coefficients

Hello, I have the following two variable recurrence equation for integers $j,k$: $f(j,k) = (k/j)f(j-1,k-1) - (3 + k/j)f(j-1,k+2)$ where $f(j,0) = (3^j - 1)/j + 3jf(j-1,2)$, $f(0,0) = 0$, $f(0,k) = ...
0
votes
0answers
125 views

A good upper bound on the size of k-biclique in random bipartite graphs.

Let $G = (X \cup Y, E)$ be a random bipartite graph, where $X$ and $Y$ are the set of vertices and $E$ the set of edges. I want to find an upper bound of the largest biclique in which exactly $k$ ...
0
votes
0answers
83 views

An upperbound related to inductively reducing a set by adding the two least elements

I hope this is not too trivial to be asked here, but here it goes anyway. This is just out of curiosity (regarding a problem with graphs but I have "reduced" it to the problem below:) Let ...
0
votes
0answers
180 views

Partial Recurrence Equation

Hey people I have the following equation, which I don't manage to solve. The background of the problem is the clustergrowth of two chemical species, resulting in a final relation I'd like to solve: ...
0
votes
0answers
395 views

Covering a set of intervals

EDIT: I posted this question to http://cstheory.stackexchange.com/questions/4358/covering-a-set-of-intervals , which looks like a more appropriate venue for such a question. Hello, I'm trying to ...