发一个projecteuler上的题 Strong Achilles Number
原题链接 ：http://projecteuler.net/problem=302A positive integer n is powerful if p2 is a divisor of n for every prime factor p in n.
A positive integer n is a perfect power if n can be expressed as a power of another positive integer.
A positive integer n is an Achilles number if n is powerful but not a perfect power. For example, 864 and 1800 are Achilles numbers: $864=2^5*3^3$ and $1800=2^3*3^2*5^2$.
We shall call a positive integer S a Strong Achilles number if both S and φ(S) are Achilles numbers.1
For example, 864 is a Strong Achilles number: $\phi(864)=288=2^5*3^2$. However, 1800 isn't a Strong Achilles number because: $\phi(1800) =480=2^5*3^1*5^1$.
There are 7 Strong Achilles numbers below 104 and 656 below 108.
How many Strong Achilles numbers are there below $10^18$?
1 φ denotes Euler's totient function.
我用程序验证了一下10^8以下的情况分布如下,更大范围内就没有有效办法了.不知各位高手有没有兴趣讨论讨论.
我验证的结果:如下
1 th StrongAchilles number :500
2 th StrongAchilles number :864
3 th StrongAchilles number :1944
4 th StrongAchilles number :2000
5 th StrongAchilles number :2592
6 th StrongAchilles number :3456
7 th StrongAchilles number :5000
7 StrongAchilles numbers less than 10000
34 StrongAchilles numbers less than 100000
99 StrongAchilles numbers less than 1000000
260 StrongAchilles numbers less than 10000000
656 StrongAchilles numbers less than 100000000 对于Strong Achilles Number,其最大素因子的次数至少3次，这个可以用来大大减小搜索范围 的确能减小搜索范围,试一下. 找出来了,我的程序要跑8分钟才能找完 另第一个个StrongAchilles应该是$3^4*2^2=324$而不是500吧 3^4*2^2 = (2*3^2)^2 不是strongachilles number:)
页:
[1]