Check Smith Number in Python
What you'll learn
- The definition of a Smith number (composite + matching digit sums).
- How to factor with trial division and count prime factors with multiplicity.
- How to check one number and list all Smith numbers from 1 to 100.
Overview
A Smith number is a composite integer where digit sum of the number equals digit sum of its prime factors (counting repeats).
Prerequisites
Loops, modulo, integer division, and basic prime factorization.
What is a Smith number?
Let S(n) be digit sum of n and F(n) be digit sum of all prime factors of n with multiplicity. If n is composite and S(n) = F(n), then n is Smith.
Example 22: S(22)=2+2=4; factorization 22 = 2*11, so F(22)=2+(1+1)=4.
Why multiplicity matters
For 27 = 3*3*3, you must count each 3. So factor digit sum is 3+3+3=9, which matches 2+7=9.
Quick examples
85 is Smith. 7 is not (prime).
Live preview
Algorithm
Reject non-composite
If n <= 1 or n is prime, not Smith.
Compute S(n)
Sum digits of n.
Compute F(n)
Factor n and add digit sums of factors with multiplicity.
Compare
Smith iff S(n) equals F(n).
📜 Pseudocode
function isSmith(n):
if n <= 1 or isPrime(n): return false
return digitSum(n) == factorDigitSum(n)Check a single number
def digit_sum(n: int) -> int:
total = 0
while n > 0:
total += n % 10
n //= 10
return total
def is_prime(n: int) -> bool:
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
def factor_digit_sum(n: int) -> int:
total = 0
x = n
i = 2
while i * i <= x:
while x % i == 0:
total += digit_sum(i)
x //= i
i += 1
if x > 1:
total += digit_sum(x)
return total
def is_smith(n: int) -> bool:
if n <= 1 or is_prime(n):
return False
return digit_sum(n) == factor_digit_sum(n)
number = 85
print(f"{number} is a Smith Number." if is_smith(number) else f"{number} is not a Smith Number.")Smith numbers from 1 to 100
# Reuse helpers above
print("Smith Numbers in the Range 1 to 100:")
for i in range(1, 101):
if is_smith(i):
print(i, end=" ")
print()Smith Numbers in the Range 1 to 100: 4 22 27 58 85 94
Efficiency notes
Trial division is fine for interview-size inputs.
Composite gate is mandatory to avoid false positives on primes.
❓ FAQ
🔄 Input / output examples
| n | Smith? | Note |
|---|---|---|
| 85 | Yes | 5 * 17, both sums = 13 |
| 7 | No | Prime |
| 58 | Yes | 2 * 29 |
| 15 | No | 6 vs 8 |
Edge cases and pitfalls
Not Smith
Not composite.
Always reject
Definition requires composite.
Must count repeats
For 27, count 3 three times.
⏱️ Time and space complexity
| Step | Time | Space |
|---|---|---|
| digit_sum | O(log n) | O(1) |
| factor_digit_sum | O(sqrt(n)) | O(1) |
| range 1..U | about O(U*sqrt(U)) | O(1) |
Summary
- Smith means composite + matching digit sums.
- Count repeated prime factors.
- From 1 to 100:
4 22 27 58 85 94.
Smith numbers are named after Albert Wilansky's brother-in-law Harold Smith, who noticed 4937775 has this property. The smallest is 4. Primes are never Smith numbers by definition.
About the author
9 people found this page helpful