Basic concepts Solving Recurrences Mod: The binary Op

Chapter 3.
Integer Functions
Discussion on CMath: A Foundation for CS

AUGPath

China Univ. of Geosciences

November 2, 2023
Basic concepts Solving Recurrences Mod: The binary Op

Section 1

Basic concepts
Basic concepts Solving Recurrences Mod: The binary Op

Floors and Ceilings

Definition
• ⌊x⌋ = the greatest integer less than or equal to x.
• ⌈x⌉ = the least integer greater than or equal to x.

5
⌊x⌋
4
⌈x⌉
y3
2
1

−5 −4 −3 −2 −1 1 2 x3 4 5
−1
−2
−3
−4
−5

Figure: Floor and ceiling

Basic concepts Solving Recurrences Mod: The binary Op

Basic Properties

• Inequality: x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1.

• Negation: ⌈−x⌉ = −⌊x⌋, ⌊−x⌋ = −⌈x⌉.
• Convert:
• ⌊x⌋ = n ⇐⇒ (with respect to x);
• ⌊x⌋ = n ⇐⇒ (with respect to n);
• ⌈x⌉ = n ⇐⇒ (with respect to x);
• ⌈x⌉ = n ⇐⇒ (with respect to n);
• Moving integers: For integer n, ⌊x + n⌋ = ⌊x⌋ + n.
Basic concepts Solving Recurrences Mod: The binary Op

Basic Properties

• Inequality: x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1.

• Negation: ⌈−x⌉ = −⌊x⌋, ⌊−x⌋ = −⌈x⌉.
• Convert:
• ⌊x⌋ = n ⇐⇒ n≤x<n+1 (with respect to x);
• ⌊x⌋ = n ⇐⇒ x−1≤n<x (with respect to n);
• ⌈x⌉ = n ⇐⇒ n−1<x≤n (with respect to x);
• ⌈x⌉ = n ⇐⇒ x≤n<x+1 (with respect to n);
• Moving integers: For integer n, ⌊x + n⌋ = ⌊x⌋ + n.
Basic concepts Solving Recurrences Mod: The binary Op

Example. An identity

Example
p √
Prove that ⌊ ⌊x⌋⌋ = ⌊ x⌋.
Basic concepts Solving Recurrences Mod: The binary Op

Example. An identity

Example
p √
Prove that ⌊ ⌊x⌋⌋ = ⌊ x⌋.
p
• Let m = ⌊ ⌊x⌋⌋. What is the range of m?
p
• m ≤ ⌊x⌋ < m + 1.
• Squaring to get the answer.
Basic concepts Solving Recurrences Mod: The binary Op

Example. Switching counting number

Example
Let f (x) be any cont. mono. increasing func. with prop. that
f (x) = integer =⇒ x = integer, prove that ⌊f (x)⌋ = f (⌊x⌋),
same as the ceiling.
Basic concepts Solving Recurrences Mod: The binary Op

Example. Switching counting number

Example
Let f (x) be any cont. mono. increasing func. with prop. that
f (x) = integer =⇒ x = integer, prove that ⌊f (x)⌋ = f (⌊x⌋),
same as the ceiling.

• If x = ⌊x⌋, trivial.
• Otherwise x > ⌊x⌋ =⇒ f (x) > f (⌊x⌋). What about f (⌊x⌋)
and ⌊f (x)⌋?
• Assume this is true: f (⌊x⌋) < ⌊f (x)⌋, continuous,
• must be a number y s.t. x ≤ y < ⌈x⌉ and f (y) = ⌈f (x)⌉. By
the special property of x
• y integer, no number between x ≤ y < ⌈x⌉, hence they are
equal.
Same problem: cont. mono. decreasing, what’s that?
Basic concepts Solving Recurrences Mod: The binary Op

Counting the Integer Points

Count the integer points on a number line.

• if a, b ∈ Z, integer point in [a, b] is b − a + 1.
• More general case
• [α, β]
• (α, β]
• [α, β)
• (α, β)
Helpful when handling summations by counting.
Basic concepts Solving Recurrences Mod: The binary Op

Counting the Integer Points

Count the integer points on a number line.

• if a, b ∈ Z, integer point in [a, b] is b − a + 1.
• More general case
• [α, β] ⌊β⌋ − ⌈α⌉ + 1
• (α, β] ⌊β⌋ − ⌊α⌋
• [α, β) ⌊β⌋ − ⌈α⌉
• (α, β) ⌈β⌉ − ⌊α⌋ − 1
Helpful when handling summations by counting.
Basic concepts Solving Recurrences Mod: The binary Op

Example. Computing a sum

Example
Compute
X
1000
√ 
W = [ 3
n |n]
i=1
Basic concepts Solving Recurrences Mod: The binary Op

Example. Computing a sum

Example
Compute
X
1000
√ 
W = [ 3
n |n]
i=1

√
• Make a new one name for k = 3 n, getting
k | n, 1 ≤ n ≤ 1000.
√
• The range for k is k ≤ 3 n < k + 1
• k|n means that there is a m so that n = km.
P
• then becomes 1 + k,m [k 3 ≤ km ≤ (k + 1)3 ][1 ≤ k < 10].
Basic concepts Solving Recurrences Mod: The binary Op

Example cont’d. Computing a sum

Example
Compute
X
K
√ 
W = [ 3 n |n], K ∈ Z.
i=1
Basic concepts Solving Recurrences Mod: The binary Op

Example cont’d. Computing a sum

Example
Compute
X
K
√ 
W = [ 3 n |n], K ∈ Z.
i=1

P
• We should care about m [k 3 ≤ Km ≤ N ].
P
• this part become m [m ∈ [k 2 ..N /K]].
• the estimation will be 3/2N 2/3 + O(N 1/3 ).
Basic concepts Solving Recurrences Mod: The binary Op

Example. The Spectra Example

Example
The spectrum of a real number α to be an infinite multiset of
integers. That is

Spec(α) = {⌈α⌉ , ⌈2α⌉ , · · · }

We can prove that (1)

√ no two spectrum are equal; (2)
Spec(2) ∪ Spec(2 + 2) = Z.
Basic concepts Solving Recurrences Mod: The binary Op

Example. The Spectra Example

Example
The spectrum of a real number α to be an infinite multiset of
integers. That is

Spec(α) = {⌈α⌉ , ⌈2α⌉ , · · · }

We can prove that (1)

√ no two spectrum are equal; (2)
Spec(2) ∪ Spec(2 + 2) = Z.
P
• We define N (α, n) = k>0 [⌊kα⌋ ≤ n].
• which is ⌈(n + 1)/α⌉ − 1.
 √   √ 
• proving n + 1/ 2 − 1 + n + 1/2 + 2 − 1 = n.
This equality will be helpful:

a ≤ b =⇒ a < b − 1 for floors and ceiling func.

Basic concepts Solving Recurrences Mod: The binary Op

Section 2

Solving Recurrences
Basic concepts Solving Recurrences Mod: The binary Op

The first example: Knuth Number(KN)

We have the following example:

K0 = 1;
Kn+1 = 1 + min(2K⌊n/2⌋ , 3K⌊n/3⌋ ).

Prove or disproof that for n ≥ 0, Kn ≥ n.

• List small vals for k.
• Proof by induction.
• Base case: K = 0 satisfy the condition.
• Induction
Basic concepts Solving Recurrences Mod: The binary Op

KN: Induction Step

K0 = 1;
Kn+1 = 1 + min(2K⌊n/2⌋ , 3K⌊n/3⌋ ).

• Assume the inequality hold for all vals up to some non

negative vals n,
• Goal: show that Kn+1 ≥ n + 1.
• Given Kn+1 = 1 + min(2K⌊n/2⌋ , 3K⌊n/3⌋ ), and
2K⌊n/2⌋ ≥ 2 ⌊n/2⌋ , 3K⌊n/3⌋ ≥ 3 ⌊n/3⌋(by hypothesis)
• But 2 ⌊n/2⌋ can be as small as n − 1, 3 ⌊n/3⌋ can be as small
as n − 2, breaking the induction.
• Or really? This case jumps fast.
Basic concepts Solving Recurrences Mod: The binary Op

KN: The special case

We can prove by contradiction:

• Assume we can find a value m s.t. Km ≤ m
• finding m’s origin, say m = n′ + 1
• requires K⌊n′ /2⌋ ≤ ⌊n′ /2⌋, and K⌊n′ /3⌋ ≤ ⌊n′ /3⌋.
• This implies K0 ≤ 0, but K0 = 1, contradiction.
Basic concepts Solving Recurrences Mod: The binary Op

About Math. Induction

In trying to devise a proof by

mathematical induction, you
may fail for two opposite rea-
sons. You may fail because you
try to prove too much: Your
P (n) is too heavy a burden.
Yet you may also fail because
you try to prove too little: Your
P (n) is too weak a support.
In general, you have to bal-
Figure: G. Polya
ance the statement of your the-
orem so that the support is just
enough for the burden.”
Basic concepts Solving Recurrences Mod: The binary Op

Jospher’s Problem Generlized(JPG)

Idea: Whenever a person is passed over, give it a new number.

Demonstrate:
Basic concepts Solving Recurrences Mod: The binary Op

Jospher’s Problem Generlized(JPG)

Idea: Whenever a person is passed over, give it a new number.

Demonstrate:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22
23 24 25
26 27
28
29
30
Basic concepts Solving Recurrences Mod: The binary Op

JPG: Findings
1 2 31 4 5 62 7 8 93 10
11 124 13 14 155 16 17
186 19 20 217 22
23 24 8 25
26 279
28
29
3010
What will the id become?
• 1, 2 become ;
• 3 executed;
• 4, 5 become ;
• 6 is executed;
• 3k + 1, 3k + 2 will become ;
• 3k + 3 is executed.
Basic concepts Solving Recurrences Mod: The binary Op

JPG: Findings
1 2 31 4 5 62 7 8 93 10
11 124 13 14 155 16 17
186 19 20 217 22
23 24 8 25
26 279
28
29
3010
What will the id become?
• 1, 2 become n + 1, n + 2;
• 3 executed;
• 4, 5 become n + 3, n + 4;
• 6 is executed;
• 3k + 1, 3k + 2 will become n + 2k + 1, n + 2k + 2;
• 3k + 3 is executed.
Basic concepts Solving Recurrences Mod: The binary Op

JPG: Findings

1 2 31 4 5 62 7 8 93 10
11 124 13 14 155 16 17
186 19 20 217 22
23 24 8 25
26 279
28
29
3010
• Counting is consistent, no jumping over someone.
• The k-th person eliminated ends up with number 3k.
• To find the survivor = figure out the original number 3N .
Basic concepts Solving Recurrences Mod: The binary Op

JPG: Findings

1 2 31 4 5 62 7 8 93 10
11 124 13 14 155 16 17
186 19 20 217 22
23 24 8 25
26 279
28
29
3010
• What is 3N originally?
• N (N > n) has a form of N = n + 2k + 1 or N = n + 2k + 2,
in a single round.
• for two ks, getting k1 = (N − 1 − n)/2, k2 = (N − 2 − n)/2.
• = ⌊(N − n − 1)/2⌋.
Basic concepts Solving Recurrences Mod: The binary Op

JPG: Findings

1 2 31 4 5 62 7 8 93 10
11 12 4 13 14 5
15 16 17
186 19 20 217 22
23 24 8 25
26 279
28
29
3010
An algorithm for this:
• Let N ← 3n;
• while N > n, let N ← ⌊(N − n − 1)/2⌋ + N − n;
• Answer← N .
Basic concepts Solving Recurrences Mod: The binary Op

JPG: Findings

1 2 31 4 5 62 7 8 93 10
11 124 13 14 155 16 17
186 19 20 217 22
23 248 25
26 279
28
29
3010
Simplifying this algorithm: like treating arithmetic series.
• Assign the numbers from largest to smallest
• yielding ⌈3/2D⌉.
Basic concepts Solving Recurrences Mod: The binary Op

JPG: Findings

1 2 31 4 5 62 7 8 93 10
11 12 4 13 14 5
15 16 17
186 19 20 217 22
23 24 8 25
26 279
28
29
3010
Generalized: D = ⌈q/(q − 1)D⌉ for general qs, i.e. q-kill one.
Basic concepts Solving Recurrences Mod: The binary Op

Section 3

Mod: The binary Op

Basic concepts Solving Recurrences Mod: The binary Op

Mod: definition

We may rewrite the quotient and remainder as follows:

If n is an integer, then

n = m ⌊n/m⌋ + n mod m.

for y ̸= 0.
• generalize it to negative integers
• 5 mod 3 = 5 − 3 ⌊5/3⌋ = 2.
• 5 mod −3 = 5 − (−3) ⌊5/ − 3⌋ = −1.
• −5 mod 3 = −5 − (−3) ⌊−5/3⌋ = 1.
• −5 mod −3 = −5 − (−3) ⌊−5/ − 3⌋ = −2.
Basic concepts Solving Recurrences Mod: The binary Op

Mod: definition

We may rewrite the quotient and remainder as follows:

If n is an integer, then

n = m ⌊n/m⌋ + n mod m.

for y ̸= 0.
• Observation: In any case the result number is exactly in
between 2 numbers.
• Special definition: if y = 0, then x mod 0 = x.
• preserves the property that x and y always differs from x by a
multiple of y.
Basic concepts Solving Recurrences Mod: The binary Op

Another notation: Mumble

We have n mod m = n − ⌊n/m⌋ m

Alternative definition: mumble.
 
x
x mumble y = y −x
y
Basic concepts Solving Recurrences Mod: The binary Op

Properties

• Distributive: c(x mod y) = (cx) mod (cy) for c, x, y ∈ R.

• reason: c(x mod y) = c(x − y ⌈x/y⌉) = cx − cy(⌊cx/cy⌋) =
(cx) mod (cy).
Basic concepts Solving Recurrences Mod: The binary Op

Example: Even partition problem(EPP)

Problem: Partition n things into m groups as equally as possible.

An example:
1 9 17 25 33
2 10 18 26 34
3 11 19 27 35
4 12 20 28 36
5 13 21 29 37
6 14 22 30
7 15 23 31
8 16 24 32

• the final row has only 5 elems, can we do better?

Basic concepts Solving Recurrences Mod: The binary Op

Example: Even partition problem(EPP)

Problem: Partition n things into m groups as equally as possible.

A evener example: An example:

1 9 17 24 31
2 10 18 25 32
3 11 19 26 33
4 12 20 27 34
5 13 21 28 35
6 14 22 29 36
7 15 23 30 37
8 16
Basic concepts Solving Recurrences Mod: The binary Op

Example: Even partition problem(EPP)

Problem: Partition n things into m groups as equally as possible.

• Division: a row by row arrange not always good.
• it tells us how many lines to put
• Some of the short one put ⌈n/m⌉ columns, others put ⌊n/m⌋
cols.
• There will be exactly n mod m cols, and exactly
m − n mod m = n mumble mshort ones.
Basic concepts Solving Recurrences Mod: The binary Op

Example: Even partition problem(EPP)

Problem: Partition n things into m groups as equally as possible.
Procedure:
• To distribute n things into m groups as even as possible,
• when m > 0, put ⌈n/m⌉ things into one group
• then use this procedure to recursively
• i.e. put put the remaining n′ = n − ⌈n − m⌉ things into
m′ = m − 1 groups.
Proof:
• Suppose that n = qm + r
• If r = 0, We put ⌊n/m⌋ = q things into the first,
n′ = n − q, m′ = m − 1.
• If r > 0, put ⌊n/m⌋ = q + 1 into first group, leaving
n′ = n − q − 1 = qm′ + r − 1.
Basic concepts Solving Recurrences Mod: The binary Op

Example: Even partition problem(EPP)

Problem: Partition n things into m groups as equally as possible.
A closed form for the formula?
• Effect: the quotient stays the same, but the remainder
decrease by 1.
• That is there are ⌈n/m⌉ things when k ≤ n mod m, and
⌊n/m⌋ things o.w.
• So the closed form is ⌈n − k + 1/m⌉.
Since we are arrange n elems, we have the following identity:
j n k n + 1 
n + (m − 1)

n= + + ··· +
m m m
Replace n by mx we get
   
1 m−1
mx = ⌊x⌋ + x + + ··· + x +
m m
Basic concepts Solving Recurrences Mod: The binary Op

Example: A Weird Sum(WS)

Find X j√ k
k
0≤k≤n

where a is a perfect square.

Solution:
X l√ m
k
0≤k≤n
X
= m[k < n][m = ⌈k⌉]
k,m≥0
X √
= m[k < n][m ≤ k < m + 1]
k,m≥0

Then we calculate the total number of this.

Basic concepts Solving Recurrences Mod: The binary Op

Example: A Weird Sum(WS)

Find X j√ k
k
0≤k≤n
where a is a perfect square.
Solution:
X √
= m[k < n][m ≤ k < m + 1]
k,m≥0
X
= m[m ≤ k ≤ (m + 1)2 ≤ a2 ]
k,m≥0
X
= m((m + 1)2 − m2 )[m + 1 ≤ a]
m≥0
X
= m(2m + 1)
m≥0,m≤a
Basic concepts Solving Recurrences Mod: The binary Op

Example: A Weird Sum(WS)

Find X j√ k
k
0≤k≤n

where a is a perfect square.

Solution:
That is
Xa
(2m2 + 3m1 )δm
0

Using the integration rule, we get

2/3a(a − 1)(a − 2) + 3/2a(a − 1).
Basic concepts Solving Recurrences Mod: The binary Op

Example: A Weird Sum(WS)

Find X j√ k
k
0≤k≤n

where a is a perfect square.

Solution:
Removing the perfect square condition
• do the partition from [0..a2 ] and [a2 ..n].
• this will use O notation to express its increament.
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for

X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

We first look at some observations
P
• n = 1, yields 0≤k<m ⌊(k + x)/m⌋, where we found at the
EPP problem.
• m = 1, this will be ⌊x⌋;
• m = 2, we look at ⌊x/2⌋ + ⌊(x + n)/2⌋.
• n even, n/2 integer. ⌊x/2⌋ + ⌊(x + n)/2⌋ = 2 ⌊x/2⌋ + n/2.
• n odd, (n − 1)/2 integer.
⌊x/2⌋ + (⌊(x + 1)/2⌋ + (n − 1)/2) = ⌊x⌋ + (n − 1)/2.
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for

X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

Have a look at m = 3:
• n mod 3 = 0, n/3 and 2n/3 integers:
 x   x n   x 2n 
3 + 3 + 3 + 3 + 3 = 3 ⌊x/3⌋ + n.
• n mod 3 = 1, n − 1/3 and 2n − 2/3 integers:
 x   x+1 n−1   x+2 2n−2 
3 + 3 + 3 + 3 + 3 = ⌊x⌋ + n − 1.
• n mod 3 = 2, n − 2/3 and 2n − 4/3 integers:
 x   x+2 n−2   x+4 2n−4 
3 + 3 + 3 + 3 + 3 = ⌊x⌋ + n − 1.
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for

X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

Look at n = 4,
• n mod 4 = 0, 4 ⌊x/4⌋ + 3n/2;
• n mod 4 = 1, ⌊x⌋ + 3n/2 − 3/2;
• n mod 4 = 0, ⌊x⌋ + 3n/2 − 3/2;
• n mod 4 = 0, 2 ⌊x⌋ + 3n/2 − 1;
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for
X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

We make a small table for this:
m n mod m = 0 n mod m = 1 n mod m = 2 n mod m == 3
1  x⌊x⌋

2 2  2  + n2 ⌊x⌋ + n2 − 12
3 x
3 3 + n ⌊x⌋ + n − 1 ⌊x⌋
 x  + n3n− 1
4 x
4 4 + 2 3n
⌊x⌋ + 2 − 2 2 2 + 2 − 1 ⌊x⌋ + 3n
3n 3
2 − 2
3

It looks that:
 
x + kn mod m kn kn mod m
+ −
m m m
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for

X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

This can be extracted from
 
x + kn mod m kn kn mod m
+ −
m m m
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for
X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

jxk 0 0 mod m
+ −
m  m m
x + n mod m n n mod m
+ + −
m m m
 
x + 2n mod m 2n 2n mod m
+ + −
m m m
.. ..
. .
 
x + (m − 1)n mod m (m − 1)n (m − 1)n mod m
+ + − .
m m } |
| {z m
{z }
| {z }
bn C
a⌊ x
a⌋
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for

X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

Looking at the table:
 
• The second column is 1
2 0+ (m−1)n
m m
• The first column: See what
0 mod m, n mod m, 2n mod m, · · · , (m − 1)n mod m will
get.
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for

X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

Look at the first row of that one, recall
j n k n + 1 
n + (m − 1)

n= + + ··· +
m m m

• We will encounter the remainder from 1 to n one time(we will

show at Chapt. 4)
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for

X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

So we have:
j    
xk x+d x+m−d
d + + ··· +
m m m
     
x/d x/d + 1 x/d + m/d − 1
=d + + ··· +
m/d m/d m/d
jxk
=d ., and hence, a = d = gcd(m, n).
d
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for

X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

The third column: d 12 0 + m−dm · m
d = m−d
2
• c= d−m
2 .
Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for

X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

Putting altogether:
X  nk + x  jxk m − 1 d−m
=d + n+ .
m d 2 2
0⩽k<m

where d = gcd(m, n).

Basic concepts Solving Recurrences Mod: The binary Op

Example: an Integrated Example(IE)

Find the closed form for
X  nk + x 
m
0≤k<m

for integer m > 0, integer n.

In fact, m and n are symmetric:
X  nk + x  jxk m − 1 d−m
=d + n+
m d 2 2
0⩽k<m
j x k (m − 1)(n − 1) m − 1 d − m
=d + + +
d 2 2 2
j x k (m − 1)(n − 1) d − 1
=d + +
d 2 2
saying,

X  nk + x  X  mk + x 
= , integers m, n > 0.
m n
0⩽k<m 0⩽k<n
Thanks