A Smith number is a composite integer whose digit sum equals the digit sum of its prime factors with multiplicity.
Remember
n is composite
AND DigitSum(n) == DigitSum of all prime factors (repeats count)
Examples: 4, 22, 27, 58, 85, 94
4 = 2 × 2 → 4 == 2 + 2
85 = 5 × 17 → 8+5 == 5 + (1+7)
27 = 3 × 3 × 3 → 2+7 == 3+3+3
n
Factors
Digit sum
Factor digits
Smith?
4
2 × 2
4
2 + 2 = 4
Yes
85
5 × 17
13
5 + 1 + 7 = 13
Yes
15
3 × 5
6
3 + 5 = 8
No
7
prime
—
—
No
Approach
How to Check a Smith Number in Python
Five clear steps — then reuse the helpers to list Smith numbers in a range.
Reject n ≤ 1 (not composite).
Factorize n with trial division (keep factors with multiplicity).
If only one prime factor appears once, n is prime → not Smith.
Compare digit_sum(n) with the digit sum of every factor.
Equal sums → Smith; otherwise not.
Helper
Job
Time
digit_sum
Sum digits of one integer
O(log n)
Factorize
Collect prime factors with repeats
O(√n)
is_smith
Composite + matching sums
O(√n)
Pseudocode
Pseudocode
function DigitSum(x):
s = 0
while x > 0:
s = s + (x % 10)
x = x / 10
return s
function IsSmith(n):
if n <= 1: return false
original = n
factorDigitSum = 0
factorCount = 0
// peel off factor 2
while n % 2 == 0:
factorDigitSum = factorDigitSum + DigitSum(2)
factorCount = factorCount + 1
n = n / 2
// odd factors
f = 3
while f * f <= n:
while n % f == 0:
factorDigitSum = factorDigitSum + DigitSum(f)
factorCount = factorCount + 1
n = n / f
f = f + 2
if n > 1: // leftover prime
factorDigitSum = factorDigitSum + DigitSum(n)
factorCount = factorCount + 1
if factorCount == 1: return false // prime
return DigitSum(original) == factorDigitSum
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Rule
Composite and digit_sum(n) == factor_digit_sum
Multiplicity
Count repeated factors (e.g. three 3’s in 27)
Primes
Never Smith
Smallest
4
Classic yes
4, 22, 27, 58, 85, 94
Classic no
1, 7 (prime), 15 (sums differ)
Try it
Live Preview
Enter an integer to factorize it and compare digit sums.
Whole numbers only. Tap a chip or type a value.
Result
n = 85
Factors: 5 × 17
DigitSum(85) = 13
Factor digits = 5 + 1 + 7 = 13
85 is a Smith number
Build digit_sum and is_smith, then list Smith numbers in a small range.
Example 1 — is_smith Check
Factorize with multiplicity, reject primes, then compare digit sums.
python
def digit_sum(x: int) -> int:
s = 0
while x > 0:
s += x % 10
x //= 10
return s
def is_smith(n: int) -> bool:
if n <= 1:
return False
original = n
factor_digit_sum = 0
factor_count = 0
while n % 2 == 0:
factor_digit_sum += digit_sum(2)
factor_count += 1
n //= 2
f = 3
while f * f <= n:
while n % f == 0:
factor_digit_sum += digit_sum(f)
factor_count += 1
n //= f
f += 2
if n > 1:
factor_digit_sum += digit_sum(n)
factor_count += 1
if factor_count == 1:
return False # prime
return digit_sum(original) == factor_digit_sum
number = 85
print(f"{number} is a Smith number" if is_smith(number) else f"{number} is not a Smith number")
Output
85 is a Smith number
How It Works
digit_sum peels off each last digit with % 10.
Even factors are peeled with the while n % 2 == 0 loop.
Odd trial factors continue until f * f > n.
A leftover n > 1 is itself a prime factor.
factor_count == 1 means the original value was prime → reject.
Otherwise compare digit sums; for 85 both sides are 13.
Example 2 — Smith Numbers in a Range
Reuse is_smith to print every Smith number from 1 to 100.
python
def digit_sum(x: int) -> int:
s = 0
while x > 0:
s += x % 10
x //= 10
return s
def is_smith(n: int) -> bool:
if n <= 1:
return False
original = n
factor_digit_sum = 0
factor_count = 0
while n % 2 == 0:
factor_digit_sum += digit_sum(2)
factor_count += 1
n //= 2
f = 3
while f * f <= n:
while n % f == 0:
factor_digit_sum += digit_sum(f)
factor_count += 1
n //= f
f += 2
if n > 1:
factor_digit_sum += digit_sum(n)
factor_count += 1
if factor_count == 1:
return False
return digit_sum(original) == factor_digit_sum
start, end = 1, 100
print(f"Smith numbers from {start} to {end}:")
for i in range(start, end + 1):
if is_smith(i):
print(i, end=" ")
print()
Output
Smith numbers from 1 to 100:
4 22 27 58 85 94
How It Works
Same helpers as Example 1 keep the rule in one place.
The outer loop visits every integer from start to end.
Only values that pass is_smith are printed.
Primes and unmatched composites are skipped automatically.
Up to 100 the classic list is 4 22 27 58 85 94.
Edge Cases & Pitfalls
Check these before calling the solution done.
Primes
Always reject
If factor_count == 1, the number is prime — not Smith.
Repeats
Count multiplicity
For 27, add digit sum of 3 three times.
Multi-digit
Factor digits too
For 17 use 1 + 7, not the bare value 17.
1
Not composite
Return False for n ≤ 1 before factoring.
Analysis
Time and Space Complexity
Program
Time
Extra space
is_smith (trial factors)
O(√n)
O(1)
Smith in range 1..N
O(N√N)
O(1)
Digit summing is cheap next to factorization. For interview sizes, trial division is enough.
Remember
Key Takeaways
Definition: composite + matching digit sums of number and prime factors.
Multiplicity: repeated factors count every time.
Primes: never Smith — exclude with a factor count of 1.
Test set: 85 → yes; 27 → yes; 15 → no; 7 → no.
One line: if n is composite and its digit sum matches the digit sum of its prime factors, n is Smith.
Frequently Asked Questions
A Smith number is a composite integer whose digit sum equals the digit sum of all its prime factors, counting repeats. Examples: 4, 22, 27, 58, 85, 94.
By definition primes are excluded. Otherwise every prime would pass, because its only prime factor is itself.
Yes. For 27 = 3 × 3 × 3, the factor digit sum is 3 + 3 + 3 = 9, matching 2 + 7.
Yes. 4 = 2 × 2. Digit sum is 4 and factor digit sum is 2 + 2 = 4.
Trial factorization up to √n is O(√n). Listing Smith numbers from 1 to N by checking each value is about O(N√N).
