Problem 618

[bentaylortheonly]

Why does
S(5)=5+6=11
?
Is that a mistake?

The prime factors of 6 are 2x3 which add up to 5
But why 5? The only prime factors of 5 are 1 and 5 which add up to 6, not 5.
I would have thought S(5) was just 6.

[traxex]

The number 1 is not a prime. The only prime factor of 5 is itself, which is true for all primes.

Otherwise you would have 5 = 1*5 = 1*1*5 = ..., so the prime factorization would not be unique, which would complicate many definitions.

In the past 1 was often considered a prime. See Wikipedia for a bit of interesting history. Seems like Euler was ahead of his time in this as well.

[LarryBlake]

Another good link is https://en.wikipedia.org/wiki/Fundament ... arithmetic .

[Alobar]

I feel like my algorithm is correct, as I get correct values for all the numbers I can work out by hand (of which ive done far too many heh). I am not getting the right answer tho, can someone tell me if these are correct?

Is S(21) = 100864?
is the sum of the function for the first 15 fibs mod 10^9 = xxxxxxxx

[brob26]

Your answer for $S(21)$ is wrong- the correct value is roughly a quarter of yours. If it helps diagnose the bug, there are $30$ distinct numbers which have a prime factor sum of $21$; the lowest is $38$, and the largest $2187$.

[Alobar]

Your answer for $S(21)$ is wrong- the correct value is roughly a quarter of yours. If it helps diagnose the bug, there are $30$ distinct numbers which have a prime factor sum of $21$; the lowest is $38$, and the largest $2187$.

thank you so much, that was very helpful! I found my bug and got the right answer

[AlbertMartino13]

I've really enjoyed tackling these problems and I feel like I've learned a lot through them! Figured it's about time I start interacting with the community

My main blockers for problems tend to be optimization. There will often be an iteration where processing time is no longer justifiable. At this point, I go back to try to thin out an algorithm or rewrite it completely, but I'm feeling stuck on this problem and want to learn more with some help.

My current algorithm for S(n) is as follows
Removed by moderator

I feel like this pseudocode is a pretty poor representation of my process I get the following result:
Removed by moderator

I understand that <removed> concepts might be useful here, as suggested in some other forums. If so, can someone point me in the direction of what I could be storing/recalling? Is there a math concept that would allow us to not check every iteration of the multiplicity? Thanks in advance. The stuff you guys come up with are mind-boggling by the way, lots of respect!

[RobertStanforth]

I'm feeling stuck on this problem and want to learn more with some help.

I have edited this post to remove potential spoilers, and moved it to the already existing topic for Problem 618 - see the red banner text at the top of this page.
Good luck solving the problem! If successful, you'll be able to discuss alternative solutions in the problem's private forum on the main site. This public forum is for clarifications on the problem statement, not for pointers on how to solve it.

[AlbertMartino13]

Ah, sorry about that. In that case, I'll keep trying to tackle it myself. Thanks for taking the time to read through my post