Problem 684

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
User avatar
Kenya_A
Posts: 3
Joined: Sat Dec 12, 2015 4:09 am

Problem 684

Post by Kenya_A »

Problem 684 (View Problem)
Hi,
I haven't solved this yet, but I noticed that the example number has the same quotient and remainder when divisible by 9, so it's impossible to tell using it alone if you have made a mistake in entering one of these into the solution.

I can't solve it because, try I might, I haven't found enough tricks to calculating the numbers in a reasonable time and without overflow. I have done modulo operations after each addition and multiplication, tried (and abandoned in favour of built-ins) a method of modular exponentiation which cancels out much of the multiplying by setting the relevant exponents mod x to 1, and found closed form expressions for the sums. The limit is the exponentiations. What, besides maybe the F's thm, can speed this up? It may be finished yet by this time next year at this rate.
Image
8-) 835410_BD2wXg2iurN8FEuwdp659qnINUNqNKbA :lol:
User avatar
hk
Administrator
Posts: 10991
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 684

Post by hk »

In the big pink box at the top of the page it reads:

'Don't ask for hints how to solve a problem'
Image
User avatar
nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 4:54 pm
Contact:

Re: Problem 684

Post by nicolas.patrois »

Hi,
Is sum from i=2 to i=30 S(fi) (mod 1_000_000_007) equal to xxxxxxxxx? <value snipped by moderator>
Thank you.
Image
RudiGj
Posts: 1
Joined: Fri Jan 03, 2020 11:59 pm

Re: Problem 684

Post by RudiGj »

Just need a little bit of clarification on this problem.

Do you have to find the smallest digit sum for each term of the fibonacci sequence from the 2nd to the 90th?

Therefore the answer would be:

digitsum(1) + digitsum(2) + digitsum(3) + digitsum(5) + digitsum(8) + .... + digitsum(n) until the 90th term?
User avatar
RobertStanforth
Administrator
Posts: 1402
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 684

Post by RobertStanforth »

RudiGj wrote: Sat Jan 04, 2020 12:04 am Do you have to find the smallest digit sum for each term of the fibonacci sequence from the 2nd to the 90th?
No, that is not correct. $S(n)$ is not digitsum.
Instead, $s(n)$ is the inverse digit sum, so $\mathrm{digitsum}(s(n)) = n$.
Note also that $S$ is the sum of $s$.

So, (given a Fibonacci number $f_i$), you have to find the smallest number whose digit sum is $n$, for each number $n$ up to $f_i$. Their sum gives you $S(f_i)$.
Then the answer would be: $S(1) + S(2) + S(3) + S(5) + S(8) + ... + S(f_{90})$.
AWR
Posts: 2
Joined: Mon Apr 13, 2020 12:59 pm

Re: Problem 684

Post by AWR »

Just solved this after quite a bit of head scratching.

Seems a bit hard for a Difficulty rating of 5%?
Or maybe I'm just a bit thick?

Andrew
User avatar
hk
Administrator
Posts: 10991
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 684

Post by hk »

Please have a look at the fastest solvers table....
Image
AWR
Posts: 2
Joined: Mon Apr 13, 2020 12:59 pm

Re: Problem 684

Post by AWR »

hk wrote: Mon Apr 13, 2020 1:13 pm Please have a look at the fastest solvers table....
True, there are some quick solutions but they all revolve around figuring out the mathematics. Once done the coding is simple. How do you balance mathematical know-how against coding ability? Problem 243 was similar - it was easy if you got your head around the maths. (I was much more familiar with the mathematics required for that problem!)

I still wouldn't put this problem in the same category with problems 53 and 55 for example!
User avatar
hk
Administrator
Posts: 10991
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 684

Post by hk »

The simple answer is: the difficulty assessment is automatically calculated based on solver times.
We've no better way to do it..
Image
User avatar
yourmaths
Posts: 29
Joined: Mon Aug 25, 2014 11:00 am

Re: Problem 684

Post by yourmaths »

I have what I think is a correct algorithm for this problem but my answer is not being accepted.
RobertStanforth wrote: Sat Jan 04, 2020 9:04 am So, (given a Fibonacci number $f_i$), you have to find the smallest number whose digit sum is $n$, for each number $n$ up to $f_i$. Their sum gives you $S(f_i)$.
Then the answer would be: $S(1) + S(2) + S(3) + S(5) + S(8) + ... + S(f_{90})$.
Is this right? From the problem description the answer should be given by
$S(f_2) + S(f_3) + ... + S(f_{90})$
level = lambda number_solved: number_solved // 25
Image
User avatar
Animus
Administrator
Posts: 1915
Joined: Sat Aug 16, 2014 1:23 pm

Re: Problem 684

Post by Animus »

The Fibonacci sequence is given as $f_0=0, f_1=1, f_2=1, f_3=2 \dots$
User avatar
yourmaths
Posts: 29
Joined: Mon Aug 25, 2014 11:00 am

Re: Problem 684

Post by yourmaths »

All good. I had a frustratingly hard-to-find typo. :roll:
level = lambda number_solved: number_solved // 25
Image
codingclubwaseesucks
Posts: 1
Joined: Sat Jul 04, 2020 6:50 pm

Re: Problem 684

Post by codingclubwaseesucks »

Could you clarify what you mean about "Instead, s(n) is the inverse digit sum, so digitsum(s(n))=n"?
What is an Inverse Digit Sum?
RobertStanforth wrote: Sat Jan 04, 2020 9:04 am
RudiGj wrote: Sat Jan 04, 2020 12:04 am Do you have to find the smallest digit sum for each term of the fibonacci sequence from the 2nd to the 90th?
No, that is not correct. $S(n)$ is not digitsum.
Instead, $s(n)$ is the inverse digit sum, so $\mathrm{digitsum}(s(n)) = n$.
Note also that $S$ is the sum of $s$.

So, (given a Fibonacci number $f_i$), you have to find the smallest number whose digit sum is $n$, for each number $n$ up to $f_i$. Their sum gives you $S(f_i)$.
Then the answer would be: $S(1) + S(2) + S(3) + S(5) + S(8) + ... + S(f_{90})$.
User avatar
dawghaus4
Posts: 56
Joined: Fri Nov 29, 2013 2:22 am

Re: Problem 684

Post by dawghaus4 »

codingclubwaseesucks wrote: Sat Jul 04, 2020 6:51 pm Could you clarify what you mean about "Instead, s(n) is the inverse digit sum, so digitsum(s(n))=n"?
What is an Inverse Digit Sum?
Let digitsum(x) be the sum of the digits of the number x. For example, digitsum(19) = 10. An inverse function would reverse that. If the sum of the digits is 10, what is the number. Without the restriction, "the smallest number," there would be lots answers With the restriction, we can say 19 is the smallest number with a digit sum of 10. That is what is meant by an Inverse Digit Sum.

In the problem, n is the digit sum, and s(n) is the smallest number whose digits sum to n. digitsum(19) = 10 and s(10) = 19.

Hope that helps.
Post Reply