Check Smith Number in PHP

Beginner
⏱️ 12 min read
📚 Updated: May 2026
🎯 2 Code Examples
Number theory

What you’ll learn

  • The definition of a Smith number (composite + matching digit sums).
  • Why the first sample program on some sites is wrong if it forgets the composite rule.
  • How to factor with trial division, add digit sums of each prime copy, and list Smith numbers up to 100.

Overview

A Smith number is a composite positive integer n such that the sum of the decimal digits of n equals the sum of the decimal digits of all primes in its prime factorization, counting multiplicity (so 4 = 2 × 2 contributes two twos).

Two programs

Check 85 (classic demo), then print every Smith number from 1 to 100.

Live preview

See digit sum, factor-digit sum, and whether n is composite—all in one box.

Correct definition

Primes are ruled out explicitly so answers match textbooks and OEIS-style lists.

Prerequisites

Loops, integer division, modulo, and the idea of prime factorization.

  • PHP functions, loops, and integer arithmetic with % and casting.
  • Knowing composite means “not prime and greater than 1.”

What is a Smith number?

Compute S(n) = sum of decimal digits of n. Factor n into primes and compute F(n) = sum of the decimal digits of each prime factor, written as many times as that factor appears. If n is composite and S(n) = F(n), then n is a Smith number.

Example 22: digits 2 + 2 = 4. Factorization 2 × 11: digit sums 2 and 1 + 1 = 2, total 4. Match, and 22 is composite—so 22 is Smith.

Smith composite and S = F
Prime never Smith (by definition)
Composite but not Smith e.g. 6, 8, 9

Why multiplicity matters

The number 27 = 33 uses the prime 3 three times. So F(27) = digit-sum(3) + digit-sum(3) + digit-sum(3) = 9. The digit sum of 27 is 2 + 7 = 9, so 27 is Smith. If you only counted distinct primes once, you would get the wrong answer.

Bug fix vs some sample code

A short program that only checks S(n) == F(n) without testing compositeness will label every prime as Smith, because for prime p, F(p) is just the digit sum of p. Always require composite.

Quick examples

85 Smith
S
8+5=13
F
5 + (1+7) = 13 from 5×17
7 Not Smith
Reason
Prime numbers are excluded by definition.

Takeaway: always factor completely, count repeated primes, and keep the composite gate.

Live preview

Trial factorization in the browser (same idea as the PHP code). Very large inputs may be capped for speed.

Use a positive integer. Preview limited roughly to n ≤ 1012.

Live result
Press “Run check”.

Algorithm

Goal: return true if and only if n is a Smith number.

Reject small or prime values

If n ≤ 1 or n is prime, it cannot be Smith.

Compute S(n)

Repeatedly take n % 10 and divide by 10 until the copy is zero.

Compute F(n)

Trial-divide starting at 2. Each time p divides the working copy, add S(p) once and strip p. After the loop, if anything remains above 1, it is a large prime factor—add S of that too.

Compare

Smith if and only if S(n) == F(n) (we already know n is composite).

📜 Pseudocode

Pseudocode
function digitSum(x):
    s ← 0
    while x > 0:
        s ← s + (x mod 10)
        x ← floor(x / 10)
    return s

function factorDigitSum(n):
    s ← 0
    t ← n
    p ← 2
    while p * p ≤ t:
        while t mod p = 0:
            s ← s + digitSum(p)
            t ← t / p
        p ← p + 1
    if t > 1:
        s ← s + digitSum(t)
    return s

function isSmith(n):
    if n ≤ 1 or isPrime(n):
        return false
    return digitSum(n) = factorDigitSum(n)
1

Check a single number

Uses $i <= (int)($x / $i) in the factorization loop (avoid unnecessary wide multiplications). Important: isSmith returns false for primes so 7, 13, etc. are never mislabeled.

php
<?php
function digitSum(int $n): int
{
    $sum = 0;
    while ($n > 0) {
        $sum += $n % 10;
        $n = (int)($n / 10);
    }
    return $sum;
}

function isPrime(int $n): bool
{
    if ($n <= 1) {
        return false;
    }
    if ($n === 2) {
        return true;
    }
    if ($n % 2 === 0) {
        return false;
    }
    for ($i = 3; $i <= (int)($n / $i); $i += 2) {
        if ($n % $i === 0) {
            return false;
        }
    }
    return true;
}

function factorDigitSum(int $n): int
{
    $sum = 0;
    $x = $n;

    for ($i = 2; $i <= (int)($x / $i); $i++) {
        while ($x % $i === 0) {
            $sum += digitSum($i);
            $x = (int)($x / $i);
        }
    }
    if ($x > 1) {
        $sum += digitSum($x);
    }
    return $sum;
}

function isSmith(int $n): bool
{
    if ($n <= 1 || isPrime($n)) {
        return false;
    }
    return digitSum($n) === factorDigitSum($n);
}

$number = 85;

if (isSmith($number)) {
    echo $number . " is a Smith Number.\n";
} else {
    echo $number . " is not a Smith Number.\n";
}
?>

Explanation

factor_digit_sum walks trial divisors. Each time it removes a prime i, it adds the digit sum of i (so 11 adds 1+1, not 11 as a single “digit”).

if (n <= 1 || is_prime(n)) return 0;

Definition guard. This is the line many short tutorials forget; without it, primes pass the digit-sum test by accident.

while (x % i == 0) { sum += digit_sum(i); x /= i; }

Multiplicity. Powers like 3k add S(3) exactly k times.

2

Smith numbers from 1 to 100

Same helpers; the outer loop is a straight scan. Output matches the classic list.

php
<?php
function digitSum(int $n): int
{
    $sum = 0;
    while ($n > 0) {
        $sum += $n % 10;
        $n = (int)($n / 10);
    }
    return $sum;
}

function isPrime(int $n): bool
{
    if ($n <= 1) {
        return false;
    }
    if ($n === 2) {
        return true;
    }
    if ($n % 2 === 0) {
        return false;
    }
    for ($i = 3; $i <= (int)($n / $i); $i += 2) {
        if ($n % $i === 0) {
            return false;
        }
    }
    return true;
}

function factorDigitSum(int $n): int
{
    $sum = 0;
    $x = $n;

    for ($i = 2; $i <= (int)($x / $i); $i++) {
        while ($x % $i === 0) {
            $sum += digitSum($i);
            $x = (int)($x / $i);
        }
    }
    if ($x > 1) {
        $sum += digitSum($x);
    }
    return $sum;
}

function isSmith(int $n): bool
{
    if ($n <= 1 || isPrime($n)) {
        return false;
    }
    return digitSum($n) === factorDigitSum($n);
}

echo "Smith Numbers in the Range 1 to 100:\n";
for ($i = 1; $i <= 100; $i++) {
    if (isSmith($i)) {
        echo $i . " ";
    }
}
echo "\n";
?>

Explanation

The range program is intentionally simple: one reliable isSmith, reused 100 times.

Efficiency notes

Factorization. Trial division up to √n is fine for interview sizes. Pollard Rho or sieves matter only for much larger cryptography-scale numbers.

Prime test. You can skip a separate is_prime if you track whether you stripped at least one factor and ended with x == 1 after factoring the original n—but a clear prime test is easier to read.

Interview: state the composite rule first, then explain multiplicity with a cube like 27.

❓ FAQ

Write a whole number in base ten and add its digits. Then factor it into primes (count repeats), and add the digits of each prime factor as it appears. If those two totals match and the number is composite (not prime), it is a Smith number.
That is the standard definition. A prime p has only one prime factor, p itself, so the factor-digit sum would always equal the digit sum of p. Every prime would look like a Smith number, which is not interesting - so mathematicians exclude primes.
Yes. It is composite: 4 equals 2 times 2. Digit sum of 4 is 4. Each factor is 2, digit sum 2, twice gives 2 plus 2 equals 4.
Yes. Eighty-five is 5 times 17. Digit sum is 8 plus 5 equals 13. Factor-digit sum is digit sum of 5 (which is 5) plus digit sum of 17 (1 plus 7 equals 8), and 5 plus 8 equals 13.
No. Seven is prime, so it is not a Smith number under the usual definition - even though a buggy program might compare digit sums incorrectly.
No. You always use the full prime factorization with multiplicity. Multiplying primes in a different order does not change which primes appear or how many times each appears.

🔄 Input / output examples

nSmith?Note
85Yes5 × 17, digit sums match
7NoPrime
58Yes2 × 29
15No3 × 5: 1+5=6 vs 3+5=8

Edge cases and pitfalls

Most mistakes are definitional (forgetting composite) or implementation (not counting repeated factors).

n = 1

Not Smith

Not composite; both isSmith paths should reject it quickly.

Squares of primes

p2

Example 9 = 3 × 3: factor-digit sum is 3+3=6, digit sum of 9 is 9—not equal, so 9 is not Smith.

Overflow

Loop bounds

Prefer i <= x / i over i * i <= x for large x on fixed-width int.

⏱️ Time and space complexity

StepTime (trial division)Extra space
digit_sum(n)O(log n) digitsO(1)
factor_digit_sum(n)O(√n) worst caseO(1)
is_prime(n)O(√n)O(1)
Scan 1..Uabout O(U√U)O(1)

Summary

  • Definition: composite n with digit sum equal to sum of digit sums of prime factors with multiplicity.
  • Code: factor by trial division; never label primes as Smith.
  • Classic list to 100: 4 22 27 58 85 94.
Did you know?

Smith numbers are named after Albert Wilansky’s brother-in-law Harold Smith, who noticed 4937775 has this digit-sum property. The smallest is 4 (2 × 2: digit sum 4, factor-digit sum 2 + 2). Primes are never Smith numbers by definition.

About the author

Mari Selvan M P
Mari Selvan M P 🔗

Developer, cloud engineer, and technical writer

  • Experience 12 years building web and cloud systems
  • Focus Full Stack Development, AWS, and Developer Education

I write practical tutorials so students and working developers can learn by doing—from databases and APIs to deployment on AWS.

AWS Certified Developer – Associate (Credly)

9 people found this page helpful

PHP Program to find Composite Number PHP Program to Condense a Number