Problem 618

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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.

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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
bentaylortheonly
Posts: 3
Joined: Wed Jan 17, 2018 7:39 pm

Problem 618

Post by 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.
Last edited by RobertStanforth on Sat Jan 20, 2018 9:43 pm, edited 1 time in total.
Reason: Renaming for consistency
traxex
Posts: 66
Joined: Thu Oct 19, 2017 1:30 pm

Re: PE 618

Post by 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.
Technically, everyone is full of himself.
LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

Re: PE 618

Post by LarryBlake »

Image
Alobar
Posts: 4
Joined: Mon Apr 17, 2017 1:57 am

Re: Problem 618

Post by 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
Posts: 8
Joined: Thu Nov 22, 2018 3:48 am

Re: Problem 618

Post by 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$.
Image
Alobar
Posts: 4
Joined: Mon Apr 17, 2017 1:57 am

Re: Problem 618

Post by Alobar »

brob26 wrote: Tue Jul 30, 2019 12:46 pm 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
Posts: 2
Joined: Wed Apr 08, 2020 10:10 pm

Problem 618 - optimization

Post by 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! :D
User avatar
RobertStanforth
Administrator
Posts: 1619
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 618 - optimization

Post by RobertStanforth »

AlbertMartino13 wrote: Wed Apr 08, 2020 10:32 pm 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
Posts: 2
Joined: Wed Apr 08, 2020 10:10 pm

Re: Problem 618

Post by 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 :)
Post Reply