Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
2  
What did you try? And are you trying to solve some project Euler question? –  Pinguin Dirk Sep 20 '13 at 11:25
1  
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
2  
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
1  
@Roi Consider registering your account, so that you'll be able to better interact with this site. –  Artes Sep 20 '13 at 16:49
show 1 more comment

5 Answers

up vote 9 down vote accepted

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

share|improve this answer
    
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
1  
@jVincent He found it :) –  Kuba Sep 20 '13 at 13:56
2  
I think Rest@Subsets[{2, 3, 5, 7}] is more flexible.:) –  chyaong Sep 20 '13 at 14:55
1  
@chyanog Or perhaps `Subsets[#, {1, Length@#}] &@ {2, 3, 5, 7}'. :) –  Michael E2 Sep 20 '13 at 15:59
add comment

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}
share|improve this answer
    
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
add comment

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?

share|improve this answer
add comment
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*)
share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.