Kevin Wampler <wam### [at] u washington edu> wrote:
> triple_r wrote:
> > http://projecteuler.net/index.php?section=problems&id=160
> >
> > I spent a lot of time on this, but was never able to get the right answer. You
> > basically need a closed-form solution since you can't even iterate a simple
> > model that far in a reasonable amount of time.
>
> My guess would be that the solution isn't closed form but can be solved
> for in time which is logarithmic (or some other o(n) function) in n.
> Looks fun though (and tricky)!
Yes, I think you're right. I should be more careful with what I mean by 'closed
form.' I did feel better when I cheated and looked at the answer though. (#160)
http://www.haskell.org/haskellwiki/Euler_problems/151_to_160
I guess I just neglected to remember that the group of invertible elements of
the ring of integers modulo 10^d is isomorphic to the product of a cyclic group
of order 2 and another cyclic group.
It was so obvious!
- Ricky
Post a reply to this message
|