Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Project Euler

Name: Anonymous 2010-09-24 23:18

Hey /prog/, I know I'm a little late to the party, but I was wondering how many problems you've solved thus far.
Other discussion regarding Project Euler is also welcome!

Name: Anonymous 2010-09-28 13:50

Problem 303
For a positive integer n, define f(n) as the least positive multiple of n that, written in base 10, uses only digits ≤2.

Thus f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222.

Also sum_n=1^100 {f(n)/n} = 11363107

Find sum_n=1^10000 {f(n)/n}.

http://projecteuler.net/index.php?section=problems&id=303

f[n_] := FromDigits@IntegerDigits[n, 3]
Timing[Sum[For[i = 1, Mod[f[i], n] != 0, i++]; f[i]/n, {n, 100}]]
{0.206891, 11363107}


Above is a brute force that is really slow and inefficient. This is ok for some of the earlier problems, but not this one.

I was thinking using a some divisibility tests and modular arithmetic such as checking ending digits and adding blocks of digits described here http://webspace.ship.edu/msrenault/divisibility and here http://webspace.ship.edu/msrenault/divisibility/StupidDivisibilityTricks.pdf

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List