2
$\begingroup$

I believe this is a standard problem, but I could not find a solution anywhere. Possibly because I don't know what to look for. I define a subset of some numbers and I want to count how many are less or equal to $x$. (Is there a better way to do this?)

table=Table[N[n^2+m^2],{n,1,3000},{m,1,3000}];
sortedlist=Sort[Apply[Join,Array[table[[#]]&,50]]];
counter[x_]:=Length[Select[sortedlist,#<=x&]];

When I plot the function counter[x] it works but it takes really long. I assume this is because some part of my definition makes Mathematica evaluate the whole expression over and over again without need. I am really new to Mathematica and I assume that this problem probably has a neat solution already which I just could not find anywhere. Thank you for any advice!

$\endgroup$
3
  • 1
    $\begingroup$ "When I plot the function counter[x] it works but it takes really long. " How do you plot counter[x]? Plot[counter[x], {x, 0, 9 10^6}] takes only 6.28 seconds on my laptop. $\endgroup$
    – xzczd
    Sep 21 at 11:13
  • $\begingroup$ Your definition for sortedlist could simply be sortedlist=Sort@Catenate@table[[;;50]] i think. As for counter: You could probably try LengthWhile[sortedlist,#<=x&] to exploit the fact that you know the list is sorted. $\endgroup$
    – Lukas Lang
    Sep 21 at 11:14
  • $\begingroup$ What is the actual problem you want to solve? Why the 50 in Array[table[[#]] &, 50]? $\endgroup$
    – Somos
    Sep 22 at 23:50
4
$\begingroup$

A zero-order interpolation is a good way to in effect invert the function from positive integers to values in sortedlist.

Timing[
 table = Table[N[n^2 + m^2], {n, 1, 3000},
  {m, 1, 3000}];
 sortedlist = Sort[Apply[Join,
  table[[1 ;; 50]]]];
 lastpairs = 
  SplitBy[Join[{{0, 0}}, 
     Transpose[{sortedlist,
       Range[Length[sortedlist]]}]], 
     First][[All, -1]];
 ii = Interpolation[lastpairs,
  InterpolationOrder -> 0];]

(* Out[455]= {2., Null} *)

It can be plotted like so.

Plot[ii[t], {t, 1, Last[sortedlist]}]

enter image description here

$\endgroup$
3
$\begingroup$

Here are some suggestions for simpler methods to find the counts, and to make a plot.

Instead of Array[table[[#]]&, 50]] use table[[;; 50]]. Check the documentation for Part.

An easy way to count the number of values that are less or equal to $x$, is to count the values with Tally, and then total the tallies with Accumulate.

table = Table[N[n^2 + m^2], {n, 1, 3000}, {m, 1, 3000}];

counts = Sort[Tally[Flatten[table[[;; 50]]]]];
counts[[All, 2]] = Accumulate[counts[[All, 2]]];
counts

It's easy to graph the counts of values less than or equal to $x$ with Histogram.

Histogram[Flatten[table[[;; 50]]], Automatic, "CumulativeCount"]

cumulative histogram

$\endgroup$

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.