# Sum all numbers from 1 to 1000 divided by either 2,3,5 or 7

How do I find the sum all numbers from 1 to 1000 divided by atleast one of 2,3,5 or 7?

EDIT: I am sorry for complicating this, but I need it to work for 10^11. So anything that requires too much heap space or too long loops will fail.

-
What did you try? And are you trying to solve some project Euler question? – Pinguin Dirk Sep 20 '13 at 11:25
Well, actually it is for Prob 432. But for very a big number (instead of 1000, it is 10^11) and so anything other than a pure mathematical aproach will fail. – Roi Sep 20 '13 at 11:30
Possible duplicate mathematica.stackexchange.com/questions/32273/… – Rorschach Sep 20 '13 at 11:36
@Blackbird It's related, but definitely is not a duplicate. Here you have finite sums (of divergent series), there are symbolic infinite sums of convergent series. So e.g. efficiency is especially important. – Artes Sep 20 '13 at 16:47
@Roi Consider registering your account, so that you'll be able to better interact with this site. – Artes Sep 20 '13 at 16:49

Here's another way:

sum[n_, d_] = Sum[d k, {k, Floor[n/d]}];
f[n_] := Total[-(-1)^Length@# sum[n, Times @@ #] & /@ Subsets[{2, 3, 5, 7}, {1, 4}]]


Example

f[10^11]


3857142857207142857139

-
Beat me to it. Mathematica is a great fit for the mixed analytical/numerical solutions. There's however a 20 fold performance increase hiding in plain sight, you just need to remove one character. Reply back if you want the specifics. :) – jVincent Sep 20 '13 at 13:13
@jVincent He found it :) – Kuba Sep 20 '13 at 13:56
I think Rest@Subsets[{2, 3, 5, 7}] is more flexible.:) – chyaong Sep 20 '13 at 14:55
@chyanog Or perhaps Subsets[#, {1, Length@#}] &@ {2, 3, 5, 7}'. :) – Michael E2 Sep 20 '13 at 15:59

If we are to deal with big numbers we should exploit symbolic capabilities of the system. This
Sum[ k Boole[Or @@ Divisible[k, {2, 3, 5, 7}]], {k, n} ] would be useful for n < 10^7 but for n > 10^9 we have to provide a neat modification.
We can observe that Sum is needed only for a small subset of the whole range $\{1, \cdots , n\}$.
Since we have:

• $2\times 3\times 5\times 7 = 210$
• Count[ Range @ 210, _?(Or @@ Divisible[#, {2, 3, 5, 7}] &)] $\quad$ yields 162.
• Sum[ k Boole[Or @@ Divisible[k, {2, 3, 5, 7}]], {k, 210}] $\quad$ yields 17115.

We define the following function:

f[n_Integer]/; n >= 1 :=
With[{ c = Floor[n/210]},
( 17115 + 162 210 (c - 1)/2) c
+ Sum[k Boole[Or @@ Divisible[k, {2, 3, 5, 7}]], {k, 210 c + 1, n}]]


Now it works nicely also for big numbers:

 f /@ {1000, 10^11}

{386788, 3857142857207142857139}


or even for much much bigger:

 IntegerDigits[ f[10^10^6]] // Short

{ 3, 8, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5,
<<1999970>>, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 8, 5}

-
I think you were faster, so I deleted my answer and you have my vote :) – Jacob Akkerboom Sep 20 '13 at 11:33
@JacobAkkerboom Thanks, I think you shouldn't delete your post but rather adding another way. – Artes Sep 20 '13 at 11:37
Hehe here I am talking about the least common multiple of prime numbers. You did what my answer was hinting at, I like it. – Jacob Akkerboom Sep 23 '13 at 15:49
@JacobAkkerboom Upvoted your answer too. Nonetheless I think the answers given haven't been sufficiently appreciated. – Artes Sep 23 '13 at 15:54

Do you mean divisible by at least one of those numbers? If so, how about

Select[Range[1000], Or @@ Divisible[#, {2, 3, 5, 7}] &] // Total


386788

If you want to have the answer for a large range of numbers, you can just get the answer for a small range, up to at least the least common multiple (LCM) of the numbers. You then have the relation

numbersWithProperty[Range[lCM]] == numbersWithProperty[Range[k*lCM+1, (k+1)lCM]] - k*lCM


for

numbersWithProperty[list_] :=

Select[list, Or @@ Divisible[#, {2, 3, 5, 7}] &]


and

lCM = LCM[2, 3, 5, 7];


and for example k=1

Perhaps it is a good exercise to figure out how to finish the exercise using this?

-
Pick[#, Times @@ Table[#~Mod~i, {i, {2, 3, 5, 7}}], 0] &@Range[1000] //Tr
(*386788*)

n /. Solve[{n~Mod~2 n~Mod~3 n~Mod~5 n~Mod~7 == 0, 0 < n <= 10^3}, n, Integers] // Tr
(*386788*)


Following two would be worked for a huge number:

Sum[(1 - Unitize[i~Mod~2 i~Mod~3 i~Mod~5 i~Mod~7]) i, {i, n}];
% /. n -> 10^11
(*3857142857207142857139*)

Times @@@ # & /@ GatherBy[Rest@Subsets[{2, 3, 5, 7}], Length]
MapIndexed[Tr[(-1)^(#2 - 1)] Boole@Thread[Mod[i, #] == 0] &, %]
Total[%, -1]
Sum[(%) i, {i, n}] // Simplify
% /. n -> 10^11
(*3857142857207142857139*)

-

Part is good for this purpose.

list = Range[1000];

Total[
Union[
list[[2 ;; ;; 2]],
list[[3 ;; ;; 3]],
list[[5 ;; ;; 5]],
list[[7 ;; ;; 7]]
]
]


Or more compactly:

Total[
Union @@ (list[[# ;; ;; #]] & /@ {2, 3, 5, 7})
]
`

(Obviously this doesn't conform to the modified requirements though.)

-