Problem 684

[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.

[hk]

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

'Don't ask for hints how to solve a problem'

[nicolas.patrois]

Hi,
Is sum from i=2 to i=30 S(f_i) (mod 1_000_000_007) equal to xxxxxxxxx? <value snipped by moderator>
Thank you.

[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?

[RobertStanforth]

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]

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

[hk]

Please have a look at the fastest solvers table....

[AWR]

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!

[hk]

The simple answer is: the difficulty assessment is automatically calculated based on solver times.
We've no better way to do it..

[yourmaths]

I have what I think is a correct algorithm for this problem but my answer is not being accepted.

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})$

[Animus]

The Fibonacci sequence is given as $f_0=0, f_1=1, f_2=1, f_3=2 \dots$

[yourmaths]

All good. I had a frustratingly hard-to-find typo.

[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?

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})$.

[dawghaus4]

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.

[PurpleBlu3s]

Generalise the problem such that F(N) = S(f₂) + ... + S(f_N).

I have a (slow) brute force algorithm, a medium algorithm and a fast algorithm. They all agree as far as I can push the slower ones, which is up to F(22) for the brute force and F(46) for the medium algorithm.

The brute force and medium algorithm both agree with S(20) = 1074 (the fast one only works on Fibonacci inputs).

My answer for F(90) is apparently not correct.

Is anyone willing to verify a couple of intermediate results?

[gaufowl]

Is anyone willing to verify a couple of intermediate results?

I'd be willing to do some cross verification with you. I haven't solved it yet either but I believe I have it running correctly so far up to the mid-30 of fibonacci numbers. Feel free to pm me on here.

[pjt33]

The brute force and medium algorithm both agree with S(20) = 1074 (the fast one only works on Fibonacci inputs).

I think it's a legitimate hint to say that there's nothing special about Fibonacci inputs. My best guess is that the question asks for the particular Fibonacci-based sum that it does as a way of making the calculation expensive enough to trip up brute force solutions without using inputs that don't fit in a 64-bit integer.

[Rock5]

This is way more difficult than 5%.

After spending about a week on this, this will be the first 5% difficulty challenge I'm going to have to give up on. I've completed 68 of them so far.

Given that it's impossible for the s(n) function to generate output with the high Fibonacci numbers as input without running out of memory, and there is no direct relation between n and the s(n) output, it's obvious that there needs to be some sort of modulo shenanigans happening in the s function that I can't figure out. I suspect that proficiently, mathematically inclined people, that are already familiar with this sort of problem, will be able to solve it. Being primarily a programmer that likes math, this ones impossible for me.

You can also tell it's difficult as only 2145 people have solved it, whereas most 5% challenges are completed by about 60,000 people.

If there is an automated process for selecting the difficulty, perhaps the process needs to be examined.

[DJohn]

The other 5% problems with tens of thousands of solvers are many years older than this. They've had a lot more time to accumulate. Other 5% problems of a similar age (686: 2733, 700: 2380, 719: 2082, 751: 1193, at the time of posting) have similar numbers of solvers, steadily decreasing as they get younger. 684 is slightly below the curve, but not by much. It is perhaps at the hard end of 5%, but it isn't a 10% problem.

Difficulty is very subjective, and depends greatly on the knowledge of the solver. I remember this one being fairly simple, but annoying to implement. Other people will have had other experiences of it.

[maujjy]

Generalise the problem such that F(N) = S(f₂) + ... + S(f_N).

I have a (slow) brute force algorithm, a medium algorithm and a fast algorithm. They all agree as far as I can push the slower ones, which is up to F(22) for the brute force and F(46) for the medium algorithm.

The brute force and medium algorithm both agree with S(20) = 1074 (the fast one only works on Fibonacci inputs).

My answer for F(90) is apparently not correct.

Is anyone willing to verify a couple of intermediate results?

Hi, I am having exactly this problem. My brute-force and slick algorithms agree up to F(30) as PurpleBlu3s puts it, and my brute-force really is the most naive thing (I suspect, I know what he means by "medium", I haven't tried that but I'll have a go now to see if I can get up to 46) but I have F(90) wrong. Is anyone willing to see if they agree with my value of F(30)?

EDIT: It was my own sloppiness, I overlooked a decision I made that introduced precision errors later on...All good now!