2
$\begingroup$

I'm working my way through Wolfram Challenges, the first question was Ok but tripped myself up on the second question. I have a basic function which takes a positive integer n and returns the number of multiples of both 3 and 5 up to n. It works for relatively smaller sets but after a point it gets stuck. So I am having trouble formatting it to be a proper written function. In searching for an answer myself, people online have made all sorts of elegant solutions for this popular programming problem but my question is far simpler in that I don't know why my function is failing.

f[n_Integer]:= Length[If[Mod[#, 15] == 0, #, Nothing] & /@ Range[n]]
$\endgroup$
2
  • $\begingroup$ What do you mean by "my function is failing"? It works but it is awkwardly slow for large n (it stops working though if n is so large that Range[n] cannot be stored in memory, though). $\endgroup$ Mar 24 '18 at 23:33
  • $\begingroup$ The failure is that it stops working if n is so large as the range specification does not have appropriate bounds. $\endgroup$
    – Ilker
    Mar 25 '18 at 0:37
2
$\begingroup$

You can also use IntegerPart

f[n_Integer?Positive] := IntegerPart[n/15]
$\endgroup$
4
  • $\begingroup$ As it was the case with my code, range specification in your code also does not have appropriate bounds so it stops if n is very large. Try f[10000000000000000000000000]. $\endgroup$
    – Ilker
    Mar 25 '18 at 0:38
  • $\begingroup$ @Ilker That seems unlikely, since there are no Range objects at all here. Have you been Clearing the definition of f between tests, just to make sure? $\endgroup$ Mar 25 '18 at 8:15
  • $\begingroup$ I tried f[2^1000000 7^1000000 11^1000000] // AbsoluteTiming and timing is 0.0418793sec $\endgroup$ Mar 25 '18 at 13:37
  • $\begingroup$ The code is perfectly fine ..Sorry, it was my bad...I was running bunch of codes when I tried yours ..I think I I had forgotten to clear the previous definitions. $\endgroup$
    – Ilker
    Mar 25 '18 at 16:44
4
$\begingroup$

Maybe you are looking for

f[n_Integer?Positive] := Quotient[n, 15]

Quotient[n, m] is basically equivalent to Floor[n/m].

The problem of your function is that it needs $O(n)$ memory and $O(n)$ integer operations for a task of complexity $O(1)$. Moreover, using Nothing leads to unpacking of PackedArrays which is also slowing things down.

$\endgroup$
2
  • $\begingroup$ Simple and eloquent; many thanks! And many thanks for all your very enlightening explanations. $\endgroup$
    – Ilker
    Mar 25 '18 at 0:39
  • $\begingroup$ You're welcome! $\endgroup$ Mar 25 '18 at 0:40
0
$\begingroup$

As others have said, the constant-time mathsy answer is the best. But a much more idiomatic way to do precisely what you were doing is:

Length@Select[Range[n], Mod[#, 15] == 0 &]

or

Count[Range[n], _Integer?(Mod[#, 15] == 0 &)]

This will have the same memory problems but is much faster: on my machine with n=100000, with averages taken over one hundred runs, your way takes an average 0.142167 seconds, while the two ways above are average 0.0826457 and 0.0940736 respectively.

Faster yet is:

Total[Boole[Mod[#, 15] == 0] & /@ Range[n]]

which is positively snappy at 0.00402328 seconds; it's even faster than Count[Mod[Range[100000], 15], 0].

But the winner I've found which still operates on a list is

Total[1 - Unitize[Mod[Range[n], 15]]]

which is 0.00113424 seconds: that's a full 125 times speedup over your one for n=100000.

$\endgroup$
7
  • $\begingroup$ Try also n - Total[Unitize[Mod[Range[n], 15]]]... $\endgroup$ Mar 25 '18 at 0:31
  • $\begingroup$ Length@Select[Range[n], Mod[#, 15] == 0 &], Count[Range[n], _Integer?(Mod[#, 15] == 0 &)], Total[Boole[Mod[#, 15] == 0] & /@ Range[n]], and Total[1 - Unitize[Mod[Range[n], 15]]] stop if n is so large. I get the following message: Range called with 0 arguments; between 1 and 3 arguments are \ expected. $\endgroup$
    – Ilker
    Mar 25 '18 at 0:43
  • $\begingroup$ @Ilker For which $n$ are you seeing this? You can expect the code to stop working eventually, because it's still having to create a gigantic list and operate on it. $\endgroup$ Mar 25 '18 at 8:10
  • 1
    $\begingroup$ Of course it stops working in that situation. You have asked your computer to hold in memory more numbers than there are atoms in the universe. $\endgroup$ Mar 25 '18 at 17:30
  • 1
    $\begingroup$ @Ilker, let me give you something to ponder on. You can use ByteCount[] to reckon out the amount of bytes needed to store something. For example, ByteCount[2*10^9] says that 16 bytes are needed to store that integer. Now think about what you were trying to do, and consider the number of bytes needed for all those numbers, and then compare with the size of your computer's memory and hard disk space. $\endgroup$
    – J. M.'s torpor
    Mar 25 '18 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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