Skip to content
Tutorials Center
My learning

Topics

Lesson 178 of 225 ยท Math and Bit Manipulation

Digit and Number Puzzles

Solve classic number exercises in Python: Armstrong and perfect numbers, digital roots, divisibility rules from digits, and finding repeating decimals of fractions.

Many coding interviews start with a small number puzzle. They look like trivia, yet each one hides a reusable technique: peeling digits with % and //, summing divisors up to the square root, noticing a pattern that replaces a loop with one modulo, and detecting a repeated remainder to find where a decimal expansion starts to cycle.

This lesson collects five such families, with brute force first and a cleverer version where one exists. Before you start, be comfortable with divisibility and gcd from Number Theory.

Taking numbers apart digit by digit

n % 10 is the last digit and n // 10 drops it. Looping until n becomes 0 visits every digit from right to left. divmod(n, 10) gives both at once.

Python Digit toolkit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Armstrong (narcissistic) numbers

An Armstrong number equals the sum of its digits each raised to the power of the digit count. For example, 153 = 1^3 + 5^3 + 3^3 and 9474 = 9^4 + 4^4 + 7^4 + 4^4. The count of digits is the exponent, which is the part beginners forget.

Python Armstrong numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are only finitely many Armstrong numbers (the largest has 39 digits), because for long numbers the digit-power sum cannot reach the value.

Perfect, abundant and deficient numbers

A number is perfect if it equals the sum of its proper divisors (those below itself): 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14. If the sum is larger it is abundant (12), if smaller deficient (8).

Do not test every number up to n. Divisors come in pairs (d, n/d), so scan only up to sqrt(n) and add both members of each pair. Watch out for the square root, which must be added only once.

Python Sum of divisors with the square-root trick

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every even perfect number has the Euclid-Euler form shown above, tying perfect numbers to the Mersenne primes of Fermat, Mersenne and Pollard's Rho. Nobody knows whether an odd perfect number exists.

Digital root without a loop

The digital root of n is what you get by adding digits repeatedly until one digit remains: 9875 -> 29 -> 11 -> 2. Because 10 % 9 == 1, a number is congruent to its digit sum modulo 9, so the answer is simply

TEXT
digital_root(n) = 0 if n == 0 else 1 + (n - 1) % 9
Python Digital root: loop versus formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Divisibility rules from the digits

Because 10 leaves different remainders modulo small numbers, you can test divisibility using only digits:

By Rule
2, 5, 10 the last digit (even, 0 or 5, 0)
4, 8 the last two or three digits
3, 9 the digit sum
11 the alternating digit sum
7, 13 alternate groups of three digits (1001 = 7 x 11 x 13)

These matter when the number arrives as a string too long for an integer type, so you process it one digit at a time keeping only a remainder.

Python Divisibility of a huge number given as text

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Horner's rule (r = r * 10 + digit, keep the remainder) is the general tool: it works for any modulus and a number of any length.

Recurring decimals

Dividing 1 by 7 gives 0.142857142857..., with a repeating block. Long division produces a remainder at each step; the digits repeat exactly when a remainder repeats. Store each remainder with the position where it first appeared. When one comes back, the digits since that position form the repeating part.

Python Fraction to decimal with a repeating block

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are at most denom different remainders, so the loop ends in at most denom steps. A fraction terminates exactly when its reduced denominator has no prime factors other than 2 and 5.

Common mistakes

  • Wrong exponent for Armstrong numbers. The power is the number of digits, not always 3.
  • Counting the square root twice when summing divisor pairs.
  • Forgetting that 1 has no proper divisors (its proper divisor sum is 0, not 1).
  • Losing leading zeros when reversing a number as an integer. Use strings if zeros matter.
  • Using floats for decimals. 1 / 3 is already rounded; do exact long division on integers.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which is the Armstrong number?

    1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153.
  2. 2. Why does a divisor search for perfect numbers only need to go up to sqrt(n)?

    Divisors come in pairs (d, n/d). One member of every pair is at most the square root.
  3. 3. What is the digital root of 9875?

    9 + 8 + 7 + 5 = 29, then 2 + 9 = 11, then 1 + 1 = 2. The formula 1 + (9875 - 1) % 9 also gives 2.
  4. 4. How do you know a decimal expansion has started to repeat?

    The next digit depends only on the current remainder, so a repeated remainder means the digits cycle from that point.

Summary

  • divmod(n, 10) peels digits; Horner's rule r = (r * 10 + d) % m handles numbers too long for an integer.
  • Armstrong numbers use the digit count as the exponent; perfect numbers equal the sum of their proper divisors, found with a sqrt(n) scan.
  • The digital root is 1 + (n - 1) % 9 for positive n, because 10 is 1 modulo 9.
  • Divisibility rules (3, 9, 11, 7) let you test huge numbers digit by digit.
  • Long division finds repeating decimals by remembering where each remainder first appeared.

Next: Number Theory