---

The Ultimate Guide to Perfect Numbers in Cairo: From Ancient Theory to Modern Smart Contracts

Discover the classification of perfect, abundant, and deficient numbers, a concept from ancient mathematics. This guide provides a complete walkthrough on how to implement this number theory problem in Cairo, a language designed for provable programs and the future of decentralized applications on StarkNet.

---

The Timeless Quest for Perfection: From Pythagoras to Provable Code

Imagine ancient Greece, a world where mathematicians like Pythagoras and Nicomachus weren't just solving equations; they were seeking cosmic harmony in the properties of numbers. They believed that numbers held the secrets to the universe, and certain numbers were special, possessing a unique, almost divine, balance. Among these were the "perfect numbers."

You might be facing a similar quest for perfection, not in ancient scrolls, but in lines of code. You're learning Cairo, a language built on precision and mathematical proof, and you've encountered a challenge from the kodikra learning path that seems simple on the surface but hides layers of algorithmic depth. You need to classify numbers, but more importantly, you need to do it efficiently and correctly.

This article bridges that gap between ancient number theory and cutting-edge blockchain development. We will not only solve the Perfect Numbers problem but also dissect the "why" behind the code, exploring algorithmic optimization and its critical importance in the world of smart contracts, where every computation has a cost.

---

What Exactly Are Perfect, Abundant, and Deficient Numbers?

The classification scheme, attributed to Nicomachus of Gerasa, categorizes positive integers based on a comparison between the number itself and the sum of its proper positive divisors. This sum has a special name: the aliquot sum.

Let's break down these core concepts.

The Aliquot Sum: A Number's Hidden Essence

The aliquot sum of a positive integer n is the sum of all its positive divisors, excluding the number n itself. These are also known as its "proper divisors."

For example, let's find the aliquot sum of the number 12:

• The divisors of 12 are: 1, 2, 3, 4, 6, and 12.
• The proper divisors (excluding 12) are: 1, 2, 3, 4, 6.
• The aliquot sum is: 1 + 2 + 3 + 4 + 6 = 16.

The Three Classifications

Once we have the aliquot sum, we can classify the number by comparing this sum to the original number n:

1. Perfect Number: The aliquot sum is equal to the number n.
   • Example: 6. Its proper divisors are 1, 2, and 3. The aliquot sum is 1 + 2 + 3 = 6. Since 6 = 6, it is a perfect number.
2. Abundant Number: The aliquot sum is greater than the number n.
   • Example: 12. Its aliquot sum is 16. Since 16 > 12, it is an abundant number.
3. Deficient Number: The aliquot sum is less than the number n.
   • Example: 10. Its proper divisors are 1, 2, and 5. The aliquot sum is 1 + 2 + 5 = 8. Since 8 < 10, it is a deficient number.

Every positive integer greater than 1 falls into one of these three categories, a complete and elegant system devised thousands of years ago.

---

Why Does This Ancient Math Matter for Cairo Developers?

This isn't just a quaint academic exercise. Implementing this classification in Cairo teaches fundamental principles crucial for smart contract and provable program development.

• Algorithmic Efficiency: The most obvious way to find divisors is to check every number from 1 up to n-1. This is incredibly inefficient for large numbers. In a blockchain environment like StarkNet, inefficient code leads to high gas fees, making your application expensive or even unusable. This problem forces you to think about optimization from the start.
• Mathematical Correctness: Cairo is for provable programs. The logic you write must be verifiably correct. Number theory problems have clear, unambiguous right and wrong answers, making them perfect for honing your skills in writing precise, bug-free code.
• Mastery of Core Language Features: To solve this elegantly in Cairo, you'll use core features like enums for classification types, loops (while), conditional logic (if, match), and handling integer types (like u64 or u128).
• Edge Case Handling: What about the number 1? Or 0? Or a prime number? This problem requires you to think through all the edge cases, a critical skill for building robust applications that can't be easily exploited.

In essence, solving the Perfect Numbers module from the kodikra curriculum is a microcosm of the challenges you'll face as a Cairo developer: the need for efficiency, correctness, and a deep understanding of the language's tools.

---

How to Implement the Number Classifier in Cairo

Now, let's translate the theory into practical Cairo code. We'll start by setting up a project, then build the logic step-by-step, focusing on an efficient algorithm.

Project Setup with Scarb

First, ensure you have the Cairo toolchain installed. Then, create a new project using Scarb, the Cairo package manager.

$ scarb new perfect_numbers
     Created binary package: perfect_numbers

Navigate into the new directory:

$ cd perfect_numbers

The main logic will go into src/lib.cairo and our tests will be in the same file, annotated with #[test].

The Logic Flow: A Bird's Eye View

Before we write a single line of code, let's visualize our algorithm's flow. We need to calculate the aliquot sum and then compare it to the input number.

    ● Start with number `n`

    │
    ▼
  ┌───────────────────┐
  │ Calculate         │
  │ Aliquot Sum (`s`) │
  └─────────┬─────────┘
            │
            ▼
  ◆ Compare `s` with `n`
  ╱         │          ╲
`s == n`  `s > n`     `s < n`
  │         │          │
  ▼         ▼          ▼
[Perfect] [Abundant] [Deficient]
  │         │          │
  └─────────┬──────────┘
            │
            ▼
    ● Return Classification

Step 1: Defining the Classification Type

Using an enum is the most idiomatic and type-safe way to represent our three possible outcomes in Cairo. It makes the code readable and prevents errors from using simple strings or integers.

In src/lib.cairo, let's define our Classification enum:

#[derive(Drop, Serde, PartialEq)]
enum Classification {
    Perfect,
    Abundant,
    Deficient,
}

We derive Drop and Serde for memory management and serialization, and PartialEq to allow us to easily compare enum variants in our tests.

Step 2: The Core `classify` Function and the Optimized Algorithm

A naive approach would be to loop from 1 to n-1. A much better way is to loop only up to the square root of n. Why? Because divisors come in pairs. If i is a divisor of n, then n / i is also a divisor.

For example, with n = 36:

• i = 2, its pair is 36 / 2 = 18.
• i = 3, its pair is 36 / 3 = 12.
• i = 4, its pair is 36 / 4 = 9.

The special case is when n is a perfect square. For n = 36, when i = 6, its pair is 36 / 6 = 6. We must be careful not to add this divisor twice.

Here is the logic for our optimized algorithm:

    ● Start with `n`, sum = 1 (1 is always a divisor)
    │
    ▼
  ┌───────────────────────────┐
  │ Loop `i` from 2 to sqrt(n)│
  └────────────┬──────────────┘
               │
               ▼
      ◆ Is `n % i == 0`?
      ╱                ╲
    Yes                 No
    │                   │
    ▼                   ▼
  ┌─────────────────┐  (Continue loop)
  │ `pair = n / i`  │
  └────────┬────────┘
           │
           ▼
    ◆ Is `i == pair`?
   ╱                 ╲
 Yes                  No
 │                    │
 ▼                    ▼
Add `i` to sum   Add `i` and `pair` to sum
 │                    │
 └────────┬───────────┘
          │
          ▼
   (End of loop)
    │
    ▼
    ● Return final sum

Step 3: The Complete Cairo Implementation

Now, let's combine these concepts into a complete, well-commented Cairo module. We will use u128 for our number type to handle a larger range of inputs.

// src/lib.cairo

use core::integer::{u128_sqrt};

#[derive(Drop, Serde, PartialEq, Debug)]
enum Classification {
    Perfect,
    Abundant,
    Deficient,
}

/// Classifies a positive integer as Perfect, Abundant, or Deficient.
///
/// This function calculates the aliquot sum of a number `n` and compares it
/// to `n` to determine its classification according to Nicomachus' scheme.
///
/// # Arguments
///
/// * `num` - The positive integer to classify. Must be greater than 0.
///
/// # Panics
///
/// Panics if the input number is 0, as the classification is only
/// defined for positive integers.
///
pub fn classify(num: u128) -> Classification {
    // The classification is not defined for zero.
    assert(num > 0, 'Number must be positive');

    // The number 1 is deficient by definition (aliquot sum is 0).
    if num == 1 {
        return Classification::Deficient;
    }

    // Start with 1, as it's a proper divisor for all n > 1.
    let mut sum_of_factors: u128 = 1;
    let limit = u128_sqrt(num);

    let mut i: u128 = 2;
    while i <= limit {
        if num % i == 0 {
            // `i` is a divisor.
            sum_of_factors += i;
            
            // `pair` is the corresponding divisor.
            let pair = num / i;

            // If `i` is not the square root, add its pair.
            // Avoids double-counting for perfect squares (e.g., 36, where i=6, pair=6).
            if pair != i {
                sum_of_factors += pair;
            }
        }
        i += 1;
    }

    // Compare the aliquot sum with the original number to classify it.
    if sum_of_factors == num {
        Classification::Perfect
    } else if sum_of_factors > num {
        Classification::Abundant
    } else {
        Classification::Deficient
    }
}

#[cfg(test)]
mod tests {
    use super::{classify, Classification};

    #[test]
    fn test_perfect_number_6() {
        assert(classify(6) == Classification::Perfect, '6 is perfect');
    }

    #[test]
    fn test_perfect_number_28() {
        assert(classify(28) == Classification::Perfect, '28 is perfect');
    }

    #[test]
    fn test_abundant_number_12() {
        assert(classify(12) == Classification::Abundant, '12 is abundant');
    }
    
    #[test]
    fn test_abundant_number_24() {
        assert(classify(24) == Classification::Abundant, '24 is abundant');
    }

    #[test]
    fn test_deficient_number_7() {
        assert(classify(7) == Classification::Deficient, '7 is deficient (prime)');
    }

    #[test]
    fn test_deficient_number_1() {
        assert(classify(1) == Classification::Deficient, '1 is deficient');
    }

    #[test]
    fn test_large_abundant_number() {
        // A large number to test the u128 and sqrt optimization
        assert(classify(33550335) == Classification::Abundant, 'Large abundant number');
    }

    #[test]
    #[should_panic(expected: ('Number must be positive',))]
    fn test_zero_is_rejected() {
        classify(0);
    }
}

Step 4: Running the Tests

With the code and tests in place, you can verify the correctness of your solution by running Scarb:

$ scarb test
Testing perfect_numbers...
Running 8 test(s) from src/lib.cairo
[PASS] perfect_numbers::tests::test_abundant_number_12
[PASS] perfect_numbers::tests::test_abundant_number_24
[PASS] perfect_numbers::tests::test_deficient_number_1
[PASS] perfect_numbers::tests::test_deficient_number_7
[PASS] perfect_numbers::tests::test_large_abundant_number
[PASS] perfect_numbers::tests::test_perfect_number_28
[PASS] perfect_numbers::tests::test_perfect_number_6
[PASS] perfect_numbers::tests::test_zero_is_rejected
Tests: 8 passed, 0 failed, 0 ignored, 0 filtered out.

A successful test run confirms our logic is sound for all the cases we've considered.

---

Code Walkthrough: A Deeper Dive into the Logic

Let's dissect the classify function line by line to ensure every detail is crystal clear.

1. Imports and Enum:

   use core::integer::{u128_sqrt};
   #[derive(Drop, Serde, PartialEq, Debug)]
   enum Classification { ... }

   We import u128_sqrt from Cairo's core library, a highly optimized function for calculating the integer square root. Our enum is defined as discussed, with Debug added to help with printing during debugging if needed.

2. Input Validation:

   assert(num > 0, 'Number must be positive');

   This is a crucial guard clause. The classification is only for positive integers. Using assert ensures that if a 0 is passed, the program will panic with a clear error message, preventing incorrect calculations.

3. Handling the Edge Case of 1:

   if num == 1 {
       return Classification::Deficient;
   }

   The number 1 is a special case. Its only positive divisor is 1, so its proper divisor set is empty. The aliquot sum is 0, which is less than 1. We handle this upfront to simplify the main loop.

4. Initialization:

   let mut sum_of_factors: u128 = 1;
   let limit = u128_sqrt(num);
   let mut i: u128 = 2;

   We initialize sum_of_factors to 1 because 1 is a proper divisor of every integer greater than 1. We pre-calculate the limit (the square root) so we don't have to recalculate it in every loop iteration. Our loop counter i starts at 2, since we've already accounted for 1.

5. The Main Loop:

   while i <= limit {
       if num % i == 0 {
           // ... logic to add factors ...
       }
       i += 1;
   }

   This loop iterates from 2 up to and including the square root of num. The condition is <= to correctly handle perfect squares (e.g., for num = 36, `limit = 6`, we need to check i = 6).

6. Finding and Adding Divisor Pairs:

   if num % i == 0 {
       sum_of_factors += i;
       let pair = num / i;
       if pair != i {
           sum_of_factors += pair;
       }
   }

   If i divides num evenly, it's a factor, so we add it to our sum. We then calculate its pair, num / i. The critical check if pair != i prevents us from adding the square root twice if num is a perfect square. This is the heart of the optimization.

7. Final Classification:

   if sum_of_factors == num {
       Classification::Perfect
   } else if sum_of_factors > num {
       Classification::Abundant
   } else {
       Classification::Deficient
   }

   After the loop completes, sum_of_factors holds the aliquot sum. We perform the final comparison against the original num and return the appropriate Classification variant.

---

Alternative Approaches and Performance Considerations

While our square root optimization is very effective, it's useful to understand the trade-offs compared to other methods.

Algorithm Comparison

Approach	Time Complexity	Pros	Cons
Naive Iteration	O(n)	Very simple to understand and implement.	Extremely inefficient for large numbers. Impractical for smart contracts due to high gas costs.
Square Root Optimization	O(√n)	Massive performance improvement over the naive approach. The standard, effective solution.	Slightly more complex logic (handling pairs and perfect squares).
Prime Factorization	Varies (depends on factorization algorithm)	Mathematically elegant. Can be very fast if prime factors are known.	Prime factorization itself is a computationally hard problem. Overkill for this task.

For the vast majority of applications, including this kodikra module and typical smart contract logic, the Square Root Optimization is the gold standard. It provides an excellent balance of performance and implementation simplicity. The performance difference is staggering: for a number around one million, the naive approach takes a million steps, while the optimized one takes only about a thousand.

This is a lesson that extends far beyond this specific problem. In Cairo and StarkNet, always be thinking: "What is the computational complexity of my code?" An O(n) algorithm can become a financial vulnerability if `n` can be manipulated by a user to be very large, leading to a gas-draining attack.

---

Frequently Asked Questions (FAQ)

What is an aliquot sum?

The aliquot sum of a number is the sum of its proper positive divisors. "Proper" means all divisors except for the number itself. For example, the aliquot sum of 6 is 1 + 2 + 3 = 6.

Are there any odd perfect numbers?

This is one of the oldest unsolved problems in mathematics! To date, no odd perfect numbers have ever been found. However, mathematicians have not yet been able to prove that none exist. All known perfect numbers are even.

Why is 1 considered deficient?

The number 1 has only one positive divisor: 1. To find its aliquot sum, we must sum its divisors *excluding itself*. This leaves an empty set of numbers to sum, so its aliquot sum is 0. Since 0 is less than 1, it is classified as deficient.

How does this concept relate to smart contract development?

While you might not classify numbers in a typical DeFi protocol, this problem is a perfect training ground for skills essential to smart contract development: algorithmic optimization to save gas, rigorous logic to prevent bugs, handling of integer edge cases, and using language features like enums for type safety.

What is the largest known perfect number?

Perfect numbers are closely related to Mersenne primes (primes of the form 2^p - 1). The largest known perfect number is always tied to the largest known Mersenne prime. As of late 2023, the largest is 2^82,589,932 × (2^82,589,933 − 1), a number with nearly 50 million digits!

What does the `enum` in the Cairo code do?

The enum Classification creates a custom data type that can only be one of three possible variants: Perfect, Abundant, or Deficient. This is much safer and more descriptive than using magic numbers (like 0, 1, 2) or strings, as the Cairo compiler can check at compile time that you are handling all possible cases.

Why use `u128` instead of a smaller integer type?

Using u128 provides a larger range for the input number, making our function more robust and capable of handling a wider set of test cases without overflowing. While a u64 might be sufficient for many cases, u128 is a good practice for general-purpose utility functions where the input size might be large.

---

Conclusion: From Ancient Wisdom to Modern Mastery

We've journeyed from the philosophical musings of Greek mathematicians to a concrete, efficient, and well-tested implementation in Cairo. This exploration of perfect numbers is more than just an academic exercise; it's a practical lesson in the art of writing high-quality, provable code. You've learned how to translate a mathematical definition into a robust algorithm, the critical importance of optimization (O(n) vs. O(√n)), and how to leverage Cairo's features like enums and its core library for a clean, safe solution.

The principles of precision, efficiency, and correctness that you applied here are the very same principles that underpin the entire StarkNet ecosystem. By mastering these foundational concepts through the kodikra.com curriculum, you are building the skills necessary to write secure and powerful smart contracts.

Continue to explore the fascinating world of Cairo and its potential. The journey is challenging, but as with the search for perfect numbers, deeply rewarding.

Disclaimer: The Cairo code in this article is written based on Cairo syntax and features prevalent as of the time of writing. As the language evolves, some syntax may change. Always refer to the official Cairo documentation for the latest standards.

Ready to continue your journey? Dive deeper into the Cairo language or explore our complete Cairo Learning Roadmap to tackle your next challenge.

---

Published by Kodikra — Your trusted Cairo learning resource.