Math toolkit

ACompressed recap

🧾

Powers of 2 grow by doubling: 2^10^ = 1024 (K), 2^20^ (M), 2^30^ (G). log₂ x is the power of 2 that gives x; logs turn products into sums and powers into products. ⌊x⌋ rounds down, ⌈x⌉ up. Halving n to 1 takes ⌊log₂ n⌋ steps, doubling 1 to at least n takes ⌈log₂ n⌉, and labelling n things needs ⌈log₂ n⌉ bits.

Sums: 1 + … + n = n(n + 1)/2; 1 + 2 + … + 2^n^ = 2^n+1^ − 1; halving sums stay below 2n. Counting: sum rule, product rule, n!, ordered choices n!/(n − k)!, unordered nCr, pairs nC2, subsets 2^n^.

BMerged rule card

0.2.1 Powers of 2 and logarithms; floor and ceiling

• 2^10^ = 1024 (K), 2^20^ ≈ 10^6^ (M), 2^30^ ≈ 10^9^ (G).
• 2^a^·2^b^ = 2^a+b^; 2^a^/2^b^ = 2^a−b^; (2^a^)^b^ = 2^ab^.
• log₂ x = the power of 2 that gives x; log₂ 1 = 0.
• log(ab) = log a + log b; log(a^k^) = k log a; logb x = log₂ x / log₂ b.
• ⌊x⌋ round down, ⌈x⌉ round up; ⌈a/b⌉ = ⌊(a + b − 1)/b⌋ for positive whole a, b.
• Halvings from n to 1 = ⌊log₂ n⌋; doublings from 1 to ≥ n = ⌈log₂ n⌉; bits for n labels = ⌈log₂ n⌉.

0.2.2 Sums of series (1+2+…+n, 1+2+4+…+2ⁿ); basic counting

• Σ i (i = 1 to n) = n(n + 1)/2; 1 + … + (n − 1) = n(n − 1)/2.
• a + … + b = (b − a + 1)(a + b)/2.
• Σ i² = n(n + 1)(2n + 1)/6.
• 1 + 2 + … + 2^n^ = 2^n+1^ − 1; 1 + r + … + r^n^ = (r^n+1^ − 1)/(r − 1).
• n + n/2 + n/4 + … < 2n.
• Sum rule (or) add; product rule (and then) multiply.
• n! orders; ordered k of n: n!/(n − k)!; unordered: nCr = n!/(k!(n − k)!); pairs nC2; subsets 2^n^.

CInterleaved GATE-style questions

Q1NAT1 markLogs

What is log₂ 4096?

Numerical answer: ________

Q2NAT1 markFloor

How many times can 1000 be halved (dropping fractions) before it reaches 1?

Numerical answer: ________

Q3MCQ1 markLogs

log₈ 512 equals:

• (A) 9
• (B) 1/3
• (C) 3
• (D) 64

Q4NAT2 marksSeries

What is 20 + 21 + … + 80?

Numerical answer: ________

Q5NAT1 markDoubling

A server log doubles in size every hour, starting at 1 MB in hour 1. What is the total written over the first 10 hours, in MB?

Numerical answer: ________

Q6MCQ2 marksCounting

How many different 4-digit PINs use only the digits 1–6 with no digit repeated?

• (A) 1296
• (B) 360
• (C) 24
• (D) 15

Q7MSQ1 markFloor and ceiling

For n = 64, which are equal to 6?

• (A) ⌊log₂ n⌋
• (B) ⌈log₂ (n + 1)⌉
• (C) ⌈log₂ n⌉
• (D) log₂ n

Q8NAT2 marksPattern

For each i from 1 to 10 you do i × i steps. How many steps in total?

Numerical answer: ________

Q9MCQ1 markCounting

How many subsets does a set of 10 elements have?

• (A) 100
• (B) 10
• (C) 1024
• (D) 3628800

DAnswer Vault