Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [ceiling-function]

The ceiling function maps a real number $x$ to the smallest integer greater than or equal to $x$, often denoted $\lceil x\rceil$. See also (floor-function).

2
votes
1answer
40 views

Prove that $ \left \lfloor {\log n} \right \rfloor = \left \lfloor {\log \left \lceil \frac {n-1}{2}\right \rceil} \right \rfloor + 1$

We have been doing algorithm analysis in university, and after analyzing binary search algorithm, the following equation resulted. What we have to do now is to prove that $ \left \lfloor {\log n} \...
4
votes
2answers
76 views

Solving $ 2< x^2 -[x]<5$

How to solve inequalities in which we have quadratic terms and greatest integer function. $$ 2< x^2 -[x]<5$$ [.] is greatest integer function. Do we need to break into the cases as [0,1), [1,...
0
votes
1answer
32 views

Ceiling function inequality mistake in an article?

I'm reading a paper which states the following (I'll just write the troubling parts): The probability that $n < N(T)$, which we represent by $P(n<N(T))$ ... because $N(T) = \lceil \lambda T\...
1
vote
0answers
50 views

Solve Inequality with ceiling function.

Motivation: Let $n,e,d$ be integers greater thant 2, such that $e\mid n-1$ and $d\mid n-1$. For $i=1,2,3,4,5$, define $$L_i=L_i(n,e,d)=a_{i1}n+a_{i2}e+a_{i3}d,$$ and $$k=\lceil \frac{L_1}{...
0
votes
0answers
20 views

Calculating the Mean of a Range with Floor and Ceiling Functions?

I did a survey a couple months back, and one of the questions required a range of numbers. I may have discovered my own formula for how to calculate the mean of a range of numbers, but I don't know ...
0
votes
1answer
42 views

Finding bounds on $g$ if $g(\frac{n}{2})=n\frac{m}{2}-\left[\lceil \frac{nm}{m+1}\rceil-\lceil\frac1{2}\lceil\frac{n}{m}\rceil\right]m$

If $g,n,m\in\mathbb{N}$ and $n$ be even with $m\le n-2$ and $$g(\frac{n}{2})=n\frac{m}{2}-\left[\displaystyle\lceil \frac{nm}{2(m+1)}\displaystyle\rceil-\displaystyle\lceil\frac1{2}\displaystyle\lceil\...
1
vote
2answers
47 views

Finding and proving a closed form formula for a recursive formula with floor and ceiling functions

I have $T:$ $\mathbb{N} \rightarrow \mathbb{N}$ Such that $T(1)=1$, $T(n)=T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil)$ for all $n\ge2$. My work: If $n$ is even then $\lceil n/2 \rceil = \lfloor ...
-1
votes
1answer
36 views

How to prove $\lceil \log_2{(n+1)} - 1 \rceil \ge \lfloor \log_2(n) \rfloor$? [closed]

Suppose $n$ is a positive integer. How can one show that $\lceil \log_2{(n+1)} - 1 \rceil \ge \lfloor \log_2(n) \rfloor$ ?
1
vote
2answers
64 views

Solving a tough equation involving integer functions

I am stuck on solving the equation, given $k\lt\frac{n}{2},\ n,k\ge3$: $$ m=\lceil 2k-\frac{2}{n}\displaystyle\left(\lfloor\frac{n-\lfloor\frac{n}{k+1}\rfloor}{2}\rfloor\right)(k+1)\rceil$$. I think ...
2
votes
3answers
36 views

Find the difference of ceiling functions

For $k \geq 1, 1 \leq r \leq k, t \geq 1, x \geq 1$, is there a lower bound or upper bound on: $$\left\lceil \dfrac{k(t+x)}{r} \right\rceil - \left\lceil \dfrac{k(t)}{r} \right\rceil$$ edit: all ...
2
votes
2answers
76 views

Finding $\lim\limits_{x\to 0} \frac{\lfloor x \rfloor}{x}$ and the different definitions of fractional part function.

I understand that $\lim\limits_{x\to 0} \frac{\lfloor x \rfloor}{x}$ does not exist because RHL is $0$ and LHL is $\infty$. However, when I tried to calculate the limit of the equivalent expression $1-...
1
vote
0answers
50 views

How to find the partial sum when a series uses $\operatorname{ceil}$?

Take this partial sum. By the formula for a finite geometric series: $$ \sum_{k=1}^n2\pi^{k-1}=2\left(\frac{1-\pi^n}{1-r}\right) $$ Simple enough. However, when a $\operatorname{ceil}$ is introduced,...
0
votes
0answers
32 views

What is the asymptotic upper bound of a variable in this functional equation?

We are given a recursive function $f(x) = \lceil \frac {f(x + 1)}{\lceil \log_2(f(x + 1)) \rceil} \rceil$. We know that $f(1) = 2$ and $f(a) = n$. What is the asymptotic upper bound of $a$ expressed ...
4
votes
5answers
903 views

$\left\lfloor \frac{a-b}{2} \right\rfloor + \left\lceil \frac{a+b}{2} \right\rceil = a$ when $a,b$ are integers? [closed]

Let $a$ and $b$ be positive integers. If $b$ is even, then we have $$\left\lfloor \frac{a-b}{2} \right\rfloor + \left\lceil \frac{a+b}{2} \right\rceil = a$$ I think the equality also hold when $b$ ...
1
vote
1answer
32 views

Equivalence between ceil and floor functions

I was reading heap data structures from various sources. They used to explain heap as stored in array. One source has array starting at index 0. Other has it starting at 1. They specify different ...
1
vote
1answer
33 views

Is it possible to represent this function as a polynomial, by removing the ceiling function?

I've been working through a derivation and have arrived at the following expression: $$E = 1 - \frac{x}y \left( \bigg\lceil \dfrac{x}{y} \bigg\rceil \right)^{-1}$$ where $x,y \in \mathbb{R^+}$. I ...
1
vote
2answers
50 views

Can this be solved to remove the floor function and simplify the answer?

I've been working through a derivation and have arrived at the following exprssion: $$E = 1 - \frac{x}y \left( \bigg\lfloor \dfrac{2x+yx-2}{2y} \bigg\rfloor \right)^{-1}$$ where $x,y \in \mathbb{R^+...
2
votes
1answer
66 views

Double sum over $\left\lfloor{ac+bd\over k}\right\rfloor$

We have $$\left\lfloor{ac+bd\over k}\right\rfloor-\left\lfloor{ac+bd-1\over k}\right\rfloor=1-\left\lceil{ (ac+bd)\mod{k}\over k}\right\rceil$$ for $a,b,c,d,k$ - integers, $a\geqslant0$, $b\geqslant0$,...
2
votes
1answer
43 views

Injectivity of $f(x) = x + [x/2]$, and finding an explicit inverse

Context: This question comes up as a tangent to an earlier MSE question from today. The OP of this question was, in effect, seeking an explicit inverse to the function $$f(x) = x + \left[ \frac{x}{2}...
0
votes
0answers
25 views

Identity involving floor, ceiling and nearest integer functions

For $n\geqslant0$, $m>0$, $s>t\geqslant0$, $n,m,s,t$ - integers we have $$\sum\limits_{k=0}^{m-1}\left\lfloor{n+ks+t\over ms}\right\rfloor=\left\lfloor{n+t\over s}\right\rfloor$$ $$\sum\limits_{...
1
vote
2answers
45 views

Prove that $\lfloor \sqrt{(p-1)p} \rfloor = p - 1$ and likewise $\lceil \sqrt{(p-1)p} \rceil = p$.

Here $p$ is prime but is not necessary for the problem just that $p \ge 0$. I suspect that a statement like $p-1 \le \sqrt{(p-1)p} \le p$ would be the case but I am not certain how to establish this ...
0
votes
0answers
16 views

Coefficients from sequence of ceil divisions

I wanted to know if there exists a systematic elegant “closed form” formula for calculating numbers ${{s}_{i,j,\left\{ 1,2 \right\}}}(n) \in {{\mathbb{N}}^{*}},$ and also positive rational numbers $...
4
votes
0answers
89 views

Prove a limit involving the ceiling function

I found a pattern that I want to prove: $$f(x) = 2^{\lceil \log_2(3^x)\rceil} - 3^x\quad \{x\in\mathbb{Z}^+\} $$ $$ \lim_{x\rightarrow\infty} f(x) = \infty $$ Discussion: $$ f(x) = 2^{\lceil \...
2
votes
1answer
54 views

Constructing a 2-periodic extension of the absolute value function using floor and ceiling functions

I am trying to use floor and ceiling functions to construct a 2-periodic extension of the function $f(x) = |x|, -1 \leq x \leq 1$. Through trial an error I have been able to show that: $f(x) = 1 - \...
0
votes
3answers
104 views

How to solve a recurrence relation involving a ceiling function?

I have no idea against ceiling function... How to solve $f(n) = 2f(\lceil{\frac{n}{2}}\rceil) - 1, n > 2, $ $f(2) = 2$ ? Thanks!
3
votes
1answer
52 views

How to evaluate the following sum if $n$ is an even number?

In a mathematical physical problem, the sum below needs to be calculated: $$ F_n(\xi) = \sum_{k=0}^{\operatorname{ceil} \left(\frac{n}{2}-1 \right)} (-1)^k \frac{\xi^{2k}}{n-2k} = \begin{cases} \...
4
votes
0answers
79 views

Are there infintely many primes generated by the recursion $c_{n+1} = \lceil \frac{3}{2} c_{n} \rceil$?

Inspired by a recent discussion (How to solve a ceiling expression or recurrence equation?) I stumbled on the question: Are there infinitely many primes in power ceiling series? If not there must ...
-1
votes
1answer
40 views

is this statement about x, y, and z true?

I would like to know if the following statement about x,y and z is true: $$x=\lfloor\frac{y}{z}\rfloor \iff z=\lfloor\frac{y}{x}\rfloor$$ I think it is true but am having a hard time wrapping my ...
4
votes
3answers
92 views

Calculate $\int_0^1{x·\lceil1/x\rceil dx}$

I am trying to calculate following integral: $$\int_0^1{x·\biggl\lceil \frac{1}{x}\biggr\rceil dx}$$ I tried usual change t=1/x but not able to further advance. Thanks!
3
votes
4answers
293 views

Prove that $\lfloor x\rfloor \geq y$ if, and only if, $x\geq\lceil y\rceil$

I have some trouble proving that if $x,y\in\mathbb{R}$ then $\lfloor x\rfloor \geq y$ if, and only if, $x\geq\lceil y\rceil$. I have tried some different approaches, the most recent being a proof by ...
0
votes
1answer
40 views

Optimization with ceiling function to determine voxel size

I am trying to calculate the voxel size for a voxel grid which must enclose a $3$D object with real dimensions $\alpha$,$\beta$,$\gamma$ ($\ge 0$). The amount of voxels may be at most $\theta$ (...
0
votes
2answers
47 views

Properties of floors, ceilings and modulus

I'm trying to reduce one calculation in an iterative Successive Over-Relaxation procedure for a program I'm writing. The code that works does this calculation: $$ s = \left\lfloor\frac{b + \left\...
9
votes
1answer
648 views

Are ceiling and floor elementary functions?

According to the Wikipedia entry on elementary functions, the trigonometric functions and their inverses are elementary functions. It doesn't seem to me that the floor and ceiling functions should be ...
0
votes
0answers
46 views

Splitting of a sum involving a ceiling function

I want to calculate a sum involving a ceiling function in its argument, by splitting the sum into several sums, and replacing the ceiling function by its evaluated value within the intervals of these ...
1
vote
2answers
36 views

Surjectivity of $\lceil x/2\rceil$ over the integers [closed]

Is the following function surjective from the set of integers to the set of integers? $$\lceil x/2\rceil$$ My initial intuition says that it is, but I don't know if once the element $x$ from the ...
1
vote
0answers
26 views

max(y) and max(x) for $1 \geq xy\lceil{\log_2{x}}\rceil\times\frac{1}{100}$

$1 \geq x\times\lceil{\log_2{x}}\rceil\times y\times\frac{1}{100}$ $x \in \mathbb{N}$, $x \geq 2$ $y \in \mathbb{Q}$, $y \geq 0$ now I can declare $max_y(x) = \frac{1}{x\times\lceil{\log_2{x}}\...
0
votes
0answers
30 views

When finding the upper bound, why is a ceiling evaluated to a +1?

Why does removing the ceiling result in $a + 1$? I'm reading Introduction to Data Compression by Guy E. Blelloch on page $19$ on Information Theory, here he is proving an upper bound. $$ \begin{...
1
vote
2answers
179 views

How can I express this expression without ceiling function: $\left\lceil \frac {1003}{3000}×2^{2n-1} \right\rceil$

I think the following equality is correct for $n\in \mathbb{Z^{+}}$ $$\left\lceil \frac 13×2^{2n-1} \right\rceil=\frac 13×(2^{2n-1}+1)$$ Now, I need to find such a equality for the following ...
1
vote
0answers
55 views

$n_{i+1} = \lceil n_i/2 \rceil + 1$, get a TIGHT upper bound of sum $\sum_{i=0}^d \lfloor n_i/2 \rfloor$

For any $n\in\mathbb{Z}^+$, define a sequence $\{n_i\}$: $$ \begin{cases} n_0=n\\ n_{i+1}=\lceil n_i/2 \rceil + 1 \end{cases} $$ and $\{k_i\}$ are the terms to be added: $$ k_i = \lfloor n_i/2 \rfloor ...
-1
votes
1answer
107 views

Ceiling function and limit problem $\lim_{n \to \infty} \frac {\lceil 4^{n+\frac{\log \frac 83}{\log4}} \rceil}{\lceil 4^{n+0.707519} \rceil}$ [closed]

I want to calculate this limit: $$\lim_{n \to \infty} \frac {\lceil 4^{n+\frac{\log \frac 83}{\log4}} \rceil}{\lceil 4^{n+\lambda} \rceil}$$ where, $\lambda$ is a constant and I know $6$ digits. ...
0
votes
1answer
27 views

Is there a way to write this out in a better way? I want to get rid of an Iverson bracket

I have $\lceil \frac{m+1}{1.37}\rceil - \lceil \frac{m}{1.37}\rceil$ which I think could be written as $[m + 1$ is an integer not divisible by 1.37$]$, where [] denotes the Iverson bracket. I want to ...
1
vote
2answers
142 views

Proving Hermite's Identity in a different approach

To prove $$S=\left [x \right]+\left [x+\frac{1}{n} \right]+\left [x +\frac{2}{n}\right]+\cdots+\left [x +\frac{n-1}{n}\right]=\left [nx \right]$$ using and starting with $$x-1 \lt \left [x \right]\...
1
vote
1answer
85 views

How to optimize for following cost function?

For given values of constants $\forall i $ $a_i, b_i, c$ such that $a_i, b_i, c \in Q^+$ and $0 < a_i < 1$, find all variables $n_i$ such that $$n_i \in Z^+$$ and $$c \ge \sum_{i}{\frac{b_i}{...
1
vote
1answer
66 views

How to solve equation with ceil function

For a problem I came out with following equation: $$\left\lceil\frac{x_1}{k}\right\rceil + \left\lceil\frac{x_2}{k}\right\rceil + \left\lceil\frac{x_3}{k}\right\rceil + \cdots + \left\lceil\frac{x_n}{...
0
votes
2answers
41 views

Solving multiple ceil functions

Hello, I am working on an computer program and I am required to find the least possible value of $x$ for $\lceil \dfrac a x \rceil + \lceil \dfrac b x \rceil + \lceil \dfrac c x \rceil + \lceil \...
1
vote
0answers
47 views

Ceiling Function Proof from First Principles? [duplicate]

My question is whether it is possible to prove that a ceiling function exists ie. If $a\in\mathbb R$, then there exists $n\in\mathbb Z$ satisfying $a\le n< a+1$. The only solutions to this that I ...
0
votes
1answer
232 views

Prove that if $x \in R,$ then there exists $n \in Z$ satisfying $x \leq n < x+1$

So this question in my book looks like it's essentially asking me to prove the ceiling function exists. This question is slightly different to other things I found in related question because we're ...
0
votes
1answer
40 views

Solve $n * \lceil{\frac{R}{T}}\rceil - \lceil{\frac{R*n}{T} - \frac{x*n}{T}}\rceil = \frac{x * n}{C}$ for x and n, $n \in Z^+$ and $x,R,T,C \in R^+$

I want to find the minimum value of n which satisfy given equation. (Also, not stated in title but given is that $C < T$) So far, I have been able to find the following properties: $$\frac{x * n}...
4
votes
1answer
99 views

Solve $\lceil x\rceil-\frac{\lceil nx\rceil}n\geqslant y$ for $n$, where $n \in\mathbb Z^+, x \in\mathbb R^+, y \in\mathbb R^+$

I want to solve for minimum value of $n$ such that$$ \lceil x\rceil - \frac{\lceil nx\rceil} n \geqslant y $$ with $x$ and $y$ given. I want to arrive at the value of $n$ in a computer program without ...
0
votes
2answers
71 views

Inequality with the difference of ceil functions [closed]

I am interested in the validation of the inequality $$ \lceil x \rceil - \lceil y \rceil \leqslant \lceil x-y \rceil $$ where $x, y$ are assumed to be positive. Can someone help me to proof it?