1
$\begingroup$

I have the following equation: $$f(L) = \left\lfloor{\frac{1}{4}\sum_{n=1}^{L-1}\left\lfloor n+300\times2^{n/7}\right\rfloor}\right\rfloor$$ where $1\leq L \leq 99$

My goal is to find a closed-form solution for this equation(if one exists) or an approximation. I tried

f[L_] := Floor (0.25 *
    Sum[Floor (n + 300*Power[2, n/7]), {n, 1, L - 1}])
FullSimplify[f[L], L >= 1 && L <= 99]

In Mathematica

Output:

Floor^2 (-795.534 + 720.534 2^(L/7) + (-0.125 + 0.125 L) L)

However this seems to only give me an approximation because the output is off by up to 15 (compared to the original equation) also i was confused about what Floor^2 meant so when doing the tests i just assumed it referred to the Floor function.

Are there functions in Mathematica that i can use to find a closed-form solution or a better approximation for this equation? I also tried Simplify and FindFormula but both of them had a far larger error margin compared to using FullSimplify

Edit: after fixing the mistake(had to use square brackets instead of paranthesis)

f[L_]:=Floor[1/4*Sum[Floor[n+300*Power[2,n/7]],{n,1,L-1}]];
FullSimplify[f[L]]

outputs the following(took a pic as it wouldn't let me copy properly) enter image description here

Which is not what im after either (I need a closed-form solution)

$\endgroup$
10
  • $\begingroup$ If I compare Floor[-795.534 + 720.534* 2^(L/7) + (-0.125 + 0.125 L) L] to the function you start with it is off by 15 for the last few points, which is only an error of 1.1*^-6. In fact, the error is worse when the function is only 'off' by 1 for low values of L. Depending on what you need this for, I'd say that's a pretty good approximation. I don't think there's any reason to suspect a "closed form" solution is available for this particular expression. $\endgroup$
    – N.J.Evans
    May 4, 2022 at 12:12
  • $\begingroup$ For what it's worth, your expression is a finite sum as long as L isn't infinity, so I'd call it closed form. I assume because you're asking for a closed form you mean something more restrictive, which you might need to specify. $\endgroup$
    – N.J.Evans
    May 4, 2022 at 12:15
  • 1
    $\begingroup$ I have better approximation ,but output is off by up to 3. :) $\endgroup$ May 4, 2022 at 12:18
  • 1
    $\begingroup$ f[L_]:=Floor[(75 (-2^(1/7) + 2^(L/7)))/(-1 + 2^(1/7)) + 1000/8071*(-1 + L) L] $\endgroup$ May 4, 2022 at 12:28
  • 1
    $\begingroup$ This is a known sequence given at oeis.org/…. But it lists no closed-form or approximation. $\endgroup$
    – JimB
    May 4, 2022 at 16:11

4 Answers 4

4
$\begingroup$

This seems good:

f2[L_] := 
 Floor[
  -((75 (2^(1/7) - 2^(L/7)))/(-1 + 2^(1/7))) - 
   (14498 L)/63125 + 
   L^2/8];

Comparison:

tab = Table[f[L] - f2[L], {L, 1000}];
ListPlot[tab, GridLines -> {{}, MinMax@tab}]
(* takes a while - did something else, didn't time it *)
tab = Table[f[L] - f2[L], {L, 10, 10000, 10}];
ListPlot[tab,
 GridLines -> {{}, MinMax@tab}, DataRange -> {10, 10000}]

Update — A brief explanation:

The function is equal to the floor of $$\frac{L^2}{8}-\frac{L}{8}-\frac{75 \left(\sqrt[7]{2}-2^{L/7}\right)}{\sqrt[7]{2}-1} - \alpha(L)\,\frac{L}{4}\,\qquad 0<\alpha(L)<1 \,.$$ Estimating $\alpha$, which is the correction due the rounding down by Floor[] in the sum, is tricky because it oscillates. I tweaked it for $L$ up to $10\,000$. There's a slight divergence as $L$ increases to $20\,000$. One can see that $\alpha$ depends on the binary expansions of $2^{k/7}$, $k=1,\dots,6$; and there may be other number theory that can be brought to bear on the problem, but I'm rusty at it.

If people want to play with it, here's a more efficient way to compute f[L]:

ClearAll[sf1, f1];
sf1[L_Integer?Negative] = 0;
sf1[1] = 0;
sf1["limit"] = 1;
sf1["limit", L_] /; sf1["limit"] >= L := True;
sf1["limit", L_] := (Do[sf1[LL], {LL, sf1["limit"], L - 1}]; 
   sf1["limit"] = Max[sf1["limit"], L - 1]; True);
mem : sf1[L_Integer] := 
  mem = sf1[L - 1] + (1/4*Floor@(L - 1 + 300*Power[2, (L - 1)/7]));
f1[L_Integer?Positive] /; sf1["limit", L] := Floor@sf1[L];

The fancy sum-limit voodoo is because there is a recursion limit. Without the trickery, you could not compute f1[L] for L greater than the previous largest L by 1022 or more. But as far as efficiency, f1[10000] computes all values for L up to 10000 in a millisecond or two longer than it takes f[10000] to compute just one value. Even if one memoizes the results of f with

mem : f[L_] := 
  mem = Floor@(1/4*Sum[Floor@(n + 300*Power[2, n/7]), {n, 1, L - 1}])

it still takes ~900 sec. to compute the rest of f[L], 0 < L < 10000. And for L up to 100000, f1 finishes in two seconds, whereas f would take nearly a day (I estimate).

$\endgroup$
3
  • $\begingroup$ This is actually great, it is only off by one at most for values of L between 1 and 99, i chose this as the accepted answer as this is far shorter & easier to evaluate compared to the solution in the previous accepted answer My goal is to still get the error rate to below 1, but even this is really good. $\endgroup$
    – Suic
    May 4, 2022 at 16:07
  • 1
    $\begingroup$ @Suic Thanks. It's ok to wait a while before accepting, since marking it as accepted makes it look like there's no point in even reading the question.. We used to advise people to wait 24 hrs so that everyone around the world could get a chance. There may be experts who can give even better answers. $\endgroup$
    – Michael E2
    May 4, 2022 at 16:22
  • $\begingroup$ ah yeah ur right, i'll keep that in mind. $\endgroup$
    – Suic
    May 4, 2022 at 16:30
5
$\begingroup$

I would fit it to a polynomial and check the difference. Below I fit it to a 20-degree poly. The difference between actual and fit is less than 0.6 for all values in range $1<n<99$:

   ClearAll[fFit, vals]
f[L_] := Floor[1/4*Sum[Floor[n + 300*Power[2, n/7]], {n, 1, L - 1}]];
nMax = 99;
vals = Table[{n, f[n]}, {n, 1, nMax}];
p1 = ListPlot[vals]
fFit[x_] = Fit[vals, Table[x^n, {n, 0, 20}], x];
p2 = Plot[fFit, {x, 0, nMax}, PlotStyle -> Red];
plots = Show[{p1, p2}, PlotLabel -> Style["Fit", 16, Bold, Black]];
difTable = 
 Table[{n, Abs[(fFit[n]) - vals[[n, 2]]]}, {n, 1, Length@vals}]
GraphicsRow[{plots, 
  ListPlot[difTable, 
   PlotLabel -> Style["Difference", 16, Bold, Black]]}]

enter image description here

$\endgroup$
10
  • $\begingroup$ Does that mean that the difference is less than 0.6% or 0.6 literally? $\endgroup$
    – Suic
    May 4, 2022 at 13:05
  • $\begingroup$ @Suic, check code: Checking absolute value of the difference of fit function and actual value $\endgroup$
    – josh
    May 4, 2022 at 13:07
  • $\begingroup$ sorry, but i only started with Mathematica today so im still learning, how exactly does the fit function work? i can see that it generates a Table but what i'd need is a closed-form solution so i would want to directly compute the result of the fit function if possible (by closed form as i mentioned in the comments of the question i mean a direct computation, i.e not iterating from 1 to L - 1 or first generating a table using that function) $\endgroup$
    – Suic
    May 4, 2022 at 13:13
  • 1
    $\begingroup$ But fFit still uses a table(unless i am misunderstanding something) what i need is a direct / closed-form equation that either gives me the exact solution or an approximation where the error rate is less than 1 An example of what i mean: f[L_]:=Floor[(75 (-2^(1/7) + 2^(L/7)))/(-1 + 2^(1/7)) + 1000/8071*(-1 + L) L] (credit to Mariusz Iwaniuk for providing this in the comments of the question) this is a direct equation that doesn't use a table or iterate from 1 to L - 1 like the original equation (which is exactly what i want) unfortunately the error margin is up to 3, but i need it to be < 1 $\endgroup$
    – Suic
    May 4, 2022 at 13:34
  • 2
    $\begingroup$ @Suic. You can extract formula: g[L_] := Rationalize[(fFit /. x -> L), 0]; g[L] $\endgroup$ May 4, 2022 at 13:51
2
$\begingroup$

Assuming that L is a a positive Integer 1<=L<=99. Then for a specific L the expression is easily calculated:

f[L_]:=Floor[1/4*Sum[Floor[n+300*Power[2,n/7]],{n,1,L-1}]];

If you need this function many times, you may use memoization and then pre-calculate the function values:

f[L_]:=f[L]=Floor[1/4*Sum[Floor[n+300*Power[2,n/7]],{n,1,L-1}]];

Do[f[i],{i,1,99}]

If you now look at f, you see that it is defined for all integers in range:

enter image description here

....

$\endgroup$
1
$\begingroup$

You need square brackets:

f[L_]:=Floor[1/4*Sum[Floor[n+300*Power[2,n/7]],{n,1,L-1}]];

Then do this:

Table[f[L],{L,1,99}]

$\endgroup$
5
  • $\begingroup$ ah yeah i used paranthesis instead of square brackets for the inner floor by mistake. However this just gives me an array of outputs for L in the range of 1-99, what i want is a closed form solution or a better approximation than above for the function. $\endgroup$
    – Suic
    May 4, 2022 at 11:59
  • $\begingroup$ You explicitly restricted L to be between 1 and 99. Can you be more precise then about which L you are interested in? All positive integers? $\endgroup$
    – user293787
    May 4, 2022 at 12:05
  • $\begingroup$ Ideally i would like it to work for all positive integers yes, however my real input is most likely going to be between 1 and 99 $\endgroup$
    – Suic
    May 4, 2022 at 12:10
  • $\begingroup$ I am not sure what more you can ask for (from a practical perspective) then the explicit list of 99 numbers (no approx involved)? You just have to run the computation once, store the result in an array, and look up the result whenever needed ( in case your main concern is speed). $\endgroup$
    – user293787
    May 4, 2022 at 12:16
  • $\begingroup$ Yeah i understand that, but as i said in the comments(of the question) i am simply curious whether it is possible to compute directly(which is what i meant by a closed-form solution) instead of iterating from 1 to L - 1 $\endgroup$
    – Suic
    May 4, 2022 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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