posted by ![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
emperor at 11:38am on 27/12/2005
emperor at 11:38am on 27/12/2005Consider a piece of code that does:
ETA: I should mention (doh) that
It seems to me that given N and g you ought to be able to just calculate the resulting values of N and g, without having to iterate.
Alas, I am too stupid to see how. Can anyone help?
while(N>=g){
N=N-(g-1);
g=g-1;
}
ETA: I should mention (doh) that
g>3 and N<=(g)(g-1)(g-2)/6It seems to me that given N and g you ought to be able to just calculate the resulting values of N and g, without having to iterate.
Alas, I am too stupid to see how. Can anyone help?
(no subject)
(no subject)
(no subject)
(no subject)
(no subject)
N-ng+1/2n(n+1) < g-n
Then the expressions either side of the < are your new values for N and g respectively
(no subject)
So:
N1 = N0 - (g0-1).
N2 = N0 - (2g0-3).
N3 = N0 - (3g0-6).
N4 = N0 - (4g0-10).
And so on. In general, Ni is equal to N0, minus i times g0, plus the ith triangular number. Now the ith triangular number is equal to i(i+1)/2 (most easily seen when you put two side-i triangles together into an i by i+1 rectangle, although there are more "mathsy" proofs available if you prefer), which means that
Ni = N0 - ig0 + i(i+1)/2
Also gi = g0 - i, but that one really should have been obvious :-)
If you're interested in finding out when the loop terminates, you can subtract the above formulae to find Ni-gi, which will be a quadratic in i which you can solve in the normal way to find out when it crosses zero. As other commenters have pointed out, it may not cross zero at all: the i2 coefficient of the quadratic is always positive, meaning it has a minimum value which might also be positive depending on the values of N0 and g0. In this situation your original loop will never terminate.
(no subject)
(no subject)
i = g -1 +/- sqrt(g^2-2N+1)
that simplifies quite nicely :-)
(no subject)
i = g - 3/2 +/- sqrt (g^2 -g -2N +1)
if I don't try and lose 1/2 a g...
It is very early in the morning.
param N, g;
var x;
gf=g-x;
Nf=N-(T(g-1)-T(gf-1))where T(n) = n*(n+1)/2; /* call it a trapezoid number */
subject to: Nf<gf and Nf+gf >= gf+1.
Hm...
Nf' = Nf - gf = N - T(g-1) + T(gf) /* since T(n) = T(n-1) + n; not sure if that matters */
subject to: Nf'<0 and Nf' >= 1 - gf
So... find the largest value of gf such that T(gf) < T(g-1) - N — and there's probably a constant-time way to do it, since it's mostly a square root — and that's the final value of g, and compute Nf by the equation in the first blob. Unless I've made an off-by-one (or worse) error somewhere, which is entirely likely.
And now I'll go peek at the other comments.