Skip to content

Super Prime Cut Numbers

Level: L3-L5 Topics: Number Theory, Recursion, Primality Testing, Dynamic Programming

Problem Statement

A number is called a Super Prime Cut (SPC) number if:

  • It is less than 10 and is prime (i.e., it is 2, 3, 5, or 7), OR
  • It is 10 or greater, AND it is prime, AND the number formed by removing its last digit is also an SPC number.

In other words, an SPC number is prime, and when you repeatedly chop off the last digit, every intermediate number is also prime — all the way down to a single-digit prime.

Background & Constraints

  • Standard primality: a number greater than 1 with no divisors other than 1 and itself.
  • "Removing the last digit" means integer division by 10 (e.g., 239 becomes 23).
  • Single-digit primes are: 2, 3, 5, 7.
  • The number 1 is NOT prime, so any chain that reaches 1 fails.

Examples

23 is SPC:

  • 23 is prime.
  • Remove last digit: 2. Is 2 SPC? Yes (single-digit prime).

29 is SPC:

  • 29 is prime.
  • Remove last digit: 2. Is 2 SPC? Yes.

113 is NOT SPC:

  • 113 is prime.
  • Remove last digit: 11. Is 11 prime? Yes.
  • Remove last digit: 1. Is 1 prime? No.
  • Chain breaks at 1, so 113 is not SPC.

233 is SPC:

  • 233 is prime. Remove last digit: 23. Is 23 prime? Yes. Remove last digit: 2. Is 2 prime? Yes.

Hints & Common Pitfalls

  • This is naturally recursive: is_spc(n) = is_prime(n) AND (n < 10 OR is_spc(n // 10)).
  • Use memoization or dynamic programming to avoid redundant primality checks.
  • To enumerate all SPC numbers up to a limit, you can build them bottom-up: start with single-digit primes, then try appending each digit 0-9 to form a larger number, keeping only those that are prime.
  • The bottom-up approach is essentially a BFS/DFS tree rooted at {2, 3, 5, 7}.
  • Common pitfall: forgetting that 1 is not prime, which disqualifies chains passing through 1 (like 11 -> 1).

Follow-Up Questions

  1. Enumerate all SPC numbers up to a limit: Given an upper bound L, find all SPC numbers up to L. What is the most efficient approach? (Hint: build the tree bottom-up rather than checking each number individually.)
  2. Super Duper variant: A number is "Super Duper Prime Cut" if it is prime and BOTH the number with the last digit removed AND the number with the first digit removed are also Super Duper Prime Cut. How does this change the structure? Is the set of Super Duper numbers finite or infinite?
  3. Numbers larger than 2^64: How would you handle very large numbers that do not fit in standard integer types? What primality testing algorithms work for arbitrary-precision integers (e.g., Miller-Rabin)?