Big numbers

[SiliconWizard]

Some (many) problems from Project Euler are interesting.

This one for instance, which looks intimidating at first: https://projecteuler.net/problem=672

Try not to spoil answers. You can give general ideas or ask general questions, but no solution here please.

Caution: Project Euler is addictive

[mrflibble]

Some (many) problems from Project Euler are interesting.

This one for instance, which looks intimidating at first: https://projecteuler.net/problem=672

Try not to spoil answers. You can give general ideas or ask general questions, but no solution here please.

Caution: Project Euler is addictive

Addictive? Naaaaaah. I only just want to do just one more puzzle  And then another, and then another... Just one more after that, and then I'll quit. Promise. 

As for that particular numero 672, did you find "the" solution yet? Probably since you mention it being intimidating at first, thus possibly implying that it is easy, oh so easy ... in hindsight.  I tried to solve it the elegant way some time ago, and failed horribly.  At one point I got sidetracked by one of those "hey, I wonder if ... works" ideas that a) did not work out and b) took up waaay too much time. So at a certain point I just had to take a break from it. I did however find a polynomial expansion for S(n) as a function of the digits d_i of n. And also got the  value of the given N as sequence of repeating digits in base 7. So last step is to tie those together, with a modulo step in the middle for the coefficients of that S(n) polynomial expansion.

There probably is an elegant solution involving H(10) and some clever inductive step, but by now I am invested in medium brute forcing it the algebraic way. If only to see if that will also work. Basically trying to see if I can get it to work with symbolic regression. Total overkill, but this sort of problem is a nice vehicle for trying out some stuff. Plus, there is a known solution, so that's always nice.

[SiliconWizard]

Yes I did manage. But it took me a few days at the time, it was definitely not just a one-evening puzzle.

There are several approaches, the most common ones including finding appropriate recurrence relations and using modular arithmetic. My own implementation was the fastest from what was posted at the time (there's an "hidden" thread for each problem that you can access once you've found the solution, so I could see what some others had done too), except for one (but the guy didn't state exec. time, he just said "instantly"...) that used dynamic programming. Dynamic programming is a frequent option for many Project Euler problems, and it's not always easy to use (well, at least it's not easy to map a given problem to a DP problem...)

Brute force is impossible here (like with most PE problems) as it would take months or years to execute IIRC...

It's against the rules to post answers or methods, so I won't. If you're interested, I can give you the solution by PM which will give you access to the PE thread (in which I posted my solution with some explanations.)

[mrflibble]

Nice! I think I will give it one more go this weekend. Only this time with an egg timer on the desk ... 

[SiliconWizard]

Alright. If you end up dry and want to at least get some pointers by accessing the solution thread, just PM and I'll PM you back with the answer so you can access it.

[mrflibble]

Woohoo! Got it in one go. Current solution is pretty slow, but I wanted to see if I was on the right track at all. The polynomial expansion did help with a few things. For example tracking which steps depend on what bits of data. Not that you couldn't do that any other way, but I found it rather convenient. Right now I have something that is linear in the number of digits of (7**K -1)//11. So H(1E9) which means ~ 1E8 digits takes order 1E8 steps. I let it run with for increasing powers of 10, and runtime does indeed multiply with about 10 for each such increase. I strongly suspect that with some memoization it can be done either in sqrt or log time. But just for the fun of it I want to see if it's possible to extract a recurrence relation from the polynomials, what with the repeating digits. Or maybe I should just leave it alone for some time.

Nope. Not addictive at all.