On Sun, Jul 11, 2010 at 03:59:13AM +0000, mark wrote: > > Congratulations Avni, > > I just wish I could understand it. Is this a formula? Or an iterative > computer counting operation? Can you put it into algebra? I've been > looking at this also, and expected to need two different formulas, one > for odd N and another for even N. I even found two that work (produce > the correct number). They have very little justification however, > since the data set is so small. If your solution is a faster counter, > can I trust the results to verify mine? Are we still in search of a > formula?
Avni's result may be expressed as an algebraic formula. Here it is, in ASCII art. You need to view this message as "plain text" (that is, constant width font) to see it:
N ----- \ a(n) = ) (Rem(C(N,i), N) + Quo(C(N,i), N)) / ----- i = 0
where N = n^2.
I need to explain some of the notation.
The function C(N,i) is what is called "N-choose-i" in combinatorics or "the binomial coefficients" in algebra. It is defined as:
N! C(N,i) = ----------- i! (N - i)!
where the exclamation mark denotes the factorial. Note that 0! = 1 by convention. Thus C(4,0) = 1 and C(4,2) = 6.
The Quo() and Rem() in the formula are the "Quotient" and "Remainder" functions which children learn in elementary school. (These are not expressed as "functions" in elementary school because this is before the concept of a function is introduced.) For any two integers p and q, Quo(p,q) is the quotient and and Rem(p,q) is the remainder of the division of p into q. For example, Quo(23,5) = 4 and Rem(23,5) = 3.
As I wrote in an earlier message, chances are good that Avni's formula is correct but I have not been able to convince myself of its validity.