Armstrong Numbers in Cairo: Complete Solution & Deep Dive Guide
Mastering Armstrong Numbers in Cairo: The Complete Guide
An Armstrong number is a fascinating mathematical curiosity where a number equals the sum of its own digits, each raised to the power of the number of digits. This guide provides a comprehensive walkthrough on how to identify these numbers using the Cairo programming language, covering the core logic, implementation details, and performance considerations from zero to hero.
The Curious Case of Self-Aware Numbers
Imagine you're building a new smart contract on Starknet, and you come across a requirement for a seemingly simple mathematical validation. It's a problem that looks like a high-school math quiz but quickly unravels into a test of your foundational programming skills: logic, iteration, and number manipulation. This is the world of Armstrong numbers, also known as narcissistic numbers.
You might wonder, "Why bother with a mathematical puzzle when I'm focused on blockchain?" The answer lies not in the direct application of Armstrong numbers, but in the skills you build by solving the problem. Mastering this challenge, especially in a provably-secure language like Cairo, sharpens your ability to handle integer arithmetic, write efficient loops, and structure your code logically—skills that are absolutely critical in the high-stakes environment of decentralized applications.
This guide, part of the exclusive kodikra.com Cairo learning path, will take you from the basic definition to a fully functional and optimized Cairo implementation. We'll break down the problem, build the solution step-by-step, and explore the nuances of writing clean, efficient code in the Starknet ecosystem.
What Exactly Is an Armstrong Number?
Before we dive into the code, let's establish a crystal-clear definition. An Armstrong number (or a narcissistic number) is a positive integer that is equal to the sum of its own digits, where each digit is raised to the power of the total number of digits in the number.
This sounds complex, but it's straightforward with a few examples:
- 9 is an Armstrong number: It has 1 digit. So,
91 = 9. The sum is 9, which equals the original number. - 153 is an Armstrong number: It has 3 digits. So, we calculate
13 + 53 + 33. This equals1 + 125 + 27, which sums up to153. The sum matches the original number. - 1634 is an Armstrong number: It has 4 digits. The calculation is
14 + 64 + 34 + 44. This equals1 + 1296 + 81 + 256, which sums up to1634.
Conversely, a number like 10 is not an Armstrong number. It has 2 digits, but 12 + 02 = 1, which does not equal 10.
The core challenge is to create a program that can take any given number and perform this verification process automatically. This involves three main computational steps:
- Counting the number of digits.
- Extracting each digit individually.
- Performing the power and sum calculation.
Why Bother with This Problem in Cairo?
While Armstrong numbers don't appear in everyday business logic, solving this problem is an exceptional educational exercise for several reasons, particularly for a Cairo developer.
Strengthening Foundational Logic
This problem forces you to think algorithmically. You must break down a high-level mathematical rule into a sequence of simple, executable steps. This process of decomposition is the essence of programming.
Mastering Integer Manipulation
In many high-level languages, you might be tempted to convert the number to a string to count and access its digits. However, the most performant and mathematically pure solution involves arithmetic operations like the modulo (%) and integer division (/). Working with these operators in Cairo, especially with its fixed-size integer types like u128 or u256, builds a deep understanding of how computers handle numbers under the hood.
Understanding Cairo's Constraints and Features
Cairo is not a general-purpose language like Python or JavaScript; it's designed for verifiable computation. This means its standard library is more focused and might lack some of the convenient math functions found elsewhere. Implementing a solution for Armstrong numbers requires you to build helper functions (like a power function) from scratch, giving you a better feel for the language's syntax, control flow (loop), and function composition.
Writing Testable Code
The problem has clear inputs and expected boolean outputs, making it perfect for practicing test-driven development (TDD). You can write a suite of tests covering single-digit numbers, multi-digit Armstrong numbers, non-Armstrong numbers, and edge cases like zero. In the Cairo ecosystem, this means getting comfortable with the scarb test command.
How to Implement the Armstrong Number Checker in Cairo
Let's architect the solution. Our goal is to create a primary function, is_armstrong_number(num: u128) -> bool, that returns true if the input num is an Armstrong number and false otherwise. To keep our code clean and modular, we'll break the logic into smaller helper functions.
The Algorithm Blueprint
Here is the logical flow our program will follow. We'll take an input number, say 153, and process it through these steps.
● Start with Input (e.g., 153)
│
▼
┌─────────────────────────┐
│ 1. Count Digits │
│ (153 -> 3 digits) │
└────────────┬────────────┘
│
▼
┌─────────────────────────┐
│ 2. Initialize Sum = 0 │
└────────────┬────────────┘
│
▼
┌─────────────────────────┐
│ 3. Loop through Digits │
└────────────┬────────────┘
┌────────┴────────┐
│ │
▼ ▼
┌──────────────┐ ┌────────────────┐
│ Isolate Digit│ │ Raise to Power │
│ (153 % 10 -> 3)│ │ (3 ^ 3 -> 27) │
└───────┬──────┘ └────────┬───────┘
│ │
└─────────┬────────┘
▼
┌─────────────────┐
│ Add to Sum │
│ (Sum = 0 + 27) │
└─────────────────┘
┌────────┴────────┐
│ │
▼ ▼
┌──────────────┐ ┌────────────────┐
│ Isolate Digit│ │ Raise to Power │
│ (15 % 10 -> 5) │ │ (5 ^ 3 -> 125) │
└───────┬──────┘ └────────┬───────┘
│ │
└─────────┬────────┘
▼
┌─────────────────┐
│ Add to Sum │
│ (Sum = 27 + 125)│
└─────────────────┘
┌────────┴────────┐
│ │
... and so on ...
│
▼
┌─────────────────────────┐
│ 4. Final Comparison │
│ (Sum == Original Num?)│
└────────────┬────────────┘
│
┌────────┴────────┐
│ │
▼ ▼
┌───────────┐ ┌────────────┐
│ Return true │ │ Return false │
└───────────┘ └────────────┘
Step 1: The Cairo Project Setup
First, ensure you have the Cairo toolchain installed. You can create a new project using Scarb, the Cairo package manager.
scarb new armstrong_numbers
cd armstrong_numbers
This command creates a standard Cairo library project structure. All our logic will go into the src/lib.cairo file.
Step 2: The Full Cairo Implementation
Open src/lib.cairo and replace its contents with the following code. We will walk through each part of this code in the next section.
// A helper function to calculate the power of a base to an exponent.
// Cairo's core library doesn't have a built-in integer power function,
// so we implement a simple one using a loop.
fn power(base: u128, exp: u32) -> u128 {
let mut result: u128 = 1;
let mut i: u32 = 0;
loop {
if i >= exp {
break;
}
// Note: This could overflow if base^exp exceeds the u128 limit.
// For this problem's constraints, it's generally safe.
result *= base;
i += 1;
};
result
}
// A helper function to count the number of digits in a given number.
// It works by repeatedly dividing the number by 10 until it becomes 0.
fn count_digits(mut num: u128) -> u32 {
if num == 0 {
return 1;
}
let mut count: u32 = 0;
loop {
if num == 0 {
break;
}
num /= 10;
count += 1;
};
count
}
/// Checks if a number is an Armstrong number.
/// An Armstrong number is a number that is the sum of its own digits
/// each raised to the power of the number of digits.
pub fn is_armstrong_number(num: u128) -> bool {
if num == 0 {
return true; // Conventionally, 0 can be considered an Armstrong number.
}
// First, determine the number of digits.
let n_digits = count_digits(num);
let mut sum_of_powers: u128 = 0;
let mut temp_num = num;
// Now, iterate through the number to process each digit.
loop {
if temp_num == 0 {
break;
}
// Isolate the last digit using the modulo operator.
let digit = temp_num % 10;
// Raise the digit to the power of n_digits and add to the sum.
sum_of_powers += power(digit, n_digits);
// Remove the last digit by integer division.
temp_num /= 10;
};
// The number is an Armstrong number if the original number
// equals the calculated sum of powers.
sum_of_powers == num
}
#[cfg(test)]
mod tests {
use super::{is_armstrong_number};
#[test]
fn test_zero_is_an_armstrong_number() {
assert(is_armstrong_number(0), '0 is an armstrong number');
}
#[test]
fn test_single_digit_numbers_are_armstrong_numbers() {
assert(is_armstrong_number(5), '5 is an armstrong number');
}
#[test]
fn test_there_are_no_two_digit_armstrong_numbers() {
assert(!is_armstrong_number(10), '10 is not an armstrong number');
}
#[test]
fn test_three_digit_armstrong_number() {
assert(is_armstrong_number(153), '153 is an armstrong number');
}
#[test]
fn test_three_digit_non_armstrong_number() {
assert(!is_armstrong_number(100), '100 is not an armstrong number');
}
#[test]
fn test_four_digit_armstrong_number() {
assert(is_armstrong_number(1634), '1634 is an armstrong number');
}
#[test]
fn test_four_digit_non_armstrong_number() {
assert(!is_armstrong_number(1635), '1635 is not an armstrong number');
}
#[test]
fn test_seven_digit_armstrong_number() {
assert(is_armstrong_number(9474), '9474 is an armstrong number');
}
}
Step 3: Running the Tests
With the code and tests in place, you can verify the correctness of your implementation from your terminal using Scarb.
scarb test
If all tests pass, you'll see a confirmation message, indicating your logic is sound for the tested cases.
Where the Magic Happens: A Detailed Code Walkthrough
Understanding the full code block is crucial. Let's dissect each function to clarify its role and the Cairo syntax involved.
The power Helper Function
fn power(base: u128, exp: u32) -> u128 {
let mut result: u128 = 1;
let mut i: u32 = 0;
loop {
if i >= exp {
break;
}
result *= base;
i += 1;
};
result
}
fn power(base: u128, exp: u32) -> u128: This defines a function namedpowerthat accepts abaseof typeu128(a 128-bit unsigned integer) and an exponentexpof typeu32. It returns au128value.let mut result: u128 = 1;: We initialize a mutable variableresultto 1. This is our accumulator. It's 1 because any number to the power of 0 is 1.loop { ... }: This is Cairo's primary looping construct. It will run indefinitely until abreakstatement is encountered.if i >= exp { break; }: The loop's exit condition. We iterateexptimes.result *= base;: In each iteration, we multiply the currentresultby thebase.
The count_digits Helper Function
fn count_digits(mut num: u128) -> u32 {
if num == 0 {
return 1;
}
let mut count: u32 = 0;
loop {
if num == 0 {
break;
}
num /= 10;
count += 1;
};
count
}
fn count_digits(mut num: u128) -> u32: Defines a function that takes a mutableu128and returns the digit count as au32.if num == 0 { return 1; }: This is an important edge case. The number 0 has one digit.num /= 10;: This is the core of the logic. Integer division by 10 effectively removes the last digit of a number (e.g.,153 / 10 = 15).count += 1;: For every digit we remove, we increment our counter.- The loop continues until
numbecomes 0, at which point we have counted all the digits.
The Main Function: is_armstrong_number
This is where we orchestrate the entire process. Here's a data flow diagram illustrating its internal logic.
Input `num` (e.g., 153)
│
├─► Call `count_digits(153)` ─► Returns `n_digits` (3)
│
▼
Initialize `sum_of_powers` = 0
Initialize `temp_num` = 153
│
▼
Loop while `temp_num` > 0
├─────────────────────────────┐
│ Iteration 1: `temp_num`=153 │
│ `digit` = 153 % 10 (→ 3) │
│ `p` = power(3, 3) (→ 27)│
│ `sum_of_powers` += 27 (→ 27)
│ `temp_num` /= 10 (→ 15)│
└─────────────────────────────┘
│
▼
├─────────────────────────────┐
│ Iteration 2: `temp_num`=15 │
│ `digit` = 15 % 10 (→ 5) │
│ `p` = power(5, 3) (→ 125)
│ `sum_of_powers` += 125(→ 152)
│ `temp_num` /= 10 (→ 1) │
└─────────────────────────────┘
│
▼
├─────────────────────────────┐
│ Iteration 3: `temp_num`=1 │
│ `digit` = 1 % 10 (→ 1) │
│ `p` = power(1, 3) (→ 1) │
│ `sum_of_powers` += 1 (→ 153)
│ `temp_num` /= 10 (→ 0) │
└─────────────────────────────┘
│
▼
Loop ends (`temp_num` is 0)
│
▼
Comparison: `sum_of_powers` (153) == `num` (153) ?
│
└─► Return `true`
The code implements this flow perfectly. It first calls count_digits to get the exponent. Then, it uses a temporary variable temp_num (to preserve the original num for the final comparison) and loops through it. In each iteration, it peels off the last digit with % 10, calculates its power using our helper function, adds it to the running total, and then removes the digit with / 10. Finally, it compares the accumulated sum with the original number.
Alternative Approaches and Performance Considerations
While the arithmetic approach is efficient and idiomatic for systems programming, it's worth knowing about other methods you might encounter in different languages.
String Conversion Method
In languages like Python or JavaScript, a common approach is to convert the number to a string.
- Convert the number to a string:
153 -> "153". - The number of digits is simply the length of the string:
len("153") -> 3. - Iterate through each character of the string:
'1', '5', '3'. - Convert each character back to an integer, raise it to the power of the length, and sum the results.
This method can be more readable for beginners but usually comes with a performance penalty due to the overhead of type conversions (integer to string, character to integer) and memory allocation for the string.
Pros and Cons of Each Approach
| Aspect | Arithmetic Method (Modulo/Division) | String Conversion Method |
|---|---|---|
| Performance | Generally faster. Involves only low-level CPU integer operations. | Slower due to overhead of string allocation and type conversions. |
| Memory Usage | Very low. Uses a few fixed-size integer variables. | Higher. Requires memory allocation for the string representation of the number. |
| Readability | Can be less intuitive for beginners but is a standard pattern for number manipulation. | Often considered more straightforward and easier to read for those unfamiliar with arithmetic tricks. |
| Language Idiom | Highly idiomatic for systems languages like C, Rust, and Cairo. | Common in high-level scripting languages like Python and JavaScript. |
For Cairo, which is designed for performance and efficiency in the context of ZK-rollups, the arithmetic method is unequivocally the superior choice. It aligns perfectly with the language's philosophy of staying close to the metal and avoiding unnecessary overhead.
Frequently Asked Questions (FAQ)
- 1. What is the difference between an Armstrong number and a narcissistic number?
There is no difference. The terms "Armstrong number," "narcissistic number," and "pluperfect digital invariant" (PPDI) all refer to the same mathematical concept. "Armstrong number" is the most common name used in programming challenges.
- 2. Are negative numbers or decimals considered Armstrong numbers?
The definition is typically restricted to positive integers. The concept doesn't naturally extend to negative numbers or decimals in a standardized way.
- 3. How does this logic handle very large numbers in Cairo, like
u256? The provided code uses
u128, but it can be easily adapted foru256by changing the type signatures. The core logic remains identical. However, be mindful of potential overflows in thepowerfunction. The sum of powered digits can grow extremely fast and may exceed even theu256limit for very large input numbers, although this is rare for known Armstrong numbers.- 4. Are there an infinite number of Armstrong numbers?
This is an open question in mathematics. It is conjectured that there are only a finite number of Armstrong numbers. In base 10, there are only 88 known Armstrong numbers, the largest of which has 39 digits.
- 5. What is the next Armstrong number after 153?
The next two Armstrong numbers after 153 are 370 (
3^3 + 7^3 + 0^3 = 27 + 343 + 0 = 370) and 371 (3^3 + 7^3 + 1^3 = 27 + 343 + 1 = 371).- 6. Why is my code slow for huge numbers?
The performance is primarily dictated by two factors: the number of digits and the magnitude of the exponent in the
powerfunction. The loops in bothcount_digitsand the main function run D times, where D is the number of digits. The loop inside thepowerfunction also runs D times. This makes the complexity roughly O(D2), which is very efficient as the number of digits grows logarithmically with the number itself.- 7. How can I learn more about Cairo programming?
This module is part of a structured learning curriculum. For more in-depth guides, tutorials, and challenges, we recommend exploring the complete kodikra.com guide to the Cairo language and its associated learning paths.
Conclusion: More Than Just a Puzzle
We've successfully journeyed from the mathematical definition of an Armstrong number to a robust, tested, and efficient implementation in Cairo. By breaking the problem down into manageable helper functions—count_digits and power—we built a clean and modular solution that is both easy to understand and performant.
This exercise from the kodikra.com learning curriculum serves as a powerful reminder that mastering a programming language isn't just about learning complex syntax or frameworks. It's about strengthening your grasp on the fundamentals of algorithmic thinking, logical decomposition, and efficient data manipulation. The skills honed by solving the Armstrong number challenge are directly transferable to more complex problems you will face when building secure and optimized smart contracts on Starknet.
Disclaimer: The code in this article is written for Cairo v2.6.3 and Scarb v2.6.4. The Cairo language and its ecosystem are under active development, and syntax or best practices may evolve. Always refer to the official documentation for the latest updates.
Published by Kodikra — Your trusted Cairo learning resource.
Post a Comment