-
Notifications
You must be signed in to change notification settings - Fork 0
/
powerful_digit_counts.rs
31 lines (30 loc) · 1.37 KB
/
powerful_digit_counts.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
pub fn solve() -> i64 {
// For any number which is not an integral power of 10, the number of
// decimal digits it contains is equal to the ceiling of its 10-logarithm.
// For a number expressible as a base to the power of some exponent to have
// as many digits as the value of the exponent, the 10-logarithm of the
// base must be less than 1. This is only possible if the base is less than
// 10.
let sum = (2..=9)
.map(|base| {
// When the exponent is 1, the number of decimal digits is
// trivially equal to the exponent, so start from 2.
(2..)
.take_while(|&exp| {
// Once the number of digits falls short of the exponent,
// it will remain short for all following exponents,
// because the base is less than 10.
let digits = (exp as f64 * (base as f64).log10()).ceil() as i32;
digits == exp
})
.count()
})
.sum::<usize>()
// We did not consider the base 1 (for the exponent 1), because it is
// an integral power of 10 (the formula mentioned above does not work
// on such). We also did not consider the exponent 1 (for each of the
// bases from 2 to 9). Count all of them.
+ 9;
assert_eq!(sum, 49);
sum as i64
}