Problem 684

[zilet]

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.

From what you wrote, it looks like at the moment you posted, you had solved 68 5%-problems, but you still had to solve problem #684. So it seems like that were at least 69 5%-problems, isn't it? Today there are only 68 5%-problems in total (including problem #684).

Does it mean that problems can get "promoted" to a more challenging difficulty tier?

[philiplu]

Does it mean that problems can get "promoted" to a more challenging difficulty tier?

Problems do get their difficulty adjusted, up or down. This seems pretty rare.

Difficulties are, from what I gather, mostly set by the speed with which a problem is solved early in its lifetime. But there's something more going on, because I occasionally see problems that have been around for years change difficulty. I don't recall seeing any forum post explaining the process, but I might have missed it.

[moxieman19]

I've been incredibly stumped by this one, coming back to it over and over again for a year now. I just want to make sure I have the logic straight here.

• s(n) is the Inverse Digit Sum, i.e. the smallest number that yields the Digit Sum = n. e.g. s(10) = 19

• S(k) is the sum of all s(n)'s from n = 1 to k. e.g. S(20) = s(1) + s(2) + ... + s(20) = 1074

• f(i) is the ith Fibonnacci number, indexed at f(0) = 0, f(1) = 1.

• Let's call F(N) the final sum on the problem page, which is the sums of S(f(i)) for all i from 2 to N. e.g. F(5) = S(1) + S(2) + S(3) + S(5)

• Calculate F(90) mod 1000000007

Can I at least get verification that for x = s(f(90)), x has over 10^18 digits? (I know the exact number of digits but don't think I can get specific here.) As a previous user posted, I think that the idea here is finding some pattern with the "modulo shenanigans". I'm aware of a couple tricks to reduce modulo expressions, but I don't think any of them can be applied to the types of numbers being generated by s(n)...

[DJohn]

Can I at least get verification that for x = s(f(90)), x has over 10^18 digits?

You've understood the problem correctly, and x will certainly be somewhere around that size. f(90) has 19 digits, and to get a digit sum of that size you need to sum a lot of digits.

[FransM]

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

This is not correct. The problem states that we start the sum with S(2) not S(1)

BTW: I agree this is not a 5% problem.

Still looking for a solution. I can calculate up to S(40) or so before it becomes expensive. Guess I need another trick.

[pjt33]

Still looking for a solution. I can calculate up to S(40) or so before it becomes expensive. Guess I need another trick.

I hope you mean $S(f_{40})$. If not, you probably need two more tricks.

[FransM]

Indeed I meant S(f₄₀)