Must Be Composite
Gate
Primes are excluded by definition.
Check Smith Number in Python
Overview
What You’ll Learn
A Smith number is a composite integer whose digit sum equals the digit sum of its prime factors with multiplicity. Examples: 4, 22, 27, 58, 85, 94. Non-examples: primes (7), and composites like 15 where the sums do not match. This tutorial covers helpers for digit sum and factorization, a live check, worked Python examples, edge cases, and complexity.
S(n)
Digit sum
Sum the digits of n itself.
F(n)
Factor digits
Digit-sum every prime factor.
Multiplicity
27 = 3³
Count each repeated factor.
Live Preview
Try 85 / 7
See S(n) and F(n) side by side.
Smallest Is 4
2*2
4 = 2+2 matches digit sum 4.
Introduction
A Smith number is a composite integer where the digit sum of the number equals the digit sum of all its prime factors, counting repeats. So for 85 = 5 * 17, both sides equal 13. For 27 = 3 * 3 * 3, factor digits are counted three times: 3+3+3 = 9, matching 2+7.
Interviews expect a composite gate plus trial factorization. Without excluding primes, every prime would “pass” because its only prime factor is itself.
Why it matters?
It combines primality, factorization, and digit arithmetic — a strong interview warm-up after composite numbers.
Key Highlights
Composite Gate
Reject primes first.
S(n) = F(n)
Matching digit sums.
Count Repeats
27 needs three 3’s.
1..100 List
4 22 27 58 85 94
In short: if n is composite and digit_sum(n) == factor_digit_sum(n), then n is Smith.
Foundation
📝 Problem & Approach
Given an integer n, decide whether it is a Smith number: composite with matching digit sums.
python
# 85 -> 5*17, S=13, F=13 Smith
# 27 -> 3*3*3, S=9, F=9 Smith (multiplicity)
# 7 -> prime not Smith
# 15 -> 3*5, S=6, F=8 not SmithInputs & Outputs
| Item | Type | Description |
|---|---|---|
n | int | Value to test (n >= 1). |
| Return | bool | True when composite and S(n) = F(n). |
| S(n) / F(n) | int | Digit sum of n / of prime factors. |
Minimal workflow
Pseudocode
function isSmith(n):
if n <= 1 or isPrime(n):
return false
return digitSum(n) == factorDigitSum(n)Method comparison
| Method | Idea | Notes |
|---|---|---|
| Trial factorization | Pull factors, sum their digits | Interview default |
| Range scan | Call is_smith on each i | Lists 4 22 27 58 85 94 |
| Trace with S/F | Print both sums for candidates | Great for debugging |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Digit sum | total += n % 10; n //= 10 |
| Prime gate | if n <= 1 or is_prime(n): return False |
| Pull factor | while x % i == 0: total += digit_sum(i) |
| Leftover prime | if x > 1: total += digit_sum(x) |
| Verdict | digit_sum(n) == factor_digit_sum(n) |
| Range list | if is_smith(i): print(i) |
Compare
📋 Check vs Range vs Trace
Same definition — different packaging.
Single check
is_smith(85)Full helpers + one verdict
Range
1..100Classic interview listing
Trace
S / F printShows why yes or no
vs prime
always FalseComposite gate is mandatory
Context
When This Problem Shows Up
Reach for a Smith check when digit sums meet prime factorization.
Interview follow-ups
After composite / prime-factor drills.
Range listing
Find Smith values in a band.
Multiplicity practice
27 forces repeated factors.
Digit-sum toolkit
Shares helpers with Armstrong / condense.
Not for primes
Definition forbids them.
Key benefit: one memorable rule — composite + matching digit sums — with a clear factorization loop.
Interactive
🔮 Live Preview
Computes S(n) and F(n), rejects primes, and reports the Smith verdict.
Hands-On
Examples Gallery
Three complete Python programs — check 85, list Smith numbers from 1 to 100, and print S/F traces for several candidates. Click View Output to reveal sample console results.
📚 Getting Started
Digit sum, primality, factor digit sum, then the composite gate.
Example 1 — Check a Single Number
Full helpers. Trial division is enough for interview-size inputs; the composite gate avoids false positives on primes.
python
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.")How It Works
85 = 5 * 17. Digit sum is 8+5 = 13. Factor digit sum is 5 + (1+7) = 13, and 85 is composite, so it is Smith.
⚡ Hunting in a Range
Reuse the helpers to list nearby Smith values.
Example 2 — Smith Numbers from 1 to 100
Reuse the helpers from Example 1 and print matching values.
python
# Reuse digit_sum, is_prime, factor_digit_sum, is_smith from Example 1
print("Smith Numbers in the Range 1 to 100:")
for i in range(1, 101):
if is_smith(i):
print(i, end=" ")
print()How It Works
Within 1..100 the hits are 4, 22, 27, 58, 85, and 94. Memorizing this short list is a useful interview sanity check.
Example 3 — Trace S(n) and F(n) for Candidates
Print both sums so you can see why a value is Smith or not — including multiplicity for 27.
python
# Reuse digit_sum, is_prime, factor_digit_sum, is_smith from Example 1
candidates = [4, 7, 15, 27, 85]
for n in candidates:
S = digit_sum(n)
F = factor_digit_sum(n)
label = "Smith" if is_smith(n) else "not Smith"
print(f"{n}: S={S}, F={F} -> {label}")How It Works
7 matches S and F but fails the composite gate. 15 is composite but 6 ≠ 8. 27 works only because F counts 3 three times.
🧠 How the Algorithm Decides
1
Reject n <= 1 or primes
Smith requires a composite n.
Gate
2
Compute S(n)
Sum the digits of n.
Digit sum
3
Compute F(n)
Factor n; add digit sums with multiplicity.
Factors
=
Compare S and F
Equal means Smith; otherwise not.
Trace
🔎 Worked Walkthrough — 85 vs 27 vs 7
Compare a two-factor Smith number, a repeated-factor Smith number, and a prime rejection.
| n | Factors | S(n) | F(n) | Verdict |
|---|---|---|---|---|
85 | 5 * 17 | 13 | 5+1+7=13 | Smith |
27 | 3 * 3 * 3 | 9 | 3+3+3=9 | Smith |
7 | prime | 7 | 7 | not Smith (gate) |
15 | 3 * 5 | 6 | 8 | not Smith |
Multiplicity and the composite gate are the two details interviewers listen for.
Use Cases
Where Smith checks show up beyond the interview prompt.
1. Interview Classics
Composite + digit-sum factors.
Example: is_smith(85).
2. Range Listing
Find Smith values in a band.
Example: 4 22 27 58 85 94.
3. Factor Practice
Trial division with repeats.
Example: 27 = 3³.
4. Digit Toolkit
Shares helpers with condense / Armstrong.
Example: digit_sum.
5. Debugging Traces
Print S and F for odd failures.
Example: Example 3.
6. Next: Condense
Continue the interview chain.
Example: related CTA.
Pro Tip: open with “composite and S(n)=F(n) with multiplicity” before coding.
Advantages
Why this factorization-plus-digit-sum approach works well.
1. Clear Definition
Composite gate + two digit sums.
2. Reusable Helpers
digit_sum and is_prime appear elsewhere.
3. Multiplicity Built In
The inner while counts repeats naturally.
4. Easy to Trace
Print S and F to debug any n.
Pro Tip: dry-run 27 out loud — if you forget multiplicity, the answer collapses.
Usage Tips
Small habits that keep Smith solutions interview-ready.
1. Gate Primes First
Return False before comparing sums.
2. Count Every Factor
Use while x % i == 0, not if.
3. Digit-Sum Large Factors
17 contributes 1+7, not 17.
4. Handle Leftover x
If x > 1 after the loop, add digit_sum(x).
5. Sanity-Check 1..100
Expect 4 22 27 58 85 94.
Pro Tip: test 4, 7, 15, 27, and 85 — if those five behave, your logic is solid.
Common Pitfalls
Mistakes that commonly break Smith-number programs.
1. Accepting Primes
S and F match for every prime.
→ Reject primes before comparing.
2. Ignoring Multiplicity
Counting 27 as a single 3.
→ Loop while divisible.
3. Adding the Factor Value
Using 17 instead of 1+7.
→ Always digit_sum each factor.
4. Dropping the Leftover
Forgetting x > 1 after trial division.
→ Add digit_sum(x) when needed.
5. Calling 1 Smith
1 is not composite.
→ Return False for n <= 1.
Edge Cases
Handle these before claiming the check is complete.
n = 1
Not Smith
Not composite.
Prime n
Always reject
Definition requires composite.
Multiplicity
Must count repeats
For 27, count 3 three times.
n = 4
Smallest Smith
2 * 2, both sums = 4.
n = 15
Composite miss
S = 6, F = 8.
Large factors
Digit-sum them
17 → 1+7, not 17.
Theory
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Named after Harold Smith. Wilansky noticed 4937775 has the property.
- Smallest is 4. The sequence in 1..100 is 4, 22, 27, 58, 85, 94.
- Primes never qualify. The composite requirement is part of the definition.
- Trial division is enough. Fine for interview-size inputs.
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Prove 85
- Factors 5 and 17
- Both sums = 13
2. Trace 27
- Count 3 three times
- Confirm F = 9
3. Reject 7 and 15
- Prime gate vs sum miss
- Explain both failures
4. List 1..100
- Reproduce Example 2
- Expect 4 22 27 58 85 94
Important
Notes
- Definition: Smith means composite + matching digit sums (with multiplicity).
- Gate: reject n <= 1 and primes before comparing S and F.
- Range check: from 1 to 100 you should get
4 22 27 58 85 94. - Efficiency: trial division is fine for interview-size inputs. The composite gate is mandatory to avoid false positives on primes.
Quick Takeaway: n is Smith when it is composite and digit_sum(n) == factor_digit_sum(n).
Analysis
⏱️ Time and Space Complexity
| Step | Time | Extra 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) |
Dominant cost is trial factorization; digit summing is cheap by comparison.
🎉 Conclusion
A Smith number is composite with matching digit sums between the number and its prime factors (counting repeats). Gate primes, factor carefully, and compare S(n) with F(n).
Practice the three examples above, then continue to condensing a number.
Composite + S(n)=F(n) with multiplicity.
Pro Tips
💡 Best Practices
✅ Do
- Require composite first
- Count repeated factors
- Digit-sum every factor
- Handle leftover x > 1
- Sanity-check 1..100 list
❌ Don’t
- Accept primes as Smith
- Count 27 as one 3
- Add 17 instead of 1+7
- Skip the leftover prime
- Treat 1 as composite
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about Smith numbers
Classify composites whose digit sums match their factors.
5
Core concepts 01
Gate
must be composite
Definition 02
Match
S(n) = F(n)
Rule 03
Repeats
count multiplicity
Factors 04
List
4..94 in 1..100
Check 05
Cost
O(√n)
Analysis❓ Frequently Asked Questions
A Smith number is a composite number where the digit sum of the number equals the digit sum of all prime factors (counting repeats).
By definition primes are excluded. Otherwise every prime would trivially pass.
Yes. 4 = 2 * 2. Digit sum(4) = 4 and factor digit sum = 2 + 2 = 4.
Yes. 85 = 5 * 17. 8+5 = 13 and 5 + (1+7) = 13.
No. 7 is prime, and primes are excluded.
Yes. For 27 = 3 * 3 * 3, digit sum of factor 3 is counted three times.
No. 1 is not composite.
No. 15 = 3*5, digit sum 1+5=6 but factor digit sum 3+5=8.
State composite + S(n)=F(n), then show multiplicity with 27.
Did you Know? 🔊
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.
Continue to Condense a Number
Learn how to repeatedly sum digits until a single digit remains.
About the author
9 people found this page helpful