# Really slow evaluation of a simple? list expression

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!

• "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. Sep 21 at 11:13
• 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. Sep 21 at 11:14
• What is the actual problem you want to solve? Why the 50 in Array[table[[#]] &, 50]? Sep 22 at 23:50

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]}]


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"]