Integers with Decreasing Prime Powers

Any positive integer can be written as a product of prime powers: $p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$,
where $p_i$ are distinct prime integers, $a_i \gt 0$ and $p_i \lt p_j$ if $i \lt j$.
A decreasing prime power positive integer is one for which $a_i \ge a_j$ if $i \lt j$.
For example, $1$, $2$, $15=3 \times 5$, $360=2^3 \times 3^2 \times 5$ and $1000=2^3 \times 5^3$ are decreasing prime power integers.
Let $C(n)$ be the count of decreasing prime power positive integers not exceeding $n$.
$C(100) = 94$ since all positive integers not exceeding $100$ have decreasing prime powers except $18$, $50$, $54$, $75$, $90$ and $98$.
You are given $C(10^6) = 922052$.
Find $C(10^{13})$.

This seems to be a complex combinatorics problem which is a bit tricky to solve without programming support. We would need a computer to come up with an efficient algorithm to calculate $C(10^{13})$ directly.

The approach will be along these lines:

1. First, understand that we aren’t dealing with decoding the prime factors of each number up to $10^{13}$ which would be unfathomably computationally expensive. Instead, we work within the prime powers representation. For a number in the form $p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$, we want $a_i \ge a_j$ if $i \lt j$.

2. Calculate how many combinations of sets of prime powers you can create that fit within the limit of $10^{13}$ and abide by the above condition. Given the limit is relatively high, it would make sense to first calculate the maximal power of each prime where the power of a prime, $p$, doesn’t exceed $10^{13}$ (i.e., calculate $a$ where $p^a \le 10^{13}$ but $p^{a+1} > 10^{13}$ for $p=2, 3, 5, 7, 11, 13,…$).

3. Associate prime powers to the primes. For each set of prime powers, sort in decreasing order and associate higher power to lower primes and go on in a reverse direction. Count all such sets. Here we are doing a reverse calculation getting all permutations from power sets and mapping to prime sets, thus getting count of all numbers with the prime-power condition.

4. Now, here’s the tricky bit: you need to avoid double counting. You need to develop a methodology to ensure that each distinct combination up to $10^{13}$ is only counted once.

This problem seems more like programming-based number theory problem and might require good bit manipulation and dynamic programming knowledge.

Due to the enormous computation involved, this can’t be done manually but a good understanding of these steps is crucial in case you need to program a solution for it.

More Answers: