Number Series & Math

A prime number is greater than 1 and has no divisors other than 1 and itself: 2, 3, 5, 7, 11, 13...

Only check divisors up to √n — if n had a factor larger than √n, its pair would be smaller than √n and already found.

Handle special cases: 2 is the only even prime; all other even numbers and multiples of 3 can be eliminated fast.

function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i <= Math.sqrt(n); i++)
    if (n % i === 0) return false;
  return true;
}
// Input: 2   => Output: true
// Input: 17  => Output: true
// Input: 25  => Output: false (5×5)
// Input: 1   => Output: false (not prime by definition)

Optimization: After checking 2 and 3, only test 6k ± 1 candidates to skip 2/3 of checks.

Time: O(√n). For large n, use Miller-Rabin primality test for probabilistic O(k log² n) checking.

The factorial of n (written n!) is the product of all positive integers from 1 to n: n! = 1 × 2 × 3 × ... × n.

Base case: 0! = 1 (by convention) and 1! = 1. For negative n, factorial is undefined.

Both recursive and iterative implementations are common; iterative avoids stack overflow for large n.

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
// Iterative version:
function factIter(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}
// Input: 0   => Output: 1
// Input: 5   => Output: 120  (1×2×3×4×5)
// Input: 10  => Output: 3628800

Growth rate: factorial grows faster than exponential. 20! = 2,432,902,008,176,640,000 — needs BigInt for n>18.

Factorial appears in permutations (n!), combinations (n!/k!(n-k)!), and Taylor series expansions.

The Greatest Common Divisor (GCD) is the largest number that divides both a and b without remainder. GCD(12,8) = 4.

The Euclidean Algorithm: replace (a, b) with (b, a % b) repeatedly until b = 0. The remaining value in a is the GCD.

This runs in O(log(min(a,b))) time — one of the oldest and most efficient algorithms, dating back to 300 BCE.

function gcd(a, b) {
  while (b) { [a, b] = [b, a % b]; }
  return a;
}
// Recursive version:
function gcdRec(a, b) { return b === 0 ? a : gcdRec(b, a % b); }
// Input: 12, 8    => Output: 4
// Input: 48, 18   => Output: 6
// Input: 100, 75  => Output: 25

GCD property: GCD(a, b) = GCD(b, a%b). Proof: any divisor of a and b also divides a%b.

GCD is used in fraction simplification, cryptography (RSA), and scheduling problems.

An Armstrong (narcissistic) number equals the sum of its digits each raised to the power of the total number of digits.

For 153: 3 digits, so check 1³ + 5³ + 3³ = 1 + 125 + 27 = 153 ✓. Each digit is raised to the SAME power (total digits).

Convert n to string to count digits and extract each digit easily using split and reduce.

function isArmstrong(n) {
  let digits = String(n).split('');
  let len = digits.length;
  let sum = digits.reduce((s, d) => s + Math.pow(+d, len), 0);
  return sum === n;
}
// Input: 153  => Output: true  (1³+5³+3³=153)
// Input: 370  => Output: true  (3³+7³+0³=370)
// Input: 9474 => Output: true  (9⁴+4⁴+7⁴+4⁴=9474)
// Input: 123  => Output: false

3-digit Armstrong numbers: 153, 370, 371, 407. Single digits (0-9) are all Armstrong numbers.

There are finitely many Armstrong numbers in base 10 — 89 total, the largest is 115132219018763992565095597973971522401.

A palindromic number reads the same forwards and backwards: 121, 1331, 12321 are examples. Negative numbers are not palindromes.

The simplest approach: convert to string and compare with its reverse. Alternatively, reverse mathematically without string conversion.

The mathematical reversal is more memory-efficient and handles leading zeros naturally (e.g., 100 reversed = 001 = 1 ≠ 100).

function isPalindromeNum(n) {
  if (n < 0) return false;
  let str = String(n);
  return str === str.split('').reverse().join('');
}
// Mathematical reversal:
function isPalindromeNumMath(n) {
  if (n < 0) return false;
  let original = n, rev = 0;
  while (n > 0) { rev = rev * 10 + n % 10; n = Math.floor(n / 10); }
  return rev === original;
}
// Input: 121   => Output: true
// Input: 1221  => Output: true
// Input: 123   => Output: false

Trick: Only need to reverse half the number and compare with the other half for O(log n / 2) time.

All single-digit numbers are palindromes. Numbers ending in 0 (except 0 itself) are never palindromes.

The digit sum adds all individual digits together: digits of 9537 → 9+5+3+7 = 24.

The iterative approach extracts each digit using n % 10 and removes it using Math.floor(n / 10).

For negative numbers, use Math.abs(n) first since negative sign is not a digit.

function sumDigits(n) {
  let sum = 0;
  n = Math.abs(n);
  while (n > 0) { sum += n % 10; n = Math.floor(n / 10); }
  return sum;
}
// String version: +d converts '5' => 5
function sumDigitsStr(n) {
  return String(Math.abs(n)).split('').reduce((s, d) => s + +d, 0);
}
// Input: 9537  => Output: 24  (9+5+3+7)
// Input: 0     => Output: 0
// Input: -123  => Output: 6   (1+2+3)

Divisibility rule: a number is divisible by 9 if and only if its digit sum is divisible by 9.

Repeated digit summing until single digit = digital root, which can be computed in O(1) using modulo 9.

Reversing an integer extracts digits from the right end one by one and builds the reversed number from left to right.

Use n % 10 to get the last digit, multiply rev by 10 and add it, then remove the last digit: n = Math.floor(n / 10).

Preserve the sign separately with Math.sign(n) and work with absolute value to simplify the loop.

function reverseInt(n) {
  let sign = Math.sign(n), rev = 0;
  n = Math.abs(n);
  while (n > 0) { rev = rev * 10 + n % 10; n = Math.floor(n / 10); }
  return rev * sign;
}
// Input: 1234   => Output: 4321
// Input: -567   => Output: -765
// Input: 1000   => Output: 1 (leading zeros dropped)
// Input: 0      => Output: 0

Overflow check: If reversed > 2³¹-1 or < -2³¹, return 0 (important for 32-bit integer constraints in LeetCode).

Numbers ending in 0 lose trailing zeros when reversed: 100 → 1. This is expected behavior.

A perfect number equals the sum of all its proper divisors (all divisors except itself). The first perfect number is 6 = 1+2+3.

Efficiently find all divisors up to √n: for each divisor i, add both i and n/i to the sum (handling the case when i = √n to avoid double-counting).

Start the sum at 1 (which is always a proper divisor of any n ≥ 2) and check divisors from 2 to √n.

function isPerfect(n) {
  if (n < 2) return false;
  let sum = 1;
  for (let i = 2; i <= Math.sqrt(n); i++)
    if (n % i === 0) sum += i + (i !== n/i ? n/i : 0);
  return sum === n;
}
// Input: 1     => Output: false
// Input: 6     => Output: true  (1+2+3=6)
// Input: 28    => Output: true  (1+2+4+7+14=28)
// Input: 496   => Output: true  (sum of divisors = 496)

All known perfect numbers: 6, 28, 496, 8128, 33550336, 8589869056... (extremely rare).

All even perfect numbers have the form 2^p-1(2^p-1) where (2^p-1) is a Mersenne prime. No odd perfect number has ever been found.

A power of two in binary has exactly one bit set to 1 (e.g., 1=0001, 2=0010, 4=0100, 8=1000).

The bitwise trick: n & (n - 1) turns off the lowest set bit. If the result is 0, exactly one bit was set, meaning n is a power of two.

Also check n > 0 since the trick gives false positive for n=0.

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}
// Input: 1   => Output: true  (2^0)
// Input: 16  => Output: true  (2^4 = 10000 in binary)
// Input: 18  => Output: false (10010 — two bits set)

Binary of powers of 2: 1, 10, 100, 1000 — always a single 1 followed by zeros.

This trick also checks for powers of any number if generalized with repeated division.

The Least Common Multiple (LCM) of two numbers is the smallest positive integer divisible by both.

The efficient formula uses GCD: LCM(a, b) = (a * b) / GCD(a, b). First find GCD using the Euclidean algorithm, then apply this formula.

Never compute LCM by brute-force iteration — always use the GCD-based formula for efficiency.

function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
function lcm(a, b) { return (a * b) / gcd(a, b); }
// Input: a=4, b=6    => Output: 12 (4*6/2=12)
// Input: a=12, b=18  => Output: 36 (12*18/6=36)
// Input: a=7, b=5    => Output: 35 (coprime: LCM = product)

LCM(a,b) * GCD(a,b) = a * b — always true, useful for verification.

For multiple numbers: LCM(a,b,c) = LCM(LCM(a,b), c). Reduce using the pair formula repeatedly.

The digital root is obtained by repeatedly summing digits until a single digit remains. For 493 → 4+9+3=16 → 1+6=7, so digital root = 7.

The mathematical shortcut: digital root = 1 + (n - 1) % 9, handling edge case n=0.

This is useful in divisibility checks and cast out nines verification.

function digitalRoot(n) {
  if (n === 0) return 0;
  return 1 + (n - 1) % 9;
}
// Iterative version:
function digitalRootIter(n) {
  while (n >= 10) {
    n = String(n).split('').reduce((s, d) => s + +d, 0);
  }
  return n;
}
// Input: 493  => Output: 7  (4+9+3=16 → 1+6=7)
// Input: 9    => Output: 9
// Input: 0    => Output: 0

Pattern: digital root of n = n % 9 for n>0, with 9 instead of 0 when n is divisible by 9.

Digital roots are used in checksum verification for credit card numbers and ISBN codes.

A Harshad number is divisible by the sum of its own digits. For example, 18 is Harshad because 1+8=9 and 18%9=0.

Compute the digit sum, then check if n % digitSum === 0.

Harshad means "joy-giving" in Sanskrit — these numbers have a special divisibility property.

function isHarshad(n) {
  let sum = String(n).split('').reduce((s, d) => s + +d, 0);
  return n % sum === 0;
}
// Input: 18  => Output: true  (1+8=9, 18%9=0)
// Input: 21  => Output: true  (2+1=3, 21%3=0)
// Input: 19  => Output: false (1+9=10, 19%10=9)

All single digits (1-9) are Harshad numbers since digit sum = n and n%n = 0.

Related: a super-Harshad number remains Harshad when its digit sum itself is also Harshad.

A strong number equals the sum of the factorials of its digits. For example, 145 = 1! + 4! + 5! = 1 + 24 + 120 = 145.

Break the number into digits, compute factorial of each, and check if their sum equals the original number.

Precomputing factorials 0! to 9! in an array speeds up the checking for large inputs.

function isStrong(n) {
  const fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880];
  let sum = String(n).split('').reduce((s, d) => s + fact[+d], 0);
  return sum === n;
}
// Input: 1   => Output: true  (1! = 1)
// Input: 2   => Output: true  (2! = 2)
// Input: 145 => Output: true  (1!+4!+5! = 1+24+120 = 145)
// Input: 123 => Output: false (1!+2!+3! = 1+2+6 = 9 ≠ 123)

There are only 4 strong numbers: 1, 2, 145, and 40585.

Also called factorions. Factorial sum for 10+ digit numbers always stays small, so all factorions are known.

A perfect square is a number that is the square of an integer: 1, 4, 9, 16, 25, etc.

Compute the integer square root via Math.sqrt, round it, and check if the square equals n. Use Math.round to avoid floating point errors.

Floating point check: Math.sqrt(n) % 1 === 0 can fail for large numbers due to precision loss.

function isPerfectSquare(n) {
  if (n < 0) return false;
  let sqrt = Math.round(Math.sqrt(n));
  return sqrt * sqrt === n;
}
// Input: 25  => Output: true  (√25 = 5)
// Input: 36  => Output: true  (√36 = 6)
// Input: 14  => Output: false (√14 ≈ 3.74)
// Input: 0   => Output: true  (0 = 0²)

Safer check: compute isqrt via binary search for very large numbers to avoid floating-point issues.

Perfect squares have an odd number of divisors — this helps verify them without computation.

Triangular numbers are formed by the formula n*(n+1)/2: 1, 3, 6, 10, 15, 21, 28...

To check if x is triangular, solve n*(n+1)/2 = x → 8x+1 must be a perfect square. If √(8x+1) is an integer, x is triangular.

This mathematical trick avoids iteration and runs in O(1) time.

function isTriangular(x) {
  let disc = 8 * x + 1;
  let sqrt = Math.round(Math.sqrt(disc));
  return sqrt * sqrt === disc;
}
// Input: 1   => Output: true  (T1 = 1)
// Input: 10  => Output: true  (T4 = 10 = 1+2+3+4)
// Input: 21  => Output: true  (T6 = 21)
// Input: 5   => Output: false

Formula: n-th triangular number = 1+2+3+...+n = n*(n+1)/2.

Triangular numbers appear in combinatorics as the count of handshakes or pair combinations: C(n+1, 2).

The nth prime is the n-th number in the sequence 2, 3, 5, 7, 11, 13, 17...

Iterate numbers starting from 2, check each for primality using trial division up to √candidate, count primes until you reach the nth one.

For small n use the simple approach; for large n use the Sieve of Eratosthenes with an estimated upper bound.

function nthPrime(n) {
  let count = 0, num = 1;
  while (count < n) {
    num++;
    let isPrime = true;
    for (let i = 2; i <= Math.sqrt(num); i++) {
      if (num % i === 0) { isPrime = false; break; }
    }
    if (isPrime) count++;
  }
  return num;
}
// Input: 1   => Output: 2
// Input: 5   => Output: 11
// Input: 10  => Output: 29

Time: O(n * √n) for simple approach. Use Sieve for O(n log log n) when n is large.

The prime counting function π(n) ≈ n/ln(n) — so the nth prime is approximately n*ln(n).

The Collatz conjecture: start with any positive integer. If even → divide by 2; if odd → multiply by 3 and add 1. The sequence always eventually reaches 1.

Generate the sequence by applying the rule until n = 1. The conjecture has never been proven but no counterexample has been found.

The Collatz sequence is a famous unsolved problem — it's easy to understand but mathematically deep.

function collatz(n) {
  let seq = [n];
  while (n !== 1) {
    n = n % 2 === 0 ? n / 2 : 3 * n + 1;
    seq.push(n);
  }
  return seq;
}
// Input: 6   => Output: [6,3,10,5,16,8,4,2,1]  (length=9)
// Input: 27  => Output: length 112 (longest for small numbers)
// Input: 1   => Output: [1]

Conjecture: every positive integer eventually reaches 1. Verified up to 2⁶⁸ but unproven.

For interview purposes, the key test cases are n=1 (already done) and very large n with long sequences.

Counting digits in a number n can be done by repeatedly dividing by 10 and counting iterations, or using the mathematical formula Math.floor(Math.log10(n)) + 1.

The string conversion approach String(Math.abs(n)).length is the simplest but slightly slower due to allocation.

Handle edge case: n = 0 has 1 digit; negative numbers have the same digit count as their absolute value.

function countDigits(n) {
  if (n === 0) return 1;
  n = Math.abs(n);
  let count = 0;
  while (n > 0) { n = Math.floor(n / 10); count++; }
  return count;
}
// Math-based (O(1)):
function countDigitsMath(n) {
  return n === 0 ? 1 : Math.floor(Math.log10(Math.abs(n))) + 1;
}
// Input: 0     => Output: 1
// Input: 12345 => Output: 5
// Input: -987  => Output: 3

Math formula: ⌊log₁₀(n)⌋ + 1. This runs in O(1) vs O(log n) for the iterative approach.

The digit count determines padding width for formatted output in multiplication tables and matrices.

An automorphic number is one whose square ends with the number itself. For example, 5² = 25 (ends with 5), 6² = 36 (ends with 6), 76² = 5776 (ends with 76).

Square n and check if the last digits of n² match n — use modulo by 10^(number of digits in n).

Also called trimorphic numbers or automorphs, these have applications in modular arithmetic.

function isAutomorphic(n) {
  let square = n * n;
  let digits = String(n).length;
  return square % Math.pow(10, digits) === n;
}
// Input: 5    => Output: true  (5²=25, 25%10=5)
// Input: 6    => Output: true  (6²=36, 36%10=6)
// Input: 25   => Output: true  (25²=625, 625%100=25)
// Input: 76   => Output: true  (76²=5776, 5776%100=76)
// Input: 7    => Output: false (7²=49, 49%10=9≠7)

The automorphic property is preserved under squaring: 5→25→625→390625 — all end in 625 (automorphic).

Known automorphs modulo 10^k: ...0, 1, 5, 6, 25, 76, 376, 625, 9376, 90625...

To find the sum of all primes ≤ n, first generate all primes using the Sieve of Eratosthenes, then sum them.

The sieve marks composites efficiently: start by marking multiples of each prime from 2 upward, skipping those already marked.

Combining the sieve with reduction is O(n log log n) — optimal for prime summation up to large n.

function sumPrimes(n) {
  let sieve = new Array(n + 1).fill(true);
  sieve[0] = sieve[1] = false;
  for (let i = 2; i * i <= n; i++)
    if (sieve[i]) for (let j = i*i; j <= n; j += i) sieve[j] = false;
  return sieve.reduce((sum, isPrime, num) => isPrime ? sum + num : sum, 0);
}
// Input: 10  => Output: 17  (2+3+5+7=17)
// Input: 20  => Output: 77  (2+3+5+7+11+13+17+19=77)
// Input: 5   => Output: 10  (2+3+5=10)

Sieve time: O(n log log n). Space: O(n) for the boolean array.

The sum of primes up to n grows approximately as n²/(2 ln n) by the prime counting function.

A Disarium number equals the sum of its digits each raised to the power of their position (1-indexed from left). For example, 89 = 8¹ + 9² = 8 + 81 = 89.

Convert the number to a string to easily access each digit and its index, then compute the positional power sum.

This is similar to Armstrong numbers but uses POSITION as the exponent instead of the total digit count.

function isDisarium(n) {
  let str = String(n);
  let sum = str.split('').reduce((s, d, i) => s + Math.pow(+d, i + 1), 0);
  return sum === n;
}
// Input: 89   => Output: true  (8^1 + 9^2 = 8+81 = 89)
// Input: 175  => Output: true  (1^1 + 7^2 + 5^3 = 1+49+125 = 175)
// Input: 135  => Output: true  (1^1 + 3^2 + 5^3 = 1+9+125 = 135)
// Input: 123  => Output: false (1+9+27 = 37 ≠ 123)

Known Disarium numbers: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 89, 135, 175, 518, 598, 1306.

The key difference from Armstrong: Disarium uses index as exponent; Armstrong uses total digit count.

Twin primes are pairs of prime numbers that differ by exactly 2: (3,5), (5,7), (11,13), (17,19), (29,31), etc.

Generate all primes up to n using the sieve, then scan consecutive primes checking if their difference is 2.

Twin prime conjecture states there are infinitely many twin prime pairs, but this remains unproven.

function twinPrimes(n) {
  let sieve = new Array(n + 1).fill(true);
  sieve[0] = sieve[1] = false;
  for (let i = 2; i * i <= n; i++)
    if (sieve[i]) for (let j = i*i; j <= n; j += i) sieve[j] = false;
  let pairs = [];
  for (let i = 2; i < n; i++)
    if (sieve[i] && sieve[i + 2]) pairs.push([i, i + 2]);
  return pairs;
}
// Input: 20  => Output: [[3,5],[5,7],[11,13],[17,19]]
// Input: 30  => Output: [[3,5],[5,7],[11,13],[17,19],[29,31]]

Largest known twin prime (2024): 2996863034895 × 2^1290000 ± 1, with 388,342 digits each.

All twin primes greater than 3 are of the form (6n-1, 6n+1) — useful for optimizing the search.

Based on sum of proper divisors (all divisors excluding n itself): a number is abundant if divisor sum > n, deficient if < n, or perfect if = n.

For each number, compute the sum of all divisors up to √n using paired divisor logic (i and n/i), then classify.

This is a great warmup problem for proving correct divisor enumeration logic.

function classify(n) {
  let sum = 1;
  for (let i = 2; i <= Math.sqrt(n); i++)
    if (n % i === 0) sum += i + (i !== n/i ? n/i : 0);
  if (sum === n) return 'perfect';
  return sum > n ? 'abundant' : 'deficient';
}
// Input: 6   => Output: "perfect"   (1+2+3=6)
// Input: 12  => Output: "abundant"  (1+2+3+4+6=16 > 12)
// Input: 8   => Output: "deficient" (1+2+4=7 < 8)

The only known perfect numbers less than 10²⁰ are: 6, 28, 496, 8128, 33550336...

All even perfect numbers follow the Euler-Euclid theorem: P = 2^p-1(2^p-1) where (2^p-1) is a Mersenne prime.