Number Theory and Pattern Puzzles Short Notes for XAT: Concepts, Formulas, Worked Examples & Practice

Number Theory and Pattern Puzzles short notes for XAT: 1 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Final Exam Strategy & Cheat Sheet

Factors & Divisibility

Total factors of

p^{a} q^{b}

(a + 1) (b + 1)

Sum of factors uses the geometric series formula.

HCF vs LCM

HCF = Intersection of primes (lowest powers). Used for "Maximum" / "Largest".

LCM = Union of primes (highest powers). Used for "Minimum" / "Smallest" / "Syncing".

HCF \times LCM = A \times B

(Only for 2 numbers).

Remainders & Cyclicity

Use negative remainders for bases close to the divisor.

Cyclicity of unit digits:

{0, 1, 5, 6} \to 1

;

{4, 9} \to 2

;

{2, 3, 7, 8} \to 4

Factorials

Trailing zeros in

n!

= Highest power of

5

n!

Pattern Puzzles

Cyclic operations: Simulate

\to

Find Loop

\to

Modulo.

Coprime in range

[2, M]

: Count primes

> M /2

Max GCD with sum

S

g \leq \frac{2 S}{k ( k + 1 )}

and

g

divides

S

Number Theory and Pattern Puzzles: Solved Questions with Step-by-Step Explanations (2 Problems)

Question 1 · Quantitative Aptitude and Data Interpretation (QA & DI) MCQ

For which of the following sets of three positive integers ${X, Y, Z}$ will the incorrect formula $X \times Y \times Z = HCF \times LCM$ accidentally yield the correct product?

A.
{2, 3, 4}
B.
{2, 3, 6}
C.
{3, 4, 1}
D.
{2, 4, 8}

Correct Answer:

Step-by-Step Solution

Key idea: This is a Cheat Sheet / Strategy question testing the boundary of the formula $HCF \times LCM = A \times B$ .

Step 1: Recall the rule.

The formula $HCF \times LCM = Product$ is ONLY valid for TWO numbers. For three numbers, it is generally false.

Step 2: Test the options to find the exception.

We need a set where $X \cdot Y \cdot Z = HCF (X, Y, Z) \times LCM (X, Y, Z)$ .

Option A: {2, 3, 4}

HCF = 1, LCM = 12. Product = 24. Formula = 12. (False)

Option B: {2, 3, 6}

HCF = 1, LCM = 6. Product = 36. Formula = 6. (False)

Option C: {3, 4, 1}

HCF = 1, LCM = 12. Product = 12. Formula = 1 * 12 = 12. (True!)

Option D: {2, 4, 8}

HCF = 2, LCM = 8. Product = 64. Formula = 16. (False)

Step 3: Understand why C works.

When one of the numbers is 1, the HCF of the set becomes 1.

The LCM of the set becomes the LCM of the other two numbers.

So the formula gives $1 \times LCM (X, Y)$ .

The actual product is $X \cdot Y \cdot 1 = X \cdot Y$ .

These are equal if and only if $X \cdot Y = LCM (X, Y)$ , which happens when $X$ and $Y$ are coprime.

In {3, 4, 1}, 3 and 4 are coprime.

Answer: {3, 4, 1}.

Question 2 · Quantitative Aptitude and Data Interpretation (QA & DI) MCQ

Let $Z (N)$ be the number of trailing zeros of $N!$ when expressed in base 6. How many positive integers $N \leq 100$ satisfy the condition that $Z (N)$ is a perfect square?

A.
12
B.
14
C.
16
D.
18

Correct Answer:

Step-by-Step Solution

Key idea: This is a synthesis of Legendre's formula for trailing zeros in a non-decimal base and perfect square constraints. We must first determine the formula for $Z (N)$ in base 6, then count how many $N$ yield a perfect square result.

Step 1: Determine $Z (N)$ for base 6.

Base $6 = 2 \times 3$ . The number of trailing zeros is determined by the limiting prime factor in the prime factorization of $N!$ .

The exponent of a prime $p$ in $N!$ is $E_{p} (N!) = \sum_{k = 1}^{\infty} ⌊ \frac{N}{p ^{k}} ⌋$ .

For base 6, we need pairs of $(2, 3)$ . Since 3 is larger than 2, $E_{3} (N!) < E_{2} (N!)$ for all $N \geq 1$ . Thus, the number of trailing zeros is determined by the exponent of 3.

$Z (N) = E_{3} (N!) = ⌊ \frac{N}{3} ⌋ + ⌊ \frac{N}{9} ⌋ + ⌊ \frac{N}{27} ⌋ + \dots$

Step 2: Analyze the range $N \leq 100$ .

We need to find $N$ such that $Z (N) = k^{2}$ for some integer $k$ .

Let's estimate the maximum value of $Z (100)$ .

$Z (100) = ⌊ \frac{100}{3} ⌋ + ⌊ \frac{100}{9} ⌋ + ⌊ \frac{100}{27} ⌋ + ⌊ \frac{100}{81} ⌋ = 33 + 11 + 3 + 1 = 48$ .

So possible perfect squares for $Z (N)$ are $0, 1, 4, 9, 16, 25, 36, 49$ (but max is 48, so up to 36).

Step 3: Count $N$ for each perfect square value $S \in {0, 1, 4, 9, 16, 25, 36}$ .

Note that $Z (N)$ is a non-decreasing step function. It stays constant for intervals of 3, except at multiples of 9, 27, etc., where it jumps more.

$Z (N) = 0$ : $⌊ N /3 ⌋ = 0 ⟹ N \in {1, 2}$ . (2 values)
$Z (N) = 1$ : $⌊ N /3 ⌋ + \dots = 1$ .

$N = 3 ⟹ 1 + 0 = 1$ .

$N = 4 ⟹ 1 + 0 = 1$ .

$N = 5 ⟹ 1 + 0 = 1$ .

$N = 6 ⟹ 2 + 0 = 2$ .

So $N \in {3, 4, 5}$ . (3 values)

$Z (N) = 4$ :

Check $N$ around $3 \times 4 = 12$ .

$N = 9 ⟹ 3 + 1 = 4$ .

$N = 10 ⟹ 3 + 1 = 4$ .

$N = 11 ⟹ 3 + 1 = 4$ .

$N = 12 ⟹ 4 + 1 = 5$ .

So $N \in {9, 10, 11}$ . (3 values)

$Z (N) = 9$ :

Check $N$ around $3 \times 9 = 27$ ? No, approx $N \approx 3 \times 9 = 27$ is too high because of higher powers.

Let's test values.

$N = 12 \to 5$ .

$N = 15 \to 5 + 1 = 6$ .

$N = 18 \to 6 + 2 = 8$ .

$N = 19 \to 6 + 2 = 8$ .

$N = 20 \to 6 + 2 = 8$ .

$N = 21 \to 7 + 2 = 9$ .

$N = 22 \to 7 + 2 = 9$ .

$N = 23 \to 7 + 2 = 9$ .

$N = 24 \to 8 + 2 = 10$ .

So $N \in {21, 22, 23}$ . (3 values)

$Z (N) = 16$ :

$N = 30 \to 10 + 3 = 13$ .

$N = 33 \to 11 + 3 = 14$ .

$N = 36 \to 12 + 4 = 16$ .

$N = 37 \to 12 + 4 = 16$ .

$N = 38 \to 12 + 4 = 16$ .

$N = 39 \to 13 + 4 = 17$ .

So $N \in {36, 37, 38}$ . (3 values)

$Z (N) = 25$ :

$N = 45 \to 15 + 5 = 20$ .

$N = 48 \to 16 + 5 = 21$ .

$N = 51 \to 17 + 5 = 22$ .

$N = 54 \to 18 + 6 = 24$ .

$N = 55 \to 18 + 6 = 24$ .

$N = 56 \to 18 + 6 = 24$ .

$N = 57 \to 19 + 6 = 25$ .

$N = 58 \to 19 + 6 = 25$ .

$N = 59 \to 19 + 6 = 25$ .

$N = 60 \to 20 + 6 = 26$ .

So $N \in {57, 58, 59}$ . (3 values)

$Z (N) = 36$ :

$N = 72 \to 24 + 8 = 32$ .

$N = 75 \to 25 + 8 = 33$ .

$N = 78 \to 26 + 8 = 34$ .

$N = 81 \to 27 + 9 + 3 = 39$ (Jump!).

Wait, let's check near 81 carefully.

$N = 80 \to 26 + 8 + 2 = 36$ .

$N = 79 \to 26 + 8 + 2 = 36$ .

$N = 78 \to 26 + 8 + 2 = 36$ ? No. $⌊ 78/27 ⌋ = 2$ . $⌊ 78/9 ⌋ = 8$ . $⌊ 78/3 ⌋ = 26$ . Sum = 36.

$N = 77 \to 25 + 8 + 2 = 35$ .

So $N \in {78, 79, 80}$ . (3 values)

Total count = $2 + 3 + 3 + 3 + 3 + 3 + 3 = 20$ ?

Let me re-evaluate $Z (N) = 0$ . $N = 1, 2$ . Correct.

Let me re-evaluate ranges.

Usually, for large $N$ , $Z (N)$ increases by 1 every 3 numbers, but jumps by extra amounts at multiples of 9, 27, etc.

The number of solutions for $Z (N) = k$ is typically 3, unless $k$ is hit exactly at a jump point where it might skip or have fewer/more.

Actually, $Z (N)$ takes every integer value?

$Z (1) = 0, Z (2) = 0$ . (2 vals)

$Z (3) = 1, Z (4) = 1, Z (5) = 1$ . (3 vals)

$Z (6) = 2, Z (7) = 2, Z (8) = 2$ . (3 vals)

$Z (9) = 4$ . Skips 3.

So $Z (N) = 3$ has 0 solutions.

$Z (10) = 4, Z (11) = 4$ . (3 vals for 4? No, $Z (9) = 4$ too. So 9,10,11. 3 vals).

$Z (12) = 5, 13 = 5, 14 = 5$ . (3 vals).

$Z (15) = 6, 16 = 6, 17 = 6$ . (3 vals).

$Z (18) = 8$ . Skips 7.

$Z (19) = 8, 20 = 8$ . ( $Z (18) = 8$ too. So 18,19,20. 3 vals).

$Z (21) = 9, 22 = 9, 23 = 9$ . (3 vals).

Squares: 0, 1, 4, 9, 16, 25, 36.

Values skipped: 3, 7, ...

Are any squares skipped?

Sequence of Z(N): 0,0, 1,1,1, 2,2,2, 4,4,4, 5,5,5, 6,6,6, 8,8,8, 9,9,9...

Squares present:

0: Yes (2 values)

1: Yes (3 values)

4: Yes (3 values)

9: Yes (3 values)

16: Yes (3 values)

25: Yes (3 values)

36: Yes (3 values)

Next square 49. $Z (100) = 48$ . $Z (101) = 48 + 0 = 48$ ? No.

$Z (100) = 48$ .

$Z (101) = 48$ .

$Z (102) = 49$ ? $⌊ 102/3 ⌋ = 34, ⌊ 102/9 ⌋ = 11, ⌊ 102/27 ⌋ = 3, ⌊ 102/81 ⌋ = 1$ . Sum=49.

But $N \leq 100$ . So 49 is not reached.

Total = $2 + 3 + 3 + 3 + 3 + 3 + 3 = 20$ .

Wait, did I miss any?

Options are 12, 14, 16, 18. My count 20 is not an option.

Let me re-read carefully. "Positive integers $N \leq 100$ ".

Did I calculate $Z (N)$ correctly?

Base 6. Limiting factor 3.

$Z (N) = E_{3} (N!)$ .

Let's re-verify the "skipped" values.

Jumps occur at multiples of 9 (jump +1 extra), 27 (jump +1 extra), 81 (jump +1 extra).

Normal increase is +1 every 3 N.

At $N = 9$ , $Z (8) = 2, Z (9) = 4$ . Jumped 3.

At $N = 18$ , $Z (17) = 6, Z (18) = 8$ . Jumped 7.

At $N = 27$ , $Z (26) = ?$ .

$Z (26) = 8 + 2 + 0 = 10$ ? No.

$Z (26) = ⌊ 26/3 ⌋ + ⌊ 26/9 ⌋ = 8 + 2 = 10$ .

$Z (27) = 9 + 3 + 1 = 13$ . Jumped 11, 12.

Squares:

0: $N = 1, 2$ . (2)

1: $N = 3, 4, 5$ . (3)

4: $N = 9, 10, 11$ . (3)

9: $N = 21, 22, 23$ . (3)

16: $N = 36, 37, 38$ . (3)

25: $N = 57, 58, 59$ . (3)

36: $N = 78, 79, 80$ . (3)

Is it possible that some squares are skipped?

Let's check 16 again.

$Z (35) = 11 + 3 + 1 = 15$ .

$Z (36) = 12 + 4 + 1 = 17$ ?

$⌊ 36/3 ⌋ = 12$ . $⌊ 36/9 ⌋ = 4$ . $⌊ 36/27 ⌋ = 1$ . Sum=17.

Ah! $Z (36) = 17$ .

$Z (35) = 15$ .

So 16 is SKIPPED.

Let's check 25 again.

$Z (56) = 18 + 6 + 2 = 26$ ?

$⌊ 56/3 ⌋ = 18$ . $⌊ 56/9 ⌋ = 6$ . $⌊ 56/27 ⌋ = 2$ . Sum=26.

$Z (55) = 18 + 6 + 2 = 26$ ?

$⌊ 55/3 ⌋ = 18$ . $⌊ 55/9 ⌋ = 6$ . $⌊ 55/27 ⌋ = 2$ . Sum=26.

$Z (54) = 18 + 6 + 2 = 26$ ?

$⌊ 54/3 ⌋ = 18$ . $⌊ 54/9 ⌋ = 6$ . $⌊ 54/27 ⌋ = 2$ . Sum=26.

$Z (53) = 17 + 5 + 1 = 23$ .

So 24, 25 are SKIPPED.

Let's check 36 again.

$Z (77) = 25 + 8 + 2 = 35$ .

$Z (78) = 26 + 8 + 2 = 36$ .

$Z (79) = 26 + 8 + 2 = 36$ .

$Z (80) = 26 + 8 + 2 = 36$ .

$Z (81) = 27 + 9 + 3 + 1 = 40$ .

So 36 is HIT. (3 values: 78, 79, 80).

Let's check 4, 9, 1, 0 again.

0: Hit.

1: Hit.

4: Hit.

9: Hit.

16: Skipped.

25: Skipped.

36: Hit.

Total = $2 (f or 0) + 3 (f or 1) + 3 (f or 4) + 3 (f or 9) + 3 (f or 36) = 14$ .

Answer: 14

Number Theory and Pattern Puzzles Short Notes for XAT: Concepts, Formulas, Worked Examples & Practice

Final Exam Strategy & Cheat Sheet

Number Theory and Pattern Puzzles: Solved Questions with Step-by-Step Explanations (2 Problems)

Step-by-Step Solution

Step-by-Step Solution

More short notes in this unit

A question from this chapter

Login to view the complete short notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course