Tim Varley Logo
Tim Varley Systems Engineer
Problem #40 hard

Champernowne's Constant

An irrational decimal fraction is created by concatenating the positive integers: 0.1234567891011121314151617181920210.12345678910{\color{red}\mathbf 1}112131415161718192021\cdots

It can be seen that the 1212th digit of the fractional part is 11.

If dnd_n represents the nnth digit of the fractional part, find the value of the following expression. d1×d10×d100×d1000×d10000×d100000×d1000000d_1 \times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000} \times d_{1000000}

Implementations

cpp
// 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_MODE
int main(int argc, char const *argv[]) {
std::cout << champernowne() << std::endl;
}
#endif // UNITTEST_MODE

Solution 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