0%

Problem 578


Problem 578


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 > 0$ and $p_i<p_j$ if $i<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×5, 360=23×32×5 and 1000=23×53 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(106) = 922052.

Find C(1013).


质因数幂次下降的整数

任意正整数可以写成一系列质数的幂的乘积:$p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$,
其中$p_i$是不同的质数,$a_i > 0$,且对于任意$i<j$都有$p_i<p_j$。

若一个正整数满足,对于任意$i \lt j$都有$a_i \ge a_j$,则称之为质因数幂次下降的正整数。
例如,1,2,15=3×5,360=23×32×5和1000=23×53都是质因数幂次下降的整数。

记C($n$)为所有不超过$n$且质因数幂次下降的整数的数目。
C(100) = 94,因为除了18,50,54,75,90和98外,其它所有不超过100的正整数都是质因数幂次下降的。
此外,还已知C(106) = 922052。

求C(1013)。