Ladakh PSC /Quantitative Aptitude

Number system

Arithmetic · free study notes

Number System – Advanced Study Notes

(MIT‑style, first‑principles approach – suitable for Ladakh PSC Quantitative Aptitude)


1. Foundations of Positional Representation

Symbol Meaning Example General formula
b Base (radix) decimal → b = 10
dᵢ Digit at position i (0‑indexed from the right) 345_10 → d₂=3, d₁=4, d₀=5
N Integer in base‑b N = Σ_{i=0}^{k} dᵢ b^i
k Highest power of b present k = ⌊log_b N⌋

Theorem (Uniqueness).
For a given base b ≥ 2, every non‑negative integer N has a unique representation
N = Σ_{i=0}^{k} dᵢ b^i with digits 0 ≤ dᵢ < b.
Proof: By induction on k. For k = 0, trivial. Assume uniqueness for all numbers < b^k. Let N < b^{k+1}. Divide N by b:
N = q·b + r, 0 ≤ r < b.
By induction, q has a unique representation with powers < b^k. Thus N’s representation is unique. ∎


2. Common Bases and Their Properties

Base Decimal value Notation Special Properties
2 Binary b₂ b² = 4 → every even number ends in 0; odd in 1.
3 Ternary b₃ Sum of digits ≡ N (mod 2).
4 Quaternary b₄ Powers of 4 give sums of digits ≡ N (mod 3).
5 Quinary b₅ Divisibility by 5 ⇔ last digit 0 or 5.
8 Octal b₈ Octal representation is convenient for binary packing.
10 Decimal b₁₀ Standard counting system.
16 Hexadecimal b₁₆ b₁₆ = 2⁴. Hex digits 0–9, A–F.
32 Base‑32 b₃₂ Useful in QR codes, base‑32 encoding.

3. Conversion Algorithms

3.1 Decimal → Base‑b (Integer part)

while N > 0:
    r = N mod b
    prepend r to result
    N = floor(N / b)

Complexity: O(log_b N).

3.2 Base‑b → Decimal

N = 0
for each digit d in representation:
    N = N * b + d

3.3 Decimal Fraction → Base‑b (Fractional part)

frac = fractional part of N
while frac ≠ 0 and precision not reached:
    frac = frac * b
    digit = floor(frac)
    append digit to result
    frac = frac - digit

Edge case: Non‑terminating representation when b and denominator are not coprime (e.g., 1/3 in binary).

3.4 Base‑b Fraction → Decimal

frac = 0
for i from 1 to length:
    digit = representation[i]
    frac += digit / (b^i)

4. Arithmetic in Non‑Decimal Bases

4.1 Addition

Same as decimal, but carry threshold is b. Example (Base‑8):

  345₈
+ 167₈
-------
  546₈

Because 5+7=12₈ → write 2, carry 1.

4.2 Multiplication

Use partial products or shift‑and‑add. In binary, multiplication by 2^k is a left shift.

4.3 Division

Long division works with base b. Remainder < b.

4.4 Modulo Properties

a ≡ b (mod m) iff a and b have the same remainder when divided by m.
Useful for divisibility tests in any base:

Base Divisibility Rule
2 Last digit even
3 Sum of digits mod 3
4 Last two digits mod 4
5 Last digit 0 or 5
8 Last three digits mod 8
16 Last two hex digits mod 16

5. Advanced Topics

5.1 Mixed‑Radix Systems

  • Time: 1h = 60 min, 1 min = 60 s → base 60 at each level.
  • Calendar: 12 months, 30 days, 24 hours → a mixed base system.

Conversion: Treat each level as a digit in a base that is the product of all lower bases.

5.2 Gray Code (Binary Reflected Gray Code)

  • Sequence where successive numbers differ by one bit.
  • Useful for error detection in digital signals.

Construction:

  1. Start with 0 and 1.
  2. Reflect list and prefix 0 to first half, 1 to second half.

5.3 Negative Bases

  • Base -2 representation can encode all integers without a sign.
  • Rule: For N, repeatedly divide by -2, recording remainders 0 or 1.

**Example

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.