Problem 618
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.

 Posts: 3
 Joined: Wed Jan 17, 2018 7:39 pm
Problem 618
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.
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.
Last edited by RobertStanforth on Sat Jan 20, 2018 9:43 pm, edited 1 time in total.
Reason: Renaming for consistency
Reason: Renaming for consistency
Re: PE 618
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.
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.
Technically, everyone is full of himself.

 Posts: 100
 Joined: Sat Aug 29, 2009 8:49 pm
Re: PE 618
Another good link is https://en.wikipedia.org/wiki/Fundament ... arithmetic .
Re: Problem 618
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
Is S(21) = 100864?
is the sum of the function for the first 15 fibs mod 10^9 = xxxxxxxx
Re: Problem 618
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$.
Re: Problem 618
thank you so much, that was very helpful! I found my bug and got the right answer

 Posts: 2
 Joined: Wed Apr 08, 2020 10:10 pm
Problem 618  optimization
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 mindboggling by the way, lots of respect!
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 mindboggling by the way, lots of respect!
 RobertStanforth
 Administrator
 Posts: 1619
 Joined: Mon Dec 30, 2013 11:25 pm
Re: Problem 618  optimization
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.AlbertMartino13 wrote: ↑Wed Apr 08, 2020 10:32 pm I'm feeling stuck on this problem and want to learn more with some help.
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.

 Posts: 2
 Joined: Wed Apr 08, 2020 10:10 pm
Re: Problem 618
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