Problem #40 hard
Champernowne's Constant
An irrational decimal fraction is created by concatenating the positive integers:
It can be seen that the th digit of the fractional part is .
If represents the th digit of the fractional part, find the value of the following expression.
Implementations
// Answer: 210
// Authored by: Tim Varley 💘// Assisted-by: Grok Code Fast via Crush 💘 <crush@charm.land>
#include <iostream>#include <vector>#include <string>
long long champernowne() { std::string s = ""; long long num = 1; while(s.size() < 1000001) { s += std::to_string(num++); } long long product = 1; std::vector<int> positions = {1,10,100,1000,10000,100000,1000000}; for(int pos : positions) { product *= s[pos-1] - '0'; } return product;}
#if ! defined UNITTEST_MODEint main(int argc, char const *argv[]) { std::cout << champernowne() << std::endl;}#endif // UNITTEST_MODESolution Notes
Mathematical Background
Champernowne’s constant is formed by concatenating positive integers: 0.1234567891011121314…
This constant is known to be transcendental (proved by Kurt Mahler in 1961), meaning it is not the root of any polynomial equation with rational coefficients.
The problem requires finding digits at specific positions in this concatenation and computing their product.
Algorithm Analysis
The implementations use direct string construction:
- Build a string by concatenating integers 1, 2, 3, … until exceeding 1,000,000 characters
- Extract digits at positions 1, 10, 100, 1000, 10000, 100000, 1000000 (1-based indexing)
- Multiply these digits together
The approach is straightforward but requires careful handling of string indexing.
Performance Analysis
- Time Complexity: O(L) where L=10⁶, dominated by string concatenation and character access. Executes in milliseconds.
- Space Complexity: O(L) for storing the concatenated string (~1MB).
- Execution Time: Very fast (under 1 second), suitable for real-time applications.
- Scalability: Linear in required length, but memory usage becomes significant for larger constants.
Key Insights
- The digits product is 1 × 1 × 5 × 3 × 7 × 2 × 1 = 210
- String concatenation is efficient in most languages for this scale
- Position-based extraction requires careful 0-based vs 1-based indexing
- The constant exhibits interesting digit distribution patterns
Educational Value
This problem teaches:
- Construction of mathematical constants through concatenation
- String manipulation and indexing in programming
- The concept of transcendental numbers
- Handling large strings efficiently
- Position-based digit extraction and arithmetic operations