Project Euler Forum

Hi Folks,

I think there is a problem with problem 302: I think there are substantially more Strong Achilles numbers than you are allowing for: I think I can find 8 below 1000, so there will be quite a lot more below 10,000. To avoid spoilers, I don't want to give the numbers, or how I deduced them, but I also don't want to waste time writing the programme if I am completely missing something...

Best wishes,

DDRM

I don't think it would do much harm it you listed those 8 below thousand, so that we can look together where your problem is.
Or better still: list them for yourself and find the prime factorisations of n and Phi(n).

Hi HK,

Thanks: my 8 candidates are:
108 = 2^2.3^3 phi(108)=36 = 2^2.3^2
216= 2^3.3^3 phi (216)=72=2^3.3^2
324=2^2.3^4 phi(324)=108=2^2.3^3
432=2^4.3^3 phi(432)=144=2^4.3^2
500=2^2.5^3 phi(500)=200=2^3.5^2
648=2^3.3^4 phi(648)=216= 2^3.3^3
864=2^5.3^3 phi(864)=288=2^5.3^2
972=2^2.3^5 phi(972)=324=2^2.3^4

Best wishes,

D

Hi ddrm,
36=6^2
216= 6^3
They are perfect powers.
[EDIT] Thank you hk, it is my mistake.

niino wrote:Hi ddrm,
36=6^2
216= 6^3
They are not perfect powers.

Actually they are perfect powers and thus no Achilles Numbers.
The same holds for 324=18^2.

Aha! Thanks, Niino.

I misinterpreted that rule as meaning not pure powers of a single prime factor - I missed the possibility of having composites! That will certainly narrow the possibilities..

I knew I would be missing something stupid, but couldn't for the life of me see what it was...

D

Man--I've spent some time on this (thoroughly annoying) problem!
I am definitely not a math whiz.
But, now that I think I'm getting close to solving it I've run into a problem.
I get 276 strong Achilles for 10^8!?!
My algo does respond with 7 for 10^4.
Would someone tell me how many Achilles numbers (not strong Achilles) are under 10^8. I'm hoping that will help me figure out what I'm doing wrong. (Besides the fact that there is some math trick that I don't get!!! )
Thanks.

I count 10553 of them (60 below 10^4).

Ach! 9994!
Something wrong in my algorithm.
Thanks, Trip.

Ah! Many thanks to hk and niino! I was also confused and didn't realize that any perfect powers were excluded, and not merely perfect powers of primes. Now I'm a little closer, since I get 7 strong Achilles numbers less than 10^4, but for some reason I am only getting 642 strong Achilles numbers less than 10^8. I must have some other bug somewhere....

Edited to add: I think I found it. It looks like I was being too clever in limiting the primes that could appear as bases in the factorization of the number. After loosening the criteria a bit, I now get the expected 656 less than 10^8.

But my code is too slow, and uses too much memory.

I am still having difficulties with the numbers, for instance, I get 6 Strong Achilles for n<10^3 and I get 15 for n<10^4. I am wondering if its really 7 Strong Achilles for n<1000 and not n<10,000.

For n < 10^4 I get 15 numbers! not 7.

Take Achilles # 432, Phi(432) is 144, which is a perfect square (12^2). Does this mean 432 should be excluded?

Since one member already posted his results for n<10^4, and he only got 8 and some of those were excluded I am seriously confused..for n<10^3, I have 108,432,500,648,864,972; 6 #s. I've checked my code and numbers carefully and have factored several of these by hand. Can someone at least tell me if this little sample is correct? S.A =5000, Phi(5000) = 2000; S.A =2000, Phi(2000) = 800

I'm not trying to weasel anything, but I've check my numbers thoroughly and something isn't adding up. So I am asking 2 things really, Did the question really mean 7 Strong Achilles for n<10^3 instead of 10^4, and does Phi(n) being a perfect square exclude n from being a Strong Achilles?

Thanks!
BostonBear
aka Mike

Ok , pls disregard my last question, I just figured it out. Writing out the question gave me the answer. If need be, go ahead and delete my last post.

Thanks!
BostonBear