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)!

Post a reply to this message

Kevin Wampler <wam### [at] uwashingtonedu> 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